ECCC-Report TR23-035https://eccc.weizmann.ac.il/report/2023/035Comments and Revisions published for TR23-035en-usSun, 26 Mar 2023 07:44:25 +0300
Paper TR23-035
| A Duality Between One-Way Functions and Average-Case Symmetry of Information |
Shuichi Hirahara,
Rahul Ilango,
Zhenjian Lu,
Mikito Nanashima,
Igor Carboni Oliveira
https://eccc.weizmann.ac.il/report/2023/035Symmetry 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.Sun, 26 Mar 2023 07:44:25 +0300https://eccc.weizmann.ac.il/report/2023/035