Bridging Worst-Case and Average-Case Complexity

24 concepts14 papers1 proposal

In theoretical computer science, a problem is traditionally deemed "hard" if it is difficult to solve in the worst case. This means that out of all possible inputs of a given size, there exists at least one pathological instance that causes an algorithm to run slowly or fail.

However, this guarantee is fundamentally inadequate for cryptography. If a security protocol relies on a worst-case hard problem, it only guarantees that some instances are secure. If the protocol randomly generates an instance for a key or a puzzle, it might inadvertently select an easy instance, leaving the system vulnerable. Cryptography requires average-case hardness—a guarantee that almost all instances generated from a specific distribution are computationally intractable.

Bridging this gap requires mathematical frameworks known as worst-case to average-case reductions. If we can prove that an algorithm capable of solving a random instance can be transformed into an algorithm that solves the absolute hardest instance, we can confidently ground real-world security in foundational complexity theory.

The Cryptographic Necessity for Average-Case Hardness

To understand why worst-case hardness fails in practice, consider the foundational tutorial by Jörg Rothe in Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial. Standard complexity classes like NP-hard are defined entirely by the existence of isolated hard instances. If an encryption scheme is built on an NP-hard problem, an adversary encountering a typical, randomly generated instance might easily bypass it because the distribution of instances encountered in practice does not intersect with the pathological worst-case instances.

This discrepancy is not merely theoretical; it regularly breaks real-world cryptographic candidates. For instance, in Sum-of-Squares Meets Program Obfuscation, Revisited, Boaz Barak et al. demonstrated that candidate indistinguishability obfuscation (iO) schemes built on simple quadratic polynomials were fundamentally insecure. Even though the underlying mathematical problems were worst-case NP-hard, the specific random-looking distributions generated by the obfuscation protocols fell into a structural trap that allowed semidefinite programming to efficiently break them.

The core building block of cryptography, the One-Way Function (OWF), exemplifies this tension. A OWF must be easy to compute but hard to invert on average. Lane A. Hemaspaandra et al. explored these structural boundaries in Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory and If P neq NP then some strongly noninvertible functions are invertible. The authors showed that while algebraic features can be proven to exist under the worst-case assumption that $P \neq NP$, these proofs fail to guarantee that the resulting functions maintain their noninvertibility when sampled uniformly on average.

Engineering the Worst-Case to Average-Case Bridge

How do we mathematically prove that average instances inherit worst-case hardness? The most direct method is an explicit reduction that takes a worst-case instance and randomizes it into an average-case instance.

Ronen Shaltiel et al. provided a foundational mechanism for this in If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances. They proved that if an NP language is hard in the worst case, it is possible to efficiently generate a distribution of inputs that causes any specific refutation algorithm to fail. This established a "mild" form of average-case hardness. However, the authors noted that amplifying this mild hardness into "strong" average-case hardness—where an algorithm performs no better than random guessing—remains an open challenge.

To achieve closer alignment, researchers use self-reductions to map instances within the same problem class. Reyad Abed Elrazik et al. advanced this approach in Pseudorandom Self-Reductions for NP-Complete Problems by demonstrating that NP-complete problems can be reduced to distributions that are computationally indistinguishable from uniform random distributions, providing a more granular understanding of how hardness is distributed across instance spaces.

Connecting Cryptography to Natural NP-Complete Problems

For decades, a primary goal of structural complexity has been to find a natural NP-complete problem whose average-case hardness is exactly equivalent to the existence of OWFs. This would mean that if any part of NP is hard on average, cryptography is possible.

Harsha Tirumala et al. achieved a major breakthrough toward this goal in One-Way Functions and a Conditional Variant of MKTP. They focused on the Minimum Conditional KT-complexity Problem (McKTP), which asks whether a string can be compressed under a time-bounded variant of Kolmogorov complexity. The authors proved that McKTP is NP-complete and that its average-case hardness is mathematically equivalent to the existence of logspace-computable OWFs. This explicitly tied the foundational existence of cryptography to the average-case difficulty of a natural problem within the hardest class of NP.

[ Worst-Case Hardness (P ≠ NP) ]
               │
               ▼  (Shaltiel et al. / Elrazik et al.)
[ Mild Average-Case Hardness / Pseudorandom Distributions ]
               │
               ▼  (Tirumala et al. via McKTP)
[ Strong Average-Case Hardness ⇔ Existence of One-Way Functions ]

Fine-Grained Average-Case Hardness and Planted Problems

While traditional complexity theory separates problems coarsely (polynomial vs. exponential time), fine-grained complexity focuses on exact lower bounds within polynomial time—such as proving that a problem requires exactly quadratic ($O(n^2)$) or cubic ($O(n^3)$) time.

To build "fine-grained cryptography" (e.g., protocols secure against adversaries with bounded polynomial resources), worst-case fine-grained bounds must also be translated to the average case. Mina Dalirrooyfard et al. pioneered techniques for this in New Techniques for Proving Fine-Grained Average-Case Hardness and Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More. The authors constructed fine-grained reductions for core problems like Orthogonal Vectors ($k$-OV) and $k$-SUM, proving that these problems remain hard when inputs are sampled from specific distributions.

To make these problems practically useful for protocols, one must be able to generate hard instances with a known solution (a trapdoor or a planted secret). Adam Polak et al. addressed this in The Planted Orthogonal Vectors Problem by engineering a method to plant a solution within a random $k$-OV instance. By ensuring the planting method maintains $(k-1)$-wise independence, the authors created average-case instances that remain immune to known algorithmic shortcuts, providing a concrete candidate for fine-grained cryptographic primitives.

Domain-Specific Gaps and Practical Vulnerabilities

The absence of proven worst-case to average-case reductions creates ongoing security risks across several practical cryptographic domains:

  • Code-Based Cryptography: In post-quantum signature design, Marco Baldi et al. introduced highly efficient signatures in Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem. However, the authors explicitly noted a theoretical gap: while restricted syndrome decoding is proven to be NP-complete in the worst case, the security of their practical signature scheme relies on the unproven assumption that random instances consistently maintain this hardness.
  • Memory-Hard Functions: Memory-hard functions (used in password hashing) rely on the difficulty of finding optimal graph pebbling strategies to force an attacker to use significant memory. Jeremiah Blocki et al. proved in On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling and Approximating Cumulative Pebbling Cost is Unique Games Hard that calculating or even approximating cumulative pebbling costs is hard in the worst case. Yet, the authors emphasize that because real-world hashing applies to specific graph distributions, understanding how these approximation challenges persist in the average case remains an essential open question.
  • Isomorphism-Based Cryptography: When designing post-quantum primitives from group actions, Zhengfeng Ji et al. showed in General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography that many average-case isomorphism problems are easily reducible to simpler cases. They introduced the Pseudorandom Group Action assumption to act as a structural "bottleneck problem," ensuring that average-case instances cannot be simplified by an attacker.

Ultimately, bridging the gap between worst-case and average-case complexity is what allows theoretical hardness to function as a reliable shield in practical applications. By constructing rigorous reductions and identifying average-case complete problems, researchers continue to turn worst-case mathematical anomalies into dependable cryptographic guarantees.

Key Foundational Work

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory (2005) — contributed 3 concept elements to this direction.
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial (2001) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_average_case_hardness_gap_69888e34,
  title = {average-case hardness gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/average-case-hardness-gap/rdr_69888e34605648a0ae8961825371b838},
  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_average_case_hardness_gap_69888e34_v1,
  title = {average-case hardness gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/average-case-hardness-gap/rdr_69888e34605648a0ae8961825371b838/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake