Computational Hardness Assumptions

Computational hardness assumptions are the unproven but well-studied conjectures — such as the difficulty of factoring, discrete logarithms, and lattice problems — on which the security of cryptographic schemes ultimately rests.

Definition

A computational hardness assumption is a conjecture that a particular computational problem cannot be solved efficiently (in polynomial time) by any realistic adversary, serving as the foundation on which provable security is built.

Scope

This topic covers the assumptions cryptography relies on: the existence of one-way functions, number-theoretic problems (factoring, RSA, discrete logarithm), and the lattice and code problems used in post-quantum cryptography. It addresses the hierarchy among assumptions, the distinction between worst-case and average-case hardness, and how assumptions are vetted. It excludes the reduction machinery that connects assumptions to schemes and the security definitions themselves, treated in sibling topics.

Core questions

• Why must cryptographic security rest on unproven hardness assumptions?
• What are the major assumptions (one-way functions, factoring, discrete log, lattices)?
• How do assumptions relate to one another in strength?
• What is the difference between worst-case and average-case hardness?
• How are candidate hard problems vetted, and what happens when one falls?

Key concepts

• one-way function
• trapdoor function
• integer factorization assumption
• discrete logarithm assumption
• RSA and Diffie-Hellman assumptions
• learning with errors (LWE)
• worst-case vs average-case hardness
• P versus NP
• assumption hierarchy

Key theories

One-way functions as a minimal assumption

The existence of one-way functions — easy to compute, hard to invert — is necessary and sufficient for much of symmetric cryptography and is the most basic assumption; nearly all of cryptography presupposes at least this.

Number-theoretic and lattice assumptions

Public-key cryptography rests on structured problems — integer factoring, the RSA problem, and discrete logarithms (classically), and learning-with-errors and shortest-vector problems in lattices (post-quantum) — each supported by decades of cryptanalytic scrutiny.

Mechanisms

Cryptography needs problems that are hard on average (over random instances), not merely in the worst case, since keys are chosen randomly. Assumptions are organized into a rough hierarchy: a break of a weaker assumption (e.g., factoring) often breaks schemes built on it, while reductions relate assumptions to one another. Lattice assumptions are notable for worst-case to average-case reductions, giving stronger confidence. Confidence in any assumption comes from sustained, failed cryptanalytic effort rather than proof.

Clinical relevance

Hardness assumptions determine what is and is not safe to deploy. The discovery that quantum computers would break factoring and discrete logarithms (via Shor's algorithm) invalidated the assumptions behind RSA and elliptic-curve cryptography against quantum adversaries, directly driving the move to lattice-based post-quantum standards. Choosing schemes built on well-studied assumptions, and tracking their status, is essential to long-term security.

Evidence & guidelines

Standards bodies favor assumptions with long cryptanalytic track records; NIST's post-quantum process explicitly evaluated the maturity and confidence of the underlying lattice, code, and hash assumptions. Best practice avoids exotic or newly proposed assumptions for high-assurance systems and prefers conservative, well-vetted problems, with key sizes set against the best known attacks.

History

The reliance on hardness emerged with public-key cryptography in 1976, when Diffie and Hellman tied security to the discrete logarithm, and RSA to factoring. The 1980s formalized one-way functions and the worst-case/average-case distinction. Ajtai's worst-case to average-case reductions (1996) and Regev's learning-with-errors problem (2005) established lattice assumptions, which gained prominence as quantum-resistant foundations and underpin the new post-quantum standards.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

Why can't we just prove these problems are hard?

Proving a problem requires super-polynomial time would resolve deep open questions in complexity theory (most notably P versus NP), which remain unsolved. So cryptography relies on assumptions whose plausibility comes from decades of unsuccessful attempts to solve them efficiently.

What happens if a hardness assumption is broken?

Every scheme whose security reduces to that assumption becomes potentially insecure and must be replaced. This is why the quantum threat to factoring and discrete logarithms prompted a global migration to schemes based on different, quantum-resistant assumptions.