SaTC: CORE: Small: On Cryptography and Kolmogorov Complexity

Cornell University, Ithaca NY

Investigators

Abstract

Whether one-way functions (OWFs) exist is arguably the most important problem in Cryptography: OWFs are known to be both necessary and sufficient for most of the basic cryptographic building blocks, such as CPA-secure private-key encryption, pseudorandom generators and functions, digital signatures, and authentication protocols, to name but a few. But the question of whether OWFs properly exist is wide open. Until very recently, known candidate constructions of OWFs relied on various types of conjectures, be they number-theoretic or lattice-based, but none of them are known to be equivalent to the existence of OWFs. The goal of this project is to develop a closer connection between standard complexity-theoretic problems---and most notably those arising from the study of Kolmogorov complexity---and cryptographic assumptions, such as OWFs. In recent work, the investigator has presented the first natural complexity-theoretic problem whose average-case hardness characterizes the existence OWFs: It was shown that the existence of OWFs is equivalent to (mild) average-case hardness of the so-called "time-bounded Kolmogorov complexity problem", a central problem in algorithmic information theory that has been studied since the 1960s. This project aims to leverage and further develop this connection between Cryptography and Kolmogorov Complexity. Concrete directions include: (a) identify additional natural problems whose average-case hardness is equivalent to the existence of OWFs; (b) characterize OWFs with additional structure, or more advanced cryptographic primitives; (c) demonstrate limitations of basing OWFs on general average-case hardness of NP; (d) study the possibility of basing cryptographic primitives, or relaxations thereof, on the worst-case hardness of primitives related to Kolmogorov complexity. Taken together, the goal is to provide a stronger theoretical underpinning of OWFs (with or without extra structure), and to further elucidate to what extent the existence of such functions can be based on more standard complexity-theoretic assumptions (such as NP != P). This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.