Post-Quantum Cryptography: Theoretical Foundations and Reconceptualisation

The Quantum Threat to Public-Key Cryptography

RSA, ECDH, DSA. All three depend on problems that a fault-tolerant quantum computer solves in polynomial time. Shor’s algorithm does not gradually weaken these schemes or shave bits off their security margins; it annihilates them outright [3]. The result is not gradual degradation. It is categorical collapse to plaintext-equivalent exposure.

When does this actually happen? Nobody agrees. A decade, perhaps several; the estimates keep shifting and the confidence intervals remain embarrassingly wide. But focusing on arrival timelines misframes the problem entirely. “Harvest now, decrypt later” inverts the chronology. Adversaries are already collecting encrypted traffic, warehousing it for the day a sufficiently large machine can strip the ciphertext bare [4]. State secrets with 50-year classification windows, genomic records that remain sensitive for a patient’s lifetime, infrastructure blueprints for systems that will operate for decades: for these categories of data, the migration deadline has quietly passed while the industry was still debating timelines.

Mosca’s Inequality: If the time to migrate (T) plus the data sensitivity lifetime (D) exceeds the time until quantum capability arrives (Q), then the data is already at risk. $D + T > Q$ implies immediate action is required [3].

Symmetric Cryptography: A Relative Safe Harbour

Grover’s algorithm provides a quadratic speedup for unstructured search, which in the brute-force model halves the effective bit-security of symmetric keys. AES-256, under this model, retains roughly 128 bits of security against a quantum adversary. That is still computationally infeasible. The precise cost depends on assumptions about Grover oracle depth, error correction overhead on actual quantum hardware, and parallelisation constraints, all of which remain open research questions [3]. But the practical conclusion is clear enough: worry about your public-key infrastructure first. Symmetric encryption is not the critical vulnerability here.

The Four PQC Algorithm Families

Post-quantum cryptography replaces the mathematical problems that Shor’s algorithm breaks with alternatives believed to resist both classical and quantum attack. Four algorithm families have emerged as serious contenders, though their maturity varies enormously [3] [4].

Lattice-Based Cryptography

Lattice problem

Finding the shortest or closest vector in a high-dimensional lattice. The Learning With Errors (LWE) and Module-LWE variants underpin CRYSTALS-Kyber (key encapsulation) and CRYSTALS-Dilithium (digital signatures).

Lattice schemes are the pragmatist’s choice. Among PQC families, they come closest to drop-in replacements for classical public-key cryptography: encryption, key exchange, digital signatures, all on commodity hardware with key sizes that are larger than RSA/ECC equivalents but not cripplingly so. NIST selected CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium as one of three standardised signature algorithms [4].

The key size increase is real but manageable: a Kyber-768 public key weighs in at 1,184 bytes versus 64 bytes for ECDH P-256. Does that matter? Context decides. For a TLS handshake on a modern server, the overhead vanishes into noise. For a constrained IoT sensor transmitting over a low-bandwidth radio link at 250 kbps, every byte counts. The deeper concern is that lattice security proofs rely on worst-case to average-case reductions whose tightness is still debated. The schemes work, the implementations are fast, but the theoretical guarantees are not as airtight as we might like.

Here is something none of the surveyed papers say directly, but that anyone working on migration planning will encounter: the lattice monoculture problem is not just a cryptanalytic risk. It is a supply-chain risk. Every PQC library, every hardware security module vendor, every TLS stack integrator is converging on the same Module-LWE assumption. If that assumption weakens even partially (not a full break, just a meaningful reduction in concrete security), the remediation would need to propagate through every layer of the software stack simultaneously. We have seen what single-point-of-failure dependency looks like in software supply chains. Applying the same pattern to cryptographic foundations should make us uncomfortable.

Code-Based Cryptography

Code-based scheme

Built on the hardness of decoding random linear error-correcting codes. The McEliece cryptosystem (1978) is the oldest PQC candidate, and newer variants like HQC and BIKE use structured codes for improved efficiency.

Code-based schemes own the longest track record in PQC. McEliece has survived over 45 years of sustained cryptanalytic assault (more than any lattice construction can claim, and considerably more than most cryptographers’ careers). The penalty? Key size. A McEliece public key occupies roughly 1 MB, rendering it impractical for most communication protocols [3]. Newer code-based designs (HQC, BIKE) use structured codes to shrink keys substantially, but they trade the well-studied random-code hardness assumption for algebraic structure that could, in theory, be exploited.

He et al. tackle the hardware side of this problem [1]. Their two sparse polynomial multiplication accelerators for HQC and BIKE achieve 56.84% and 80.25% lower area-delay product (ADP) than previous designs, which matters if code-based PQC is ever going to run on anything smaller than a server rack.

Hash-Based Signatures

Hash-based signature

Digital signatures constructed from hash function properties alone. SPHINCS+ (now SLH-DSA) relies only on the collision resistance and pre-image resistance of hash functions, making it the most conservative security assumption in PQC.

Hash-based signatures occupy the conservative extreme. No exotic algebra, no lattice assumptions, no structured codes. Their security reduces entirely to hash function properties (collision resistance, pre-image resistance), which cryptographers have stress-tested for decades and which survive Grover’s speedup when output lengths are doubled. NIST selected SPHINCS+ (now SLH-DSA) as one of three standardised signature algorithms [4].

The trade-off is brutal, not subtle. SPHINCS+-256s signatures balloon to 49 KB, and signing lags behind lattice alternatives by a wide margin. Worth it? For root-of-trust certificate signing and firmware attestation, where assumption strength trumps throughput: absolutely. For high-throughput TLS connections handling thousands of handshakes per second: almost certainly not.

Multivariate Cryptography

Multivariate scheme

Based on the hardness of solving systems of multivariate polynomial equations over finite fields. Rainbow was a NIST finalist before being broken by a classical attack in 2022.

The Rainbow break deserves attention because of what it reveals about the maturity of PQC as a field. Rainbow was a NIST Round 3 finalist, meaning it had survived multiple rounds of public evaluation by the international cryptographic community. Then Ward Beullens published an attack that recovered Rainbow secret keys “over the weekend on a laptop” [5] [4]. Not with a quantum computer. With classical cryptanalysis. The Rainbow team acknowledged the attack and proposed moving to larger parameters, but the damage was done; NIST eliminated the scheme before final selection.

SIKE (Supersingular Isogeny Key Encapsulation) collapsed even more dramatically. Castryck and Decru broke it “in about one hour on a single core” [4] by exploiting torsion-point information in the SIDH protocol, building on a theorem by Kani from 1997. The technical mechanism (a genus-2 Richelot isogeny construction) is less important than the implication: a mathematical observation from over two decades earlier, sitting in the literature unnoticed, contained the seed of a complete break.

What should practitioners take from this? Two things. First: PQC algorithms are young, and the mathematical bedrock beneath them has received far less adversarial punishment than RSA’s integer factorisation (which withstood four decades of concentrated effort by the world’s best number theorists). Second: building systems that can swap algorithms without a full redesign is not a nice-to-have. It is a survival requirement.

I will state something blunter than the papers do. The SIKE break should have been a field-wide wake-up call about the limits of competition-based cryptographic assurance. NIST’s process is rigorous, but it evaluates submitted candidates against known attack techniques. It does not, and cannot, guarantee that a theorem from 1997 will not resurface as a complete break in 2022. The fact that the Kani theorem sat in the literature for 25 years before anyone connected it to SIDH is not an anomaly; it is a structural feature of mathematics. Results migrate across subfields unpredictably. Any security model that assumes “extensively evaluated” equals “safe” has already been falsified by SIKE.

Hardware Acceleration for Code-Based PQC

The practical viability of code-based PQC depends heavily on efficient hardware implementation. He et al. identify sparse polynomial multiplication as the computational bottleneck for HQC and BIKE [1]. NIST selected HQC for standardisation in March 2025; BIKE was not selected.

Their contribution is twofold:

1. Parallel Segment-based Accumulation (PSA): Decomposes sparse polynomial multiplication into segment-level operations that can be parallelised across FPGA resources. The memory-based implementation achieves high throughput using block RAM for intermediate storage.

