Foundations of Average Case Hardness for Cryptography

This direction is split into other directions: average-case hardness gap. Its last version stays readable and citable here.

Version 1 of 121 papers32 conceptsfrozen 2026-10-04

In theoretical computer science, we often classify problems by their "worst-case" difficulty. If a problem is NP-complete, we know that at least one instance of that problem is incredibly hard to solve. However, for a cryptographer, worst-case hardness is a fragile shield. If a digital signature scheme is based on a problem that is hard only in the worst case, an attacker might find that 99% of the keys generated are actually easy to crack.

The central challenge in modern cryptography is bridging the gap between worst-case hardness (it’s hard for someone, somewhere) and average-case hardness (it’s hard for everyone, almost always).

The Worst-Case Average-Case Gap

Standard complexity theory, as noted by Jörg Rothe in Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial, evaluates difficulty based on the existence of any hard instances. Cryptography, however, requires that nearly all instances are difficult. This distinction is not merely academic; it is the difference between a theoretical proof of security and a system that survives a real-world attack.

As Jörg Rothe and Lane A. Hemaspaandra explore in Characterizations of the Existence of Partial and Total One-Way Permutations, establishing a formal link between these two domains remains one of the most fundamental unsolved problems in the field. Without this link, we cannot be certain that the "one-way functions" we use to encrypt data are truly one-way for the average user.

Why Lattices are Special

One of the most successful bridges built across this gap involves lattice-based cryptography. In his tutorial, Jörg Rothe highlights that lattice problems are unique because they offer worst-case to average-case reductions. This means we can mathematically prove that if you can solve a random instance of a lattice problem (average case), you can solve any instance of that problem (worst case). This property makes lattice-based systems exceptionally robust candidates for post-quantum security.

The Challenge in Post-Quantum Candidates

As we move toward new cryptographic standards, other mathematical structures are being scrutinized for similar gaps.

  1. Code-Based Cryptography: In Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem, Marco Baldi and Antonia Wachter-Zeh introduce the Restricted Syndrome Decoding Problem (R-SDP). While R-SDP is NP-complete in the worst case, the authors acknowledge a persistent theoretical gap: we lack formal proofs that random instances used in signatures maintain that same level of security.
  2. Isogeny-Based Cryptography: This field uses the paths between elliptic curves as cryptographic puzzles. Kristin E. Lauter and Ludovic Perret have recently worked toward Unconditional foundations for supersingular isogeny-based cryptography. Their work aims to prove that if these problems are hard in the worst case, they are hard on average, specifically to support schemes like SQIsign.
  3. The Danger of Structure: Sometimes, specific instances are unexpectedly easy. The paper Supersingular Curves With Small Non-integer Endomorphisms demonstrates that certain elliptic curves (M-small curves) cluster in "isogeny valleys" that make them vulnerable to specialized attacks. This illustrates the danger of the gap: if we don't understand the average-case landscape, we might accidentally pick a "weak" starting point.

Hardness as a Resource

The broader impact of this research direction is best summarized by the career of Avi Wigderson. As detailed by Boaz Barak and Salil P. Vadhan in On the works of Avi Wigderson, Wigderson helped reshape our understanding of computational hardness. He viewed hardness not just as a limitation, but as a resource—a substitute for randomness that allows for secure communication.

Understanding the transition from worst-case complexity to average-case security is not just about patching holes; it is about building a rigorous science of cryptography where security is a proven property of the mathematical landscape, rather than a hopeful assumption.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_foundations_of_average_case_hardness_for_bdd07107,
  title = {Foundations of Average Case Hardness for Cryptography},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/foundations-of-average-case-hardness-for-cryptography/rdr_bdd07107baf443e993cadf65948ffaae},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_foundations_of_average_case_hardness_for_bdd07107_v1,
  title = {Foundations of Average Case Hardness for Cryptography},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/foundations-of-average-case-hardness-for-cryptography/rdr_bdd07107baf443e993cadf65948ffaae/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}