One-Way Functions and a Conditional Variant of MKTP

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

TL;DR

This paper establishes a crucial link between the existence of one-way functions (OWFs) and the average-case hardness of a specific NP-complete problem called Minimum Conditional KT-complexity Problem (McKTP). They show that McKTP is NP-complete and that its average-case hardness is equivalent to the existence of OWFs, providing a natural NP-complete problem that cryptographers have been seeking.

What Problem Does This Paper Address?

The field of cryptography heavily relies on the existence of one-way functions (OWFs) – functions that are easy to compute but hard to invert. While it's known that OWFs exist if and only if certain computational problems are hard on average, the connection to natural NP-complete problems has been elusive. Previous work showed that average-case hardness of time-bounded Kolmogorov complexity (Kt) implies OWFs, but Kt is not known to be NP-complete. The authors aim to bridge this gap by investigating a conditional variant of Minimum KT-complexity Problem (McKTP), which is NP-complete, and demonstrating its equivalence to OWFs under average-case hardness assumptions. This is significant because NP-complete problems are considered the "hardest" problems in NP, and finding a natural NP-complete problem whose average-case hardness is equivalent to OWFs would be a major theoretical breakthrough.

Methods

The paper employs a combination of techniques from computational complexity theory and cryptography. Key methods include:

  • Average-case decision-to-search reductions: They show how to transform an average-case solver for the decision version of McKTP into a solver for its search version.
  • Leveraging existing results: The authors build upon prior work by Liu and Pass [20] and Ren and Santhanam [28] concerning Kolmogorov complexity and its relation to OWFs.
  • NP-completeness proofs: They establish that McKTP is NP-complete under polynomial-time randomized reductions, a standard technique in complexity theory.
  • Conditional KT-complexity: The core of their work revolves around the Minimum Conditional KT-complexity Problem (McKTP), a variant of KT complexity that allows for conditional inputs, making it amenable to NP-completeness proofs.
  • Randomized reductions: To prove McKTP's NP-hardness, they utilize randomized reductions, specifically adapting techniques used for approximating Set Cover.

Datasets

Not discussed in the paper. The paper deals with theoretical computational problems and their properties, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • McKTP as a Cryptographic Primitive: The paper identifies McKTP as a natural NP-complete problem whose average-case hardness is directly tied to the existence of one-way functions. This is a significant step towards grounding cryptography in the hardness of well-understood NP-complete problems.
  • Equivalence of OWFs and McKTP Hardness: The central finding is the equivalence: OWFs exist if and only if McKTP is hard on average. This is a strong theoretical result that connects two fundamental concepts in computer science.
  • Logspace-Computable OWFs: The authors further refine this equivalence, showing that logspace-computable OWFs exist if and only if McKTP is hard on average. This is a more specific and potentially stronger result, as logspace computation is a more restricted model.
  • McKTP's NP-Completeness: Establishing McKTP's NP-completeness under randomized reductions is crucial for its relevance as a candidate for cryptographic hardness.

Key Results

The paper presents several key theorems and corollaries:

  • Theorem 1 (Informal): If McKTP is average-case hard on a polynomial fraction of its instances, then OWFs exist.
  • Theorem 2 (Informal): McKTP is NP-complete under polynomial-time one-sided-error randomized reductions.
  • Theorem 3 (Informal): Logspace-computable OWFs exist if McKTP is average-case hard on a polynomial fraction of its instances.
  • Theorem 4 (Informal): OWFs exist only if McKTP is hard-on-average on an exponential fraction of its instances.
  • Theorem 5 (Informal): Logspace-computable OWFs exist only if McKTP is hard-on-average on a polynomial fraction of its instances.
  • Corollary 6: McKTP is hard-on-average if and only if logspace-computable OWFs exist.

Limitations and Future Work

  • "Naturalness" of McKTP: While McKTP is presented as a "natural" NP-complete problem, the paper acknowledges that the definition of "natural" can be subjective. Further exploration into other NP-complete problems and their relationship to OWFs would be valuable.
  • Average-Case Hardness Assumptions: The paper relies on average-case hardness assumptions for McKTP. Understanding the precise nature of these assumptions and their implications for practical cryptography remains an area for future research.
  • Pessiland Exclusion: The authors suggest that proving McKTP is NP-hard under average-case reductions could exclude "Pessiland" (a hypothetical world with average-case hard NP problems but no OWFs). This remains an open direction.
  • Further Exploration of KT Complexity: The paper uses KT complexity as a foundation. Deeper investigations into the properties of KT complexity and its variants could lead to new insights in both complexity theory and cryptography.

Summary updated

Abstract

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some natural NP-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows. 1) First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs. 2) Then, we observe that McKTP is NP-complete under polynomial-time randomized reductions. 3) Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP. Thus the existence of OWFs is inextricably linked to the average-case hardness of this NP-complete problem. In fact, building on recently-announced results of Ren and Santhanam [Rahul Ilango et al., 2021], we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs.
BibTeX
@inproceedings{allender2021one,
  author = {Eric Allender and Mahdi Cheraghchi and Dimitrios Myrisiotis and Harsha Tirumala and Ilya Volkovich},
  title = {{One-Way Functions and a Conditional Variant of MKTP}},
  booktitle = {FSTTCS},
  year = {2021},
  doi = {10.4230/lipics.fsttcs.2021.7},
}
Figure