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

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$^t$ 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.

Available format(s)
Publication info
Published elsewhere. Symposium on Theory of Computing (STOC), 2023
one-way functionssymmetry of informationKolmogorov complexityaverage-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
2023-03-24: approved
2023-03-23: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.