The Complexity of Public-Key Cryptography

Boaz BarakTutorials on the Foundations of Cryptography 2017 · DOI · DBLP

TL;DR

This paper surveys the computational foundations of public-key cryptography, questioning the assumptions underlying its security. It explores the evidence for these assumptions, particularly the difficulty of problems like integer factoring and discrete logarithms, and discusses the implications of potential breakthroughs in solving them, especially in the context of quantum computing.

What Problem Does This Paper Address?

The paper addresses the fundamental question of what makes public-key cryptography secure. It highlights that, unlike private-key cryptography which can be based on the general concept of one-way functions, public-key cryptography currently relies on a limited set of "structured" problems, primarily those related to algebraic groups (like factoring and discrete logarithms) and geometric/lattice-based problems. The core problem is to understand if these structured assumptions are truly necessary for public-key cryptography, or if there's a more fundamental basis, and to assess the evidence for their hardness, especially in light of potential quantum attacks. The paper also delves into the social and philosophical aspects of relying on unproven mathematical assumptions in a scientific field.

Methods

The paper employs a survey and theoretical analysis approach. It reviews existing cryptographic constructions and the computational hardness assumptions they rely on. The author categorizes these assumptions into "algebraic" (group-theoretic) and "geometric" (lattice/coding-based) families. A significant part of the paper is dedicated to exploring the evidence for the hardness of these problems, including known classical and quantum algorithms, and discussing hypothetical scenarios like the discovery of efficient algorithms. It also examines alternative constructions and theoretical frameworks, such as Impagliazzo's "worlds" of computational complexity, to contextualize the current state of public-key cryptography.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "Crisis" in Public-Key Cryptography: The paper suggests a potential "crisis" in public-key cryptography due to the fact that current secure schemes largely rely on a small number of structured assumptions. The advent of quantum computers (via Shor's algorithm) threatens the security of the "algebraic" family, leaving lattice-based cryptography as the primary alternative.
  • Limited Foundation for Public-Key Crypto: Unlike private-key cryptography, which has a broad foundation in one-way functions, public-key cryptography seems to be built on a narrower set of assumptions. This raises questions about its fundamental security and whether it can be based on more diverse or less structured problems.
  • The Role of Structure in Hardness: The paper explores the idea that computational problems are hard because they lack certain structures that would make them easy to solve. This is contrasted with problems that have exploitable algebraic or geometric structures.
  • Evidence for Hardness is Indirect: The primary evidence for the hardness of cryptographic assumptions is the lack of efficient algorithms to break them, rather than direct proof of their difficulty. This is analogous to the evidence for P ≠ NP.
  • Impagliazzo's Worlds: The paper uses Impagliazzo's framework of computational complexity "worlds" to illustrate how different assumptions about problem hardness would impact cryptography, highlighting the current state as potentially leaning towards "Cryptomania" (where LWE holds) or "Obfustopia."

Key Results

  • Shor's Algorithm Threatens Algebraic Schemes: The paper reiterates that Shor's algorithm provides polynomial-time quantum solutions for factoring and discrete logarithms, undermining the security of widely used algebraic public-key cryptosystems.
  • Lattice-Based Cryptography as a Primary Alternative: Lattice and coding-based schemes are presented as the most promising current alternatives, though they also have their own vulnerabilities and structural properties that could be exploited.
  • No Known Reductions Between Diverse Hard Problems: The paper notes that while reductions exist between many problems within the "algebraic" or "geometric" families, there's a lack of known reductions that connect problems from these different families or to more general average-case problems. This suggests a fragmented "assumption landscape."
  • The Search for "Non-Mainstream" Constructions: The paper discusses ongoing research into alternative public-key constructions based on less conventional assumptions, such as combinatorial problems or indistinguishability obfuscators, to broaden the foundation of public-key cryptography.

Limitations and Future Work

  • Lack of a Clean Theory of Average-Case Hardness: The authors acknowledge that a comprehensive and predictive theory of average-case hardness is still missing, which hinders our ability to relate the hardness of various problems.
  • Subjectivity in "Similarity" of Assumptions: The paper admits that judging whether two cryptographic assumptions are "similar" or belong to the "same family" is inherently subjective.
  • Open Questions on Structure and Combinatorial Problems: Significant open questions remain regarding whether combinatorial problems can form a robust basis for public-key cryptography and whether current lattice-based schemes can be broken by exploiting their structure.
  • Future Work: The paper implicitly calls for research into:
  • Finding new, diverse, and provably secure assumptions for public-key cryptography.
  • Developing a better theoretical understanding of average-case hardness and its relation to worst-case hardness.
  • Exploring the potential of combinatorial problems and other less structured assumptions for building secure cryptographic primitives.
  • Investigating the implications of quantum computing on the entire landscape of cryptographic assumptions.

Summary updated

BibTeX
@inproceedings{barak2017complexity,
  author = {Boaz Barak},
  title = {{The Complexity of Public-Key Cryptography}},
  booktitle = {Tutorials on the Foundations of Cryptography},
  year = {2017},
  doi = {10.1007/978-3-319-57048-8\_2},
}

Loading related content...

Figure