A Duality Between One-Way Functions and Average-Case Symmetry of Information

Shuichi Hirahara; Rahul Ilango; Zhenjian Lu; Mikito Nanashima; Igor C. Oliveira

Paper 2023/424

A Duality Between One-Way Functions and Average-Case Symmetry of Information

Shuichi Hirahara, National Institute of Informatics

Rahul Ilango, Massachusetts Institute of Technology

Zhenjian Lu, University of Oxford

Mikito Nanashima, Tokyo Institute of Technology

Igor C. Oliveira, University of Warwick

Abstract

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) established that if SoI holds for time-bounded Kolmogorov complexity then cryptographic one-way functions do not exist, and asked if a converse holds. We show that one-way functions exist if and only if (probabilistic) time-bounded SoI fails on average, i.e., if there is a samplable distribution of pairs (x,y) of strings such that SoI for pK complexity fails for many of these pairs. Our techniques rely on recent perspectives offered by probabilistic Kolmogorov complexity and meta-complexity, and reveal further equivalences between inverting one-way functions and the validity of key properties of Kolmogorov complexity in the time-bounded setting: (average-case) language compression and (average-case) conditional coding. Motivated by these results, we investigate correspondences of this form for the worst-case hardness of NP (i.e., NP ⊄ BPP) and for the average-case hardness of NP (i.e., DistNP ⊄ HeurBPP), respectively. Our results establish the existence of similar dualities between these computational assumptions and the failure of results from Kolmogorov complexity in the time-bounded setting. In particular, these characterizations offer a novel way to investigate the main hardness conjectures of complexity theory (and the relationships among them) through the lens of Kolmogorov complexity and its properties.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Symposium on Theory of Computing (STOC), 2023
Keywords: one-way functions symmetry of information Kolmogorov complexity average-case complexity
Contact author(s): s_hirahara @ nii ac jp
rilango @ mit edu
zhenjian lu @ cs ox ac uk
nanashima m aa @ is c titech ac jp
igor oliveira @ warwick ac uk
History: 2023-03-24: approved; 2023-03-23: received; See all versions
Short URL: https://ia.cr/2023/424
License: CC BY

BibTeX

@misc{cryptoeprint:2023/424,
      author = {Shuichi Hirahara and Rahul Ilango and Zhenjian Lu and Mikito Nanashima and Igor C. Oliveira},
      title = {A Duality Between One-Way Functions and Average-Case Symmetry of Information},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/424},
      year = {2023},
      url = {https://eprint.iacr.org/2023/424}
}