A Duality between One-Way Functions and Average-Case Symmetry of Information
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
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.
Topics & Concepts
ConverseBounded functionProperty (philosophy)Duality (order theory)Symmetry (geometry)Kolmogorov complexityCryptographyDiscrete mathematicsMathematicsOne-way functionComputer scienceCombinatoricsAlgorithmMathematical analysisGeometryEpistemologyPhilosophyComputability, Logic, AI AlgorithmsBenford’s Law and Fraud DetectionCryptography and Data Security