Questions: Post-Quantum Cryptography

Question 1

An organization argues they don't need post-quantum cryptography because large-scale quantum computers are at least 10-15 years away. What threat model are they ignoring?

Model answer: The 'harvest now, decrypt later' threat: adversaries (especially state-level) can record encrypted network traffic today and store it. Once quantum computers become available, they can retroactively decrypt everything they captured. Data with long-term sensitivity — state secrets, medical records, financial data, intellectual property — needs quantum-resistant protection NOW, because it must remain confidential for decades beyond the point when quantum computers arrive.

The transition timeline matters: deploying new cryptographic standards across global infrastructure takes years. If migration starts when quantum computers arrive, the window of vulnerability extends years further. NIST and NSA recommend immediate migration planning, with hybrid deployments (classical + PQC) as the transitional approach.

Question 2

NIST selected lattice-based schemes (ML-KEM, ML-DSA) as primary standards but also standardized a hash-based signature scheme (SLH-DSA/SPHINCS+). Why include both?

• A. Hash-based signatures are faster than lattice-based ones
• B. SLH-DSA relies only on the security of hash functions, which have decades of analysis and no known algebraic structure to exploit. If a breakthrough breaks lattice assumptions, SLH-DSA survives. Including it provides cryptographic diversity — not putting all eggs in the lattice basket
• C. Hash-based signatures provide shorter keys than lattice-based ones
• D. NIST was required by law to standardize at least two different mathematical foundations

Answer: (B)

Cryptographic diversity is a hedge against catastrophic assumption failure. All lattice-based schemes share related mathematical foundations — a breakthrough in lattice cryptanalysis could break them all simultaneously. Hash-based signatures rest on a completely different foundation (the security of hash functions, a much older and more conservative assumption). The tradeoff is performance: SLH-DSA signatures are ~8-50 KB and signing is slower, compared to ML-DSA's ~2.4 KB signatures and faster signing. The diversity premium justifies the performance cost.

Question 3

Shor's algorithm breaks RSA and ECDSA but does not break AES or SHA-256. Does this mean symmetric cryptography is unaffected by quantum computers?

• A. Correct — symmetric cryptography is completely quantum-safe
• B. Partially — Grover's algorithm provides a quadratic speedup for brute-force key search, halving the effective security. AES-128 drops to ~64 bits of quantum security, so AES-256 (providing ~128 quantum bits) is recommended. SHA-256 collision resistance drops from 128 to ~85 bits. These are manageable by doubling key/hash sizes, unlike the exponential-to-polynomial collapse for public-key schemes
• C. Symmetric cryptography is equally broken by quantum computers
• D. Grover's algorithm breaks AES in linear time

Answer: (B)

Grover's algorithm searches an unstructured space of N items in O(sqrt(N)) quantum operations. For AES-128 with 2^128 keys, this means ~2^64 quantum operations — feasible for a large quantum computer. AES-256 requires ~2^128 quantum operations, which remains secure. The impact on symmetric crypto is quantitative (double key sizes) rather than qualitative (completely broken). This is why the PQC transition focuses on public-key algorithms, which face an existential threat.

Question 4

During the PQC transition, hybrid key exchange combines a classical algorithm (like ECDH) with a PQC algorithm (like ML-KEM). Security holds if EITHER algorithm is secure.

• T. True
• F. False

Answer: True

Hybrid key exchange derives the shared secret by combining outputs from both algorithms (typically via a key derivation function). If ML-KEM turns out to be broken but ECDH is secure (no quantum computers), the combined key is still secure. If ECDH is broken by a quantum computer but ML-KEM is secure, the combined key is still secure. Only if both are simultaneously broken does the system fail. This belt-and-suspenders approach provides safety during the uncertain transition period where confidence in PQC schemes is still building.

Question 5

The SIKE/SIDH isogeny-based key exchange was a NIST PQC finalist before being catastrophically broken in 2022. What lesson does this carry for the PQC transition?

Model answer: SIDH survived over 10 years of cryptanalysis before Castryck-Decru found a polynomial-time key recovery attack in 2022 — a complete break, not a marginal improvement. This demonstrates that even well-studied schemes can harbor fundamental vulnerabilities. Lessons: (1) cryptographic diversity is essential — relying on a single mathematical foundation is risky, (2) longer cryptanalysis history provides more confidence but never certainty, (3) hybrid deployments protect against surprise breaks in new schemes. NIST's decision to include hash-based signatures alongside lattice schemes reflects this lesson.

SIDH's break was enabled by known mathematical connections between isogenies and abelian varieties that the cryptographic community had not fully explored. The attack used theta functions and the structure of product isogenies. It was a reminder that the security of a scheme depends on the full depth of mathematical understanding of the underlying problem — and that understanding evolves.