2. Permutating-with-Power (PWP): A memory-free alternative that eliminates block RAM dependency entirely, enabling deployment on FPGAs where RAM resources are reserved for other functions. Despite the constraint, PWP achieves even better ADP than PSA.

Both designs are generic across all HQC and BIKE security levels (128, 192, 256-bit equivalent), providing a reusable hardware primitive for the code-based PQC family.

Practical Significance

With NIST’s March 2025 selection of HQC for standardisation, accelerators like these move from speculative to directly relevant. They become the implementation foundation for embedded systems, IoT gateways, and network appliances where software-only PQC performance is often insufficient. The gap between what software can deliver and what constrained environments demand is exactly where FPGA acceleration earns its complexity cost.

Hybrid QC/PQC: Defence in Depth, or Wishful Layering?

Kavitha et al. propose combining quantum key distribution (QKD) with PQC encryption as a defence-in-depth strategy [2]. The logic is appealing: QKD provides information-theoretic security grounded in physics, while PQC provides computational security on classical infrastructure. An attacker who needs to break both faces a higher bar than either defence alone.

A caveat is warranted here. The Kavitha et al. proposal is conceptual. No prototype was built, no simulation was run, no performance data was collected. The architecture is plausible but entirely unvalidated, and no formal security model exists to prove that the combination actually provides strictly greater security than either component in isolation. The argument that “two layers must be better than one” sounds intuitive, but intuition is not proof.

Where Hybrid Might Make Sense

Despite the thin evidence base, the use cases with the strongest rationale are narrow and specific:

• Government and military communications where “harvest now, decrypt later” threats are existential and budgets can absorb quantum hardware costs
• Financial infrastructure where transaction integrity carries multi-decade legal significance
• Critical national infrastructure (power grids, telecommunications backbone) where compromise triggers cascading physical consequences

For typical enterprise applications, PQC alone is sufficient and far more practical. The hybrid approach adds engineering complexity, cost, and operational fragility that is difficult to justify unless the threat model genuinely demands physics-based key distribution.

Reconceptualising Security Models

The quantum transition is not an algorithm swap. It forces something deeper: a rethinking of how security is defined, how it is quantified, and how long any given defence can be trusted before it decays into false assurance.

Crypto-Agility as a Design Primitive

Classical cryptographic deployment operated on an assumption that now looks dangerously optimistic: algorithms would last decades. RSA-2048 was expected to remain secure until 2030 at a minimum. PQC algorithms have survived, at most, a few years of serious scrutiny. SIKE and Rainbow demonstrate that multi-year expert evaluation can still miss fatal weaknesses [5].

So algorithm replacement needs to become ordinary. Boring, even. Not an emergency convened in a crisis room. Not a multi-year migration programme with executive sponsors and Gantt charts. A routine maintenance operation, as unremarkable as rotating certificates or patching a dependency on a Tuesday afternoon. TLS 1.3 already supports algorithm negotiation with PQC extensions; hybrid certificates (PQ/T) allow dual-signing during transition periods; key encapsulation can be abstracted behind interfaces that support swapping. The engineering patterns exist. The organisational discipline to treat cryptographic primitives as replaceable modules, rather than load-bearing permanent infrastructure, does not.

Layered Defence and System-Level Thinking

“One good algorithm is enough” was always a simplification. Now it is a dangerous one. Confidence in any single PQC algorithm sits well below where confidence in RSA sat for most of its operational life, and layered defence becomes the rational response: PQC for computational resistance, QKD where physics-based guarantees justify the expense and infrastructure overhead, forward secrecy to contain blast radius when (not if) a key is compromised, aggressive key rotation to limit exposure windows.

But here is the part that gets less attention than it should. An algorithm’s theoretical security means nothing if the implementation leaks timing information through a side channel, or the key management system stores secrets in a world-readable file, or the migration process itself introduces a compatibility gap that silently downgrades connections to classical algorithms. PQC algorithm research has outpaced deployment engineering by a wide margin [4]. The gap is understandable in a field this young. It is also the gap that will determine whether the transition succeeds or stalls at pilot stage.

Research Gaps and Open Questions

Four areas stand out where the theoretical foundations remain incomplete or contested:

• Tight security reductions for lattice-based schemes: The worst-case to average-case reductions that underpin Kyber and Dilithium security proofs have gaps in tightness that affect concrete security parameter selection
• Formal hybrid security models: No rigorous framework exists for proving that hybrid QC/PQC systems provide security strictly greater than either component alone [2]
• Quantum-resistant zero-knowledge proofs: Identified by topic modelling as an emerging research area, but still lacking mature constructions suitable for standardisation [4]
• Side-channel resistance: Hardware implementations like HSPA focus on functional performance but do not address timing, power analysis, or electromagnetic emanation attacks

Takeaways

The quantum threat to public-key cryptography is not a matter of degree. Shor’s algorithm does not weaken RSA; it eliminates it. Migration means replacement, not optimisation, and the timeline for starting that replacement is governed by Mosca’s inequality, not by when a sufficiently large quantum computer is built.

For most deployments, lattice-based schemes (Kyber, Dilithium) are the pragmatic starting point: best performance on commodity hardware, broadest library support, and NIST’s endorsement. But pragmatic is not the same as permanent. SIKE and Rainbow both survived years of expert evaluation before classical (not quantum) attacks destroyed them. Lattice cryptography has received less adversarial attention than integer factorisation. Treat the current algorithm portfolio as provisional.

Code-based PQC is maturing faster than it might appear from a pure key-size perspective. The HSPA accelerators from He et al. demonstrate 57 to 80% ADP improvement on FPGA, which opens a pathway for HQC and BIKE in constrained environments where lattice schemes might not be the only viable option.

The hybrid QC/PQC concept from Kavitha et al. is intellectually attractive but practically unvalidated. No prototype exists; no formal security model proves the combination exceeds either component alone. For high-value targets where “harvest now, decrypt later” is an existential concern, the concept deserves further investigation, but treating a conceptual paper as deployment guidance would be premature.

One architectural decision matters more than any algorithm selection: crypto-agility. The ability to swap primitives without redesigning the system is what protects against the surprises that a young cryptographic field will inevitably produce.

Questions on Algorithmic Foundations and Hardware

What makes post-quantum cryptography different from quantum cryptography?

They solve different problems with different tools. Post-quantum cryptography uses classical algorithms, running on ordinary hardware, designed to resist attacks from quantum computers. Quantum cryptography (typically QKD) uses the physical properties of photons to distribute keys, which requires specialised quantum hardware and fibre-optic channels. PQC is about upgrading the maths; QKD is about changing the physics. Most organisations will deploy PQC. Very few will deploy QKD.

Why were SIKE and Rainbow broken, and what does that tell us?

SIKE fell to a classical mathematical attack that exploited torsion-point information in the SIDH protocol, building on a theorem published by Kani in 1997. Rainbow was broken by Beullens’ key-recovery attack, also entirely classical. Both had survived multiple rounds of NIST evaluation. The lesson is not that NIST’s process failed; it is that PQC algorithms sit on mathematical foundations that have received far less adversarial attention than RSA or ECC. Expect more surprises. Design for algorithm replacement.

Is AES-256 safe against quantum computers?

For all practical purposes, yes. Grover’s algorithm halves the effective key length in the idealised brute-force model, reducing AES-256 to roughly 128-bit equivalent security against a quantum adversary. That level of resistance remains computationally infeasible with any foreseeable resources. The real cost of running Grover on actual quantum hardware (circuit depth, error correction, parallelisation limits) may push the effective security even higher. The genuine vulnerability in most systems is asymmetric cryptography, not AES.

How does hardware acceleration change PQC deployment decisions?

Code-based PQC schemes like HQC and BIKE depend on sparse polynomial multiplication that is expensive in software. The FPGA accelerators from He et al. reduce the area-delay product by 57 to 80%, which makes these schemes viable candidates for embedded and IoT contexts where software-only performance would be prohibitive. Without that kind of hardware support, the practical PQC palette shrinks to lattice-based schemes almost by default.

Technical Appendix