Communications of the ACM

Research Highlights

Toward Basing Cryptography on the Hardness of EXP

By Yanyi Liu, Rafael Pass
Communications of the ACM, May 2023, Vol. 66 No. 5, Pages 91-99
10.1145/3587167
Comments

Let Kt(x) denote the Levin-Kolmogorov Complexity of the string x, and let MKtP denote the language of pairs (x, k) having the property that Kt(x) ≤ k. We demonstrate that:

• MKtP ∉ Heur_negBPP (i.e., MKtP is two-sided error mildly average-case hard) iff infinitely-often OWFs exist.
• MKtP ∉ Avg_negBPP (i.e., MKtP is errorless mildly average-case hard) iff EXP ≠ BPP.

Taken together, these results show that the only "gap" toward getting (infinitely-often) OWFs from the assumption that EXP ≠ BPP is the seemingly "minor" technical gap between two-sided error and errorless average-case hardness of the MKtP problem.

Back to Top

1. Introduction

A one-way function⁶ (OWF) is a function f that can be efficiently computed (in polynomial time), yet no probabilistic polynomial-time (PPT) algorithm can invert f with inverse polynomial probability for infinitely many input lengths n. Whether one-way functions exist is unequivocally the most important open problem in cryptography (and arguably the most important open problem in the theory of computation, see e.g., Levin¹⁹): OWFs are both necessary¹² and sufficient for many of the most central cryptographic primitives and protocols (e.g., pseudorandom generators,^{2, 11} pseudo-random functions,⁷ private-key encryption,⁸ etc.)

While many candidate constructions of OWFs are known, the question of whether OWFs can be based on some "standard" complexity-theoretic assumption is mostly wide open.

---

No entries found

Log in to Read the Full Article