Technical Perspective: Finding Connections between One-Way Functions and Kolmogorov Complexity

Cryptography requires “useful” sources of computational hardness for most of its constructs. For example, in the classic setting of encryption schemes, decryption should be easy when given an appropriate decryption key, while it must be infeasible without it. Fortunately, the theory of computational complexity generously provides a wide variety of sources of computational hardness, but which ones may be useful for cryptography?

The long-celebrated interplay between cryptography and computational complexity has been challenged constantly with understanding what “useful” hardness means, where it may be found, and how it may be utilized. This has led the cryptography community to embark on an exciting journey initiated by the pioneering work of Whitfield Diffie and Martin Hellman back in 1976. One of the most instrumental early contributions of this fruitful journey was the introduction of an extremely modest cryptographic primitive referred to as a one-way function—a function that is easy to evaluate but hard to invert. The modest nature of one-way functions turned out to serve as a “minimal” form of useful hardness in the sense that the existence of nearly any cryptographic construct implies that of a one-way function. Despite their modest nature, a significant effort over the years showed that one-way functions are in fact sufficient for many of the most central cryptographic tasks. Specifically, one-way functions suffice for nearly all private-key primitives (for example, private-key encryption schemes and signature schemes).

For the most part, cryptographers have obtained rather satisfying answers to two of the challenges mentioned here: Understanding what useful hardness means and how it may be utilized (there are still many unresolved related challenges, such as whether one-way functions are sufficient also for public-key cryptography). However, when it comes to understanding where useful hardness may be found, the situation is subtle. On one hand, a variety of candidate one-way functions are widely deployed. On the other hand, any unconditional proof that one-way functions exist would imply that P ≠ NP, and thus currently seems out of reach.

Luckily, cryptographers are not intimidated by this frustrating situation. Instead, research in the foundations of cryptography addresses it by reasoning about the existence of one-way functions, and particularly about the possibility of basing their existence on assumptions that are either seemingly weaker or that may offer alternative perspectives. The following paper by Yanyi Liu and Rafael Pass does precisely that by establishing surprisingly tight bidirectional connections between one-way functions and the cross-domain notion of Kolmogorov complexity. It is the second out of two breakthrough papers by the authors, presenting such connections between one-way functions and Kolmogorov complexity—whose introduction in the 1960s predates the birth of modern cryptography in the 1970s!

What is Kolmogorov complexity, and what did the authors show? Kolmogorov complexity quantifies the “amount of randomness” in individual strings: Given a string x, its Kolmogorov complexity is defined as the length of the shortest program P that outputs it (this explains in part why we would consider the string abababababababab to be “less random” than the string 4c1j5b2p-0cv4w1x8). Kolmogorov complexity is, in general, incomputable, and this has led to considering two complementing computational analogs. The first is time-bounded Kolmogorov complexity, which considers programs that run in at most a prespecified number of steps. The second is Levin-Kolmogorov complexity which directly incorporates running time as an additional cost at a logarithmic scale (thus, any polynomial-time program incurs only a small additional cost).

Liu and Pass present a fresh and complete characterization of the existence of cryptography’s most basic construct. Specifically, they constructively proved the existence of one-way functions is equivalent to the average-case hardness of computing time-bounded Kolmogorov complexity. Note that appropriately formalizing the task of computing time-bounded Kolmogorov complexity as a decisional problem positions it in the class NP. Thus, this result pins down a natural NP problem whose average-case hardness is equivalent to the existence of one-way functions.

However, the task of computing time-bounded Kolmogorov complexity is not known to be complete for NP, and therefore this result falls short of characterizing the existence of one-way functions based on arbitrary average-case NP-hardness. In their second paper, the authors showed that Levin-Kolmogorov complexity does enable to reason about the possibility of basing the existence of one-way functions on general limitations of feasible computation. They proved that the question of whether one-way functions can be based on the assumption that BPP ≠ EXP is equivalent to a seemingly “minor” technical gap between two-sided error and errorless average-case hardness of computing Levin-Kolmogorov complexity. They also demonstrated that any reduction bridging this gap implies that P ≠ NP.

Equipped with this fresh perspective, the cryptography community is looking forward to seeing the extent to which this work will lead to additional exciting insights. A quest for such understanding into the connections between cryptography and Kolmogorov complexity has fantastic potential in leading to fruitful cross-domain interactions and extending our ability to reason on the existence of cryptographic constructs well beyond one-way functions.