[Resource Topic] 2023/424: A Duality Between One-Way Functions and Average-Case Symmetry of Information

Welcome to the resource topic for 2023/424

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

Authors: Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira


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.

ePrint: https://eprint.iacr.org/2023/424

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .