Post-quantum cryptography: a survey of foundations, standards, and security assumptions

Abstract

Post-quantum cryptography (PQC) replaces public-key constructions threatened by large quantum computers with algorithms intended to resist both classical and quantum attacks. The central question is now broader than which mathematical problems appear hard: which standardized primitives can be composed, implemented, and maintained as trustworthy systems? This survey connects the quantum threat model to lattice-based, code-based, and hash-based constructions; compares the finalized NIST algorithms; and examines what security reductions, parameter categories, and cryptanalysis actually establish. Its main finding is that algorithm selection is a portfolio decision constrained by protocol role, security assumptions, message size, and implementation risk. ML-KEM, ML-DSA, and SLH-DSA provide concrete starting points, while diversification and continuing analysis remain essential. Migration and protocol integration are examined in the companion survey.

Reading this survey. Standards and source status were checked on September 5, 2026. Sizes below come from published specifications; this article reports no new benchmarks or cryptanalytic experiments. “Quantum-resistant” expresses a security assessment under stated assumptions, not a proof against every future algorithm.

1. Scope and review method

This is a focused narrative survey, organized around four questions: what changes in the attacker model; how the leading constructions work; which tradeoffs distinguish standardized choices; and what evidence should guide deployment? The audience is engineers and researchers who understand public and private keys but need a bridge between mathematical descriptions and system decisions.

The literature search prioritized NIST publications, IETF documents, original scheme specifications, and original attack papers. Searches covered the standardized algorithm names, their predecessor designs, hybrid key establishment, implementation attacks, and migration guidance. Sources were followed backward to foundational work and forward to current standards pages. Final specifications take precedence over submission-era names and sizes; current publisher records determine whether a document is final, draft, or superseded. Vendor rankings and quantum-arrival predictions were excluded from the comparative evidence.

The result is deliberately selective. It is not a systematic review with an exhaustive database search or a meta-analysis of performance studies. Quantum error correction, quantum key distribution hardware, zero-knowledge proof systems, and a complete catalog of signature candidates are outside scope. Bernstein and Lange’s overview supplies a useful historical framing: preserving usability and confidence is as central as identifying new mathematical assumptions. [1]

2. The threat changes unevenly

2.1 Shor: public-key assumptions fail structurally

Shor’s algorithms solve integer factorization and discrete logarithms in polynomial time on an appropriate quantum computer. That threatens the assumptions underlying RSA and finite-field Diffie–Hellman, with the discrete-logarithm approach also motivating the replacement of elliptic-curve systems. Increasing an RSA modulus is therefore a different kind of response from replacing the underlying assumption: it raises concrete cost without removing the asymptotic vulnerability. [2]

The relevant machine is a cryptographically relevant quantum computer, capable of executing an attack at the scale and reliability required by the target. A laboratory qubit count is not itself a cryptanalytic capability. This survey assigns no calendar date to that machine. A defensible migration argument can instead start from information lifetime and replacement lead time.

2.2 Grover: generic search improves, but not in the same way

Grover’s algorithm reduces generic search over an unstructured space of size N to order √N oracle queries. For a uniform k-bit key search, the idealized query expression becomes order 2^k/2. This is a query-complexity statement: reversible implementation, circuit depth, error correction, and parallelization affect the resources of a real attack. It should not be presented as an unconditional wall-clock estimate or as “all cryptography is broken.” [3]

Consequently, public-key replacement and symmetric-parameter review are separate workstreams. Neither a longer symmetric key nor a stronger hash repairs a vulnerable public-key exchange that exposes the symmetric key. Conversely, replacing RSA does not eliminate nonce misuse, weak randomness, or endpoint compromise.

2.3 Why migration can be urgent without a quantum deadline

Mosca’s migration framing compares the confidentiality lifetime of data, the time needed to move systems, and the time until an adversary gains the relevant capability. A simple planning expression is:

T_secrecy + T_migration > T_quantum

When that inequality holds, waiting until the quantum computer exists leaves an exposure window. An adversary can record vulnerable encrypted exchanges today and attempt decryption later. The expression is a risk heuristic, not a probability distribution or a prediction. Its value is that uncertainty about the right-hand side does not erase the two lead times on the left. [4]

3. Separate the cryptographic jobs

A key-encapsulation mechanism (KEM) establishes shared secret material. Its abstract interface consists of key generation, encapsulation, and decapsulation:

(ek, dk) ← KeyGen()
(K, c) ← Encaps(ek)
K′ ← Decaps(dk, c)

The public encapsulation key is ek; the private decapsulation key is dk; c is the ciphertext. For correctly generated inputs, both parties should obtain the same secret, except for any permitted negligible failure probability. A protocol then uses appropriate key derivation and authenticated symmetric encryption. The KEM does not by itself establish the identity of the peer. NIST SP 800-227 treats authentication, key confirmation, and secret-key usage as additional parts of secure key establishment. [5]

A digital signature answers a different question: does a verification key validate a signature on a particular message? An unforgeability claim typically considers an attacker that has already obtained signatures on chosen messages. Verification still needs an authenticated association between the public key and its owner. A valid signature from an attacker-controlled key establishes no trusted identity.

Table 1. Distinct jobs in a secure system
Role	Typical component	What remains outside it
Establish secret material	KEM such as ML-KEM	Peer authentication and application policy
Authenticate a message	Signature such as ML-DSA	Trust in the verification key; replay policy
Protect application bytes	Authenticated symmetric encryption	Key establishment, nonce discipline, endpoint safety
Distribute trust	Certificates and trust stores	Issuance, revocation, updates, and lifecycle decisions

This separation prevents a frequent category error: comparing an ML-KEM ciphertext with an ML-DSA signature as though they were competing encodings of the same operation. The meaningful comparison is within a role and at an explicitly stated security target.

4. Lattices: structured arithmetic with carefully controlled noise

4.1 From linear equations to Module-LWE

A useful starting model is a public system of noisy linear equations:

t = A s + e (mod q)

If the error e disappeared, ordinary linear algebra could reveal the secret s under suitable conditions. Carefully chosen noise turns recovery and distinguishing problems into cryptographic assumptions. Module constructions organize entries as polynomials and perform arithmetic over a specified ring. Structure makes representations and multiplication efficient, while also defining the precise problem whose hardness must be studied.

The Kyber specification illustrates the design: polynomial vectors, bounded noise, compression, and fast polynomial arithmetic combine to make key establishment practical. The intuition above is not the complete encryption scheme or its proof. Concrete security also depends on the distribution, dimensions, modulus, attack models, and parameters; a generic statement that “lattices are hard” does not settle those choices. [6]

4.2 ML-KEM is the standardized object

FIPS 203 specifies ML-KEM, derived from CRYSTALS-Kyber, with three parameter sets. Its public-key encryption component is embedded inside a KEM construction with validity checks and ciphertext re-encryption during decapsulation. On a ciphertext mismatch, implicit rejection selects alternative secret material instead of exposing the decrypted candidate. Exact byte encodings and checks matter: a tutorial implementation of the noisy equation is not ML-KEM, and a submission-era Kyber implementation should not be assumed interchangeable with the final standard. [7]

4.3 ML-DSA: proving knowledge without leaking the signing key

Dilithium, the predecessor of ML-DSA, uses a Fiat–Shamir-with-aborts design. At a high level, the signer commits using a fresh masking value, derives a challenge from a hash, and produces a response involving the secret. Rejection conditions prevent the response distribution from revealing too much about that secret. Rounding and hints reduce the data a verifier needs. Removing rejection sampling as a performance optimization would alter the security argument rather than merely speed up an implementation. [8]

FIPS 204 defines ML-DSA-44, ML-DSA-65, and ML-DSA-87, along with the external signing and verification interfaces. Applications must agree on context and message processing, including whether a standardized prehash interface is in use. The predecessor paper explains the construction; the final specification governs interoperable implementations. [9]

4.4 What a reduction does and does not prove

A security reduction connects a successful adversary against a construction to a solver for an underlying problem, under a specified model. It supplies a disciplined conditional argument. It does not establish an unconditional lower bound on every attack against concrete parameters, and it does not prove that compiled machine code has no leakage. Treat the theorem, concrete attack estimates, and implementation assessment as complementary evidence. Conflating them turns a qualified result into a stronger claim than the literature supports.

5. Hash-based signatures: another assumption, another cost profile

Hash-based signatures build authentication from carefully arranged hash evaluations. The SPHINCS+ framework combines a few-time signature construction, FORS, with a hypertree of Merkle trees and one-time signatures. Authentication paths connect message-level evidence to a compact public root. Its stateless design avoids requiring the application to maintain a single monotonically advancing signing index across every signing operation. This removes a difficult operational dependency, while increasing the amount of signature material and computation. [10]

FIPS 205 standardizes SLH-DSA with SHA-2 and SHAKE variants. The s and f parameter families make different size–speed tradeoffs. Their small public keys do not imply small signatures. “Based on hashes” also does not reduce the security argument to one generic collision-resistance claim: the construction uses several domain-separated functions and specific security properties. [11]

Stateful schemes are a separate option. NIST SP 800-208 specifies LMS/HSS and XMSS variants. Their operational contract includes preserving signing state so that one-time key material is not reused. Backups, replicas, failover, and snapshot restoration must respect that contract. A firmware-signing service with tightly controlled key hardware may have a different fit from a replicated general-purpose signing service. Algorithm choice therefore reaches into system architecture. [12]

6. Codes and the wider research portfolio

Code-based cryptography uses the difficulty of decoding appropriately constructed error patterns without the secret structure needed by the legitimate party. HQC is a code-based KEM whose stated assumption concerns quasi-cyclic syndrome decoding. Its appeal in a portfolio is the use of a different mathematical foundation from Module-LWE, rather than a claim that it wins every performance comparison. [13]

NIST’s fourth-round report selected HQC for standardization after considering BIKE, Classic McEliece, HQC, and SIKE. The report is useful precisely because it evaluates more than one axis: security confidence, performance, suitability, and portfolio needs all shape a standardization decision. A construction can remain scientifically important without being the selected deployment standard. [14]

The wider signature landscape includes multivariate constructions and proof-based approaches that turn knowledge of a secret into a noninteractive signature. These families deserve continued analysis, but a research taxonomy should not imply equal maturity. NIST’s additional-signature process seeks alternative assumptions and useful performance profiles; advancement in that process is not a final standard. [15]

The evidence supports specific diversification. Two implementations sharing the same vulnerable arithmetic code may not provide much implementation diversity. Two schemes built around related structured assumptions may not provide the mathematical diversity an operator intended. A portfolio should state which failure modes its components are expected to avoid sharing.

7. Standards snapshot: September 5, 2026

Table 2. Final standards and continuing standardization
Construction	Role / foundation	Verified status
ML-KEM	KEM / module lattices	FIPS 203, final August 13, 2024
ML-DSA	Signature / module lattices	FIPS 204, final August 13, 2024
SLH-DSA	Signature / hashes	FIPS 205, final August 13, 2024
Falcon / FN-DSA	Signature / NTRU lattices	Selected; ongoing standardization
HQC	KEM / codes	Selected; ongoing standardization

NIST’s current project overview identifies the first three as the principal published standards and Falcon and HQC as continuing standardization work. This survey consequently does not present five finalized NIST PQC standards. Selection, draft publication, finalization, implementation support, and module validation are different milestones. [16]

8. Compare sizes before making performance claims

Table 3. ML-KEM serialized sizes, bytes. FIPS 203, Table 3.
Parameter set	Public key	Private key	Ciphertext	Shared secret
ML-KEM-512	800	1,632	768	32
ML-KEM-768	1,184	2,400	1,088	32
ML-KEM-1024	1,568	3,168	1,568	32

These are algorithm encodings, not complete protocol messages or total runtime memory. The equal shared-secret length does not make the parameter sets equivalent in security. [7]

Table 4. Signature sizes, bytes. FIPS 204, Table 2; FIPS 205, Table 2. SLH-DSA rows apply to both SHA2 and SHAKE.
Parameter set	NIST category	Public key	Signature
ML-DSA-44	2	1,312	2,420
ML-DSA-65	3	1,952	3,309
ML-DSA-87	5	2,592	4,627
SLH-DSA-128s	1	32	7,856
SLH-DSA-128f	1	32	17,088
SLH-DSA-192s	3	48	16,224
SLH-DSA-192f	3	48	35,664
SLH-DSA-256s	5	64	29,792
SLH-DSA-256f	5	64	49,856

NIST categories compare attack costs with specified symmetric reference problems; they are not measurements of actual quantum attack time. Category 2 and category 1 rows should not be silently treated as an equal-security contest. Even at the same category, signature size alone does not determine signing throughput, verification latency, memory, or energy. [9] [11]

9. What failures teach us

Castryck and Decru’s SIDH attack exploited information supplied by the protocol, notably torsion-point images. It broke the security of the SIDH construction underlying SIKE using classical computation. This is evidence against that construction, not a proof that every isogeny-based proposal is broken. The general lesson is to analyze the full public transcript rather than infer security from the apparent difficulty of an isolated mathematical task. [17]

KyberSlash demonstrates a different failure class: secret-dependent division timing in implementations. The authors reported key recovery on the studied platforms and coordinated patches. That finding concerns how code exposes secrets; it does not establish a mathematical break of Module-LWE. The two cases belong in different columns of a security review, because changing an implementation and replacing an algorithm are different responses. [18]

There is also a current portfolio update. NIST states that HAWK was withdrawn after a vulnerability announced on July 28, 2026, and that the finding does not affect its finalized PQC standards. This is a source-attributed status report, not an independent reproduction of the attack. It reinforces the value of continuing public evaluation while resisting the unsupported leap from one candidate’s failure to a failure of an entire family. [19]

10. Synthesis and open research questions

Across these constructions, four tensions recur. Compact representations can require more structured assumptions. Small public keys can accompany large signatures. Strong mathematical evidence can coexist with vulnerable machine code. A published standard can still require substantial protocol and lifecycle work before a system gains the intended property.

Research remains valuable where it reduces those tensions: better concrete attack estimates; tighter and more applicable reductions; implementation verification that survives compiler and platform changes; practical signatures under different assumptions; and reproducible comparisons that report network and lifecycle costs alongside primitive timings. Constrained devices also need studies that include stack usage, persistent storage, update paths, and energy rather than importing server-class results.

The engineering conclusion is specific. Start with the cryptographic role and threat model, choose among relevant finalized standards, inspect the complete implementation and protocol contract, and retain a way to replace the choice. Treat mathematical diversity as a resource to evaluate, and treat every performance claim as dependent on its measurement setup. The second survey follows that argument through hybrid TLS, certificate and firmware dependencies, migration evidence, and operational testing.

References

Sources checked September 5, 2026. Numbered citations link directly to the corresponding publication. Word count excludes this reference list.