The Complexity of Public-Key Cryptography

Boaz BarakTutorials on the Foundations of Cryptography 2017 · OpenReview

TL;DR

This paper surveys the foundational assumptions behind public-key cryptography, questioning the evidence for their hardness and exploring alternative constructions. It argues that our current understanding of public-key security might be more fragile than commonly assumed, particularly in light of quantum computing and the limited diversity of underlying hard problems.

What Problem Does This Paper Address?

Public-key cryptography, a cornerstone of modern digital security, relies on the assumption that certain mathematical problems are computationally hard to solve. Historically, these problems have largely fallen into two categories: those based on algebraic structures (like factoring and discrete logarithms) and those based on geometric structures (like lattices and coding theory). This paper delves into the evidence supporting the hardness of these assumptions, particularly in the face of advancements like Shor's algorithm for quantum computers. It questions whether our reliance on a narrow set of problems makes public-key cryptography inherently vulnerable and explores the implications of this reliance for the field's future. The author aims to provoke discussion about the "assumption landscape" of cryptography, moving beyond just mathematical proofs to consider the broader scientific and philosophical underpinnings.

Methods

The paper adopts a survey and discussion-oriented approach rather than presenting new algorithms or empirical results. It systematically reviews:

  • Candidate Constructions: It examines various proposed schemes for one-way functions and public-key encryption, categorizing them into "algebraic" (group-theoretic) and "geometric" (lattice/coding-based) families.
  • Hardness Assumptions: It discusses the specific computational problems that underpin these schemes, such as integer factoring, discrete logarithms, learning with errors (LWE), and planted problems.
  • Evidence for Hardness: The author critically assesses the evidence for the hardness of these assumptions, considering both classical and quantum algorithms, and the lack of definitive proofs of hardness.
  • Alternative Constructions: It explores less mainstream proposals for public-key cryptography, aiming to determine if they offer genuinely different foundations.
  • Theoretical Frameworks: The paper references theoretical frameworks like Impagliazzo's "worlds" to contextualize the current state of cryptographic assumptions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Fragile Foundations: Despite their widespread use, the core assumptions underpinning public-key cryptography (like factoring and discrete logarithms) lack strong evidence of hardness, especially against quantum computers.
  • Limited Diversity: The field heavily relies on a small number of problem families. If these fail, there are few truly distinct alternatives, raising concerns about the robustness of public-key cryptography.
  • The "Crisis" in Public-Key Cryptography: The author suggests a potential "crisis" due to the limited diversity of assumptions and the looming threat of quantum computing, urging a re-evaluation of our foundational beliefs.
  • LWE as a Central Pillar: The Learning With Errors (LWE) problem has emerged as a crucial assumption, underpinning many advanced cryptographic primitives, but its minimal nature and relationship to other problems are still under investigation.
  • The Role of Structure: The paper explores the idea that computational problems are presumed hard unless they have a "structural reason" to be easy, hinting at a more principled way to understand hardness beyond brute-force attacks.
  • Subjectivity in Cryptography: The author acknowledges that judging the similarity or difference between cryptographic assumptions and schemes involves a degree of subjectivity, making definitive classifications challenging.

Key Results

The paper does not present new quantitative results but rather synthesizes existing knowledge and theoretical arguments. Its key "results" are conceptual:

  • Identification of a Limited Assumption Landscape: It clearly delineates the two main families of public-key cryptosystems and highlights the scarcity of truly independent foundational assumptions.
  • Questioning Existing Evidence: It systematically points out the lack of definitive proof for the hardness of commonly used problems, emphasizing the impact of quantum algorithms.
  • Highlighting LWE's Prominence: It underscores the growing importance of the LWE assumption as a versatile foundation for modern cryptography.
  • Proposing a Research Agenda: The paper implicitly outlines future research directions by posing open questions about alternative constructions and the nature of computational hardness.

Limitations and Future Work

  • Subjectivity: The author explicitly states that many of the judgments made in the paper are subjective, particularly regarding the similarity of assumptions and the definition of "families" of cryptosystems.
  • Lack of Definitive Proofs: The paper emphasizes that for many of the discussed problems, there is no proof of hardness, only a lack of known efficient algorithms. This leaves room for future breakthroughs that could undermine current security.
  • Future Work: The paper strongly suggests the need for:
  • Exploring and validating alternative public-key constructions that are based on fundamentally different assumptions.
  • Developing a deeper theoretical understanding of why certain problems are hard, potentially leading to more robust security guarantees.
  • Investigating the relationship between different hardness assumptions and the possibility of reducing public-key cryptography to simpler primitives.
  • Understanding the implications of quantum computing for the entire landscape of cryptographic assumptions.

Summary updated

Abstract

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for publickey encryption schemes, and the types of evidence we have for the veracity of these assumptions.
BibTeX
@article{barak2017complexity,
  author = {Boaz Barak},
  title = {{The Complexity of Public-Key Cryptography}},
  journal = {Tutorials on the Foundations of Cryptography},
  year = {2017},
  url = {https://openreview.net/forum?id=OniJpM2iJX},
}
Figure