Post-Quantum Cryptography (PQC)
1. Overview
A. Definition
Post-quantum cryptography (PQC) is the collective term for public-key encryption and digital-signature algorithms designed to remain secure even once a large general-purpose quantum computer exists, by basing their security on mathematical problems that quantum algorithms cannot solve efficiently — such as lattice, code, hash, and multivariate problems. Because they run on ordinary digital (classical) computers, they are fundamentally different from quantum key distribution (QKD), which distributes keys via quantum physical phenomena.
Today's internet trust rests heavily on RSA and elliptic-curve cryptography (ECC). TLS key exchange, digital signatures and certificates (PKI), code signing, and blockchain wallet signatures all stand on the assumption that "factoring large numbers" or the "discrete logarithm problem" cannot be solved in any realistic time. In 1994, however, Shor's algorithm showed that a sufficiently large fault-tolerant quantum computer could solve both problems in polynomial time — effectively breaking RSA and ECC. Post-quantum cryptography answers this threat by keeping the operational framework of classical cryptography while replacing the mathematical foundation itself with problems resistant to quantum attack.
B. Background and Necessity
The decisive reason PQC became "a task for right now" rather than "a future precaution" is the Harvest Now, Decrypt Later (HNDL) threat. Even without a quantum computer today, an adversary can collect and store the ciphertext flowing across networks now and decrypt it later once a quantum computer is built. Data with a long protection horizon — state secrets, medical records, financial transactions, intellectual property — is therefore already exposed before any quantum computer exists. Mosca's inequality (X+Y>Z), where X is the required protection period, Y the migration time, and Z the arrival of quantum computers, compactly captures this urgency: if X+Y exceeds Z, you are already at risk.
Symmetric ciphers and hashes are a different matter. Grover's algorithm gives only a square-root speedup for search, so AES-128's effective strength drops to about 64 bits but AES-256 remains secure, and hashes are handled by lengthening the output. Public-key cryptography, by contrast, collapses exponentially under Shor's algorithm and cannot be saved by length adjustments alone — only by replacement. This asymmetry leads to PQC's core task: "public-key systems (key exchange and digital signatures) must be replaced first, and comprehensively."
Institutionally, the transition has already begun. The U.S. NIST ran a public-competition standardization from 2016 and finalized its first standards in August 2024, and the U.S. NSA's CNSA 2.0 set a timeline for full PQC adoption across national-security systems around 2035. Korea, too, announced a master plan to migrate the national cryptographic system to post-quantum cryptography by 2035 (July 2023), led by the National Intelligence Service, and is securing its own algorithms through a Korean competition (KpqC). In short, PQC is not "a technology for someday" but a regulatory and operational priority for which migration plans must be made now.
C. Characteristics
- Classical-hardware compatible: runs on existing CPUs without a quantum computer, largely reusing the existing PKI/TLS operating model.
- Diversified mathematical foundations: spreads bets across distinct hard problems — lattice, code, hash, multivariate, isogeny — so an alternative remains if one problem is broken.
- Size/performance trade-off: public keys, signatures, and ciphertexts are larger than RSA/ECC (hundreds of bytes to several KB or more), a burden in bandwidth- and memory-constrained environments.
- Demands crypto-agility: a structure that allows easy algorithm replacement (crypto-agility) and hybrid migration are effectively mandatory.
2. Classification Scheme and Overall Structure of PQC
Post-quantum cryptography splits into families by "which mathematical hard problem it stakes its security on." The structural diagram below organizes the representative families together with the algorithms NIST standardized or eliminated.
flowchart TB
PQC["Post-Quantum Cryptography (PQC)"] --> L["Lattice-based"]
PQC --> C["Code-based"]
PQC --> H["Hash-based"]
PQC --> M["Multivariate"]
PQC --> I["Isogeny"]
L --> LK["ML-KEM (Kyber) - key est."]
L --> LS["ML-DSA (Dilithium) - signature"]
L --> LF["FN-DSA (Falcon) - signature"]
C --> CM["Classic McEliece"]
C --> CH["HQC (backup KEM, sel. 2025)"]
H --> HS["SLH-DSA (SPHINCS+) - signature"]
M --> MR["Rainbow (broken 2022)"]
I --> IS["SIKE (broken 2022)"]
style PQC fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
style L fill:#e9f8ee,stroke:#1f9d55,stroke-width:1px
style M fill:#fdecec,stroke:#d64545,stroke-width:1px
style I fill:#fdecec,stroke:#d64545,stroke-width:1px
Lattice-based cryptography is the current mainstream of PQC. It rests on the assumption that the "closest vector problem (CVP)" in a lattice, or its variant LWE (Learning With Errors) and Module-LWE, is hard for both quantum and classical computers. Because its operations are mostly polynomial multiplication and modular addition, it is comparatively fast with balanced key/ciphertext sizes, which is why NIST chose lattice families as the mainstay for both key establishment (ML-KEM) and signatures (ML-DSA, FN-DSA). The downside is that concentrating all core algorithms in one family raises a single-point-of-failure concern — "if that problem breaks, everything collapses at once" — making a parallel backup family important.
Code-based cryptography exploits the fact that "decoding a general error-correcting code is NP-hard." It dates back as far as the 1978 McEliece cryptosystem, so it enjoys long-standing confidence in its security, but its public key can reach hundreds of thousands of bytes, making practical deployment awkward. NIST's March 2025 addition of HQC as a backup to ML-KEM was intended to secure a mathematical foundation different from the mainstay (lattice) and thereby diversify risk. Hash-based signatures (SLH-DSA, XMSS, LMS) assume only the security of the hash function, so they are the most conservatively secure, but signatures are large and slow. In contrast, the multivariate (Rainbow) and isogeny (SIKE) families were each hit by devastating attacks in 2022 and effectively eliminated — symbolizing PQC's distinctive risk: "a new mathematical hard problem cannot be trusted lightly until it has undergone sufficient public scrutiny."
| Family | Representative problem | Standard/representative algorithm | Strength | Weakness |
|---|---|---|---|---|
| Lattice | Module-LWE/LWR, NTRU | ML-KEM, ML-DSA, FN-DSA | Balanced speed/size, versatile | Relatively new, concentration risk |
| Code | Syndrome decoding | Classic McEliece, HQC | Long scrutiny, high trust | Large public key |
| Hash | Hash collision resistance | SLH-DSA, XMSS/LMS | Most conservative security | Large signature, stateful |
| Multivariate | MQ problem | (Rainbow — eliminated) | Short signature | Security-collapse cases |
| Isogeny | Supersingular isogeny | (SIKE — eliminated) | Very small key | Broken by 2022 attack |
3. NIST Standards and Algorithm Composition
NIST began its competition in 2016, narrowed some 70 candidates over several rounds, and officially announced its first three PQC standards on August 13, 2024. Note precisely in an exam answer that these standards were renamed from their former candidate names (Kyber, Dilithium, SPHINCS+) to standard names (ML-KEM, ML-DSA, SLH-DSA).
| Standard | Algorithm (original candidate) | Purpose | Family | Status |
|---|---|---|---|---|
| FIPS 203 | ML-KEM (CRYSTALS-Kyber) | Key encapsulation (KEM, key est.) | Lattice | Finalized 2024.8 |
| FIPS 204 | ML-DSA (CRYSTALS-Dilithium) | Digital signature (mainstay) | Lattice | Finalized 2024.8 |
| FIPS 205 | SLH-DSA (SPHINCS+) | Digital signature (hash-based backup) | Hash | Finalized 2024.8 |
| FIPS 206 | FN-DSA (Falcon) | Digital signature (compact) | Lattice | In development (draft) |
| (planned) | HQC | Key encapsulation backup | Code | Selected 2025.3, standardizing |
Each algorithm offers several parameter sets by security strength. For instance, ML-KEM provides ML-KEM-512/768/1024, targeting strengths comparable to AES-128/192/256 respectively; larger numbers are more secure but the public key and ciphertext grow. In practice, picking "a parameter neither excessive nor insufficient for the protection period and threat level" is the cost/security sweet spot, and Google's and Cloudflare's hybrid TLS deployments defaulting to ML-KEM-768 reflect exactly this compromise. Not confusing the security-strength level (NIST Level 1/3/5) with the parameter-set correspondence is important in an answer.
The division of roles among the three standards reflects a clear design intent. ML-KEM is a key encapsulation mechanism (KEM) that "securely agrees a session key with the peer," as in TLS, replacing the former RSA/ECDH key exchange. In a KEM, the sender encapsulates a symmetric key with the public key and sends it, and the receiver extracts it with the private key — substituting a lattice problem for the Diffie-Hellman-style key exchange that is vulnerable to Shor's algorithm. ML-DSA is the default for general digital signatures; FN-DSA (Falcon) has short signatures and suits places where bandwidth matters, and SLH-DSA is positioned as a conservative backup staking security on hashes rather than lattices. In other words, the multi-family diversification strategy — "make lattice (ML-DSA) the default for signatures, but keep hash (SLH-DSA) in reserve in case lattice wavers" — is baked into the very composition of the standards.
4. Migration Procedure and the Hybrid Approach
The practical heart of PQC migration is not "replace all at once" but gradual, hybrid transition. The diagram below shows the stages an organization goes through together with the flow of the hybrid key exchange widely used in TLS.
flowchart LR
subgraph MIG["Migration roadmap"]
A["1. Crypto inventory<br/>(what is used where)"] --> B["2. Risk prioritization<br/>(retention, sensitivity)"]
B --> C["3. Crypto-agility<br/>(swappable design)"]
C --> D["4. Apply hybrid"]
D --> E["5. Pure PQC"]
end
subgraph HYB["Hybrid key exchange (TLS)"]
CH["ClientHello: X25519 + ML-KEM"] --> SH["ServerHello: both shared keys"]
SH --> KDF["Combine both secrets (KDF)"]
KDF --> KEY["Session key set"]
end
E -.ref.-> HYB
style A fill:#e8f0fe,stroke:#2f6fed,stroke-width:1px
style KEY fill:#e9f8ee,stroke:#1f9d55,stroke-width:1px
The starting point of migration is, paradoxically, not cryptography itself but visibility. Most organizations do not precisely know "where, which algorithm and key length, with what lifetime" they use. Thus one identifies the usage landscape through a crypto inventory and a CBOM (Cryptographic Bill of Materials), and prioritizes assets that are both long-lived and sensitive (long-retained documents, code-signing root keys, financial transactions) first. Without this step, replacing only the algorithm leaves RSA embedded deep in embedded-device firmware or third-party libraries, so the transition ends up "full of holes."
Next, one secures crypto-agility — a structure where the algorithm can be swapped by configuration — and then applies the hybrid approach. Hybrid runs an existing algorithm (e.g., X25519) and a PQC one (e.g., ML-KEM-768) simultaneously and combines the two shared secrets with a KDF, so that it is "secure as long as only one of the two is not broken." In fact, Google Chrome and Cloudflare deployed an X25519+ML-KEM hybrid in TLS 1.3 at large scale in 2023–2024, a pragmatic choice to insure against implementation flaws or not-yet-revealed vulnerabilities in PQC algorithms using proven existing ones. Only in the final stage of migration does one move to pure PQC.
5. Comparison with Existing Public-Key Crypto and QKD
To understand PQC's position precisely, two axes of comparison are needed: first, "what it replaces" (versus existing RSA/ECC); second, "how it differs from the often-confused quantum key distribution (QKD)." In exam answers especially, describing PQC and QKD as the same thing is a deduction point, so you must be able to explain the reason for the difference as well.
| Criterion | RSA-2048/ECC | PQC (ML-KEM, etc.) | QKD (quantum key distribution) |
|---|---|---|---|
| Security basis | Factoring, discrete log | Quantum-hard math problems | Quantum mechanics (measurement disturbance) |
| Quantum resistance | None (collapses to Shor) | Yes | Yes |
| Operating basis | Classical computer | Classical computer | Dedicated quantum hardware/optics |
| Key/signature size | Small (hundreds of B) | Large (several KB) | N/A (keys only) |
| Distance/infra | Internet-wide | Internet-wide (SW swap) | Distance-limited, dedicated network |
| Signature support | Supported | Supported | Not supported (key distribution only) |
Versus existing RSA/ECC, PQC's essential difference is that it changes the basis of security. RSA rests on the hardness of factoring, ECC on elliptic-curve discrete log, but both collapse in polynomial time to Shor's algorithm. PQC's greatest strength is operational continuity — swap only the software and it runs on top of the existing internet and PKI. The cost is larger keys, signatures, and ciphertexts. For example, while an ECDSA signature is around 64 bytes, an ML-DSA signature exceeds 2 KB, and SLH-DSA ranges from several KB to tens of KB. This size increase becomes a real bottleneck in bandwidth- and storage-tight environments such as TLS handshakes with long certificate chains or IoT firmware signing.
The difference from QKD is more fundamental. QKD distributes keys using the physical law that measuring a photon disturbs its state to detect eavesdropping, but it needs dedicated quantum hardware and optical infrastructure, is heavily distance-constrained, and cannot provide digital signatures. PQC, by contrast, runs in pure software across the whole internet and covers signatures and authentication too. For this reason, national security agencies (such as the U.S. NSA) have made clear that "the center of a general-purpose security system is PQC, not QKD." The two are better seen not as competitors but as a complementary relationship, in which QKD may serve auxiliary high-security segments.
6. Deep Dive — Domestic and International Standardization Trends and KpqC
The global standardization landscape shifted its center of gravity from "selection" to "implementation" around 2024–2025. After NIST finalized FIPS 203/204/205 in August 2024, it selected HQC as its fifth algorithm (a code-based backup KEM) on March 11, 2025, while the FN-DSA (Falcon) standard (FIPS 206) is in development. This shows that the diversification philosophy of "lattice mainstay + heterogeneous-family backup" has solidified at the standard level. In industry, too, libraries such as OpenSSL, BoringSSL, and liboqs have incorporated ML-KEM/ML-DSA, and Apple introduced a PQC-based protocol called PQ3 into iMessage — adoption is accelerating.
Domestically, Korea secured its own algorithms through the KpqC (Korean post-quantum cryptography) competition led by the National Intelligence Service. Opening the call in November 2021, it received 16 entries in 2022, narrowed them to 8 in a first round in November 2023, and finalized 4 algorithms in January 2025. The finalists are reportedly 2 digital signatures (AIMer, HAETAE) and 2 public-key-encryption/key-establishment schemes (NTRU+, SMAUG-T). In particular, the AIMer signature technology was introduced as a case in which a domestic company (Samsung SDS) participated. That said, detailed specifications, names, and schedules may be updated as the competition proceeds, so for actual deployment it is safest to consult the official specifications of the NIS and the post-quantum cryptography research group.
The standardization bodies are not limited to NIST, either. The work of embedding key exchange and signatures into actual protocols is carried out by the IETF for TLS 1.3 hybrids, X.509 certificates, SSH, and so on, and by Europe's ETSI and the international ISO/IEC JTC1 SC27 in parallel. That is, "algorithm standards (NIST)" and "protocol/operational standards (IETF, ETSI, ISO)" mesh at different layers, and applying PQC to real products requires tracking both layers. Domestically, too, the follow-up work of reflecting KpqC algorithms into TTA group standards and national standards, and aligning with the cryptographic module validation program (KCMVP), determines how effective the transition is.
On the policy side, Korea announced a master plan to migrate the national cryptographic system to PQC by 2035 in July 2023, and has since been concretizing field-specific transition roadmaps for the public, financial, and defense sectors through a comprehensive implementation plan. This aligns with the roughly-2035 full-transition timeline set out by the U.S. CNSA 2.0. From a Professional Engineer's perspective, PQC is likely to appear on exams not as a mere cryptographic-technology problem but as a multi-year transition program at the national/enterprise level that entails governance, budget, procurement, and workforce issues.
7. Considerations and Implications
Single-family concentration risk and a diversification strategy: That the mainstay standards are all lattice-based gives efficiency and consistency, but if a fundamental breakthrough emerges against lattice problems, simultaneous collapse is a risk. Hence a multi-family readiness that also supports hash (SLH-DSA) and code (HQC) backups, and a crypto-agile architecture that can swap algorithms by configuration, are a strategic must.
Managing the performance/size trade-off: PQC's larger keys, signatures, and ciphertexts cause TLS handshake latency, certificate-chain bloat, and memory pressure on constrained devices such as IoT and smart cards. Before deployment one should measure the impact on bandwidth, latency, and power, and balance security strength against cost through parameter-set choice (e.g., ML-KEM-512/768/1024).
The inevitability of hybrid and gradual transition: Given the risk of implementation/design flaws in PQC, whose public-scrutiny period is still relatively short, a hybrid combined with existing algorithms is the realistic answer for now. However, hybrid increases handshake cost and complicates interoperability testing, so an exit strategy toward pure PQC as standards mature must be designed alongside it.
Proactive asset protection that must start now (HNDL response): Long-lived data is exposed to collect-and-store threats even now, with no quantum computer. By Mosca's inequality (X+Y>Z), one must immediately begin crypto inventory/CBOM creation → prioritized transition of sensitive assets, and recognize at the organizational-governance level that migration is a multi-year program.
Related technologies and supply-chain considerations: PQC migration is interwoven with PKI, HSMs, TLS libraries, code signing, the digital-signature regime, and the entire commercial-solution supply chain. If one fails to track cryptography embedded in third-party libraries and firmware, the transition is nullified; it is therefore advisable to make confirmation of a vendor's PQC roadmap and alignment with domestic KpqC and the validated cryptographic module list (KCMVP) a requirement at the procurement/contract stage.
References
- NIST, "Post-Quantum Cryptography Standardization" — https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
- NIST, "NIST Releases First 3 Finalized Post-Quantum Encryption Standards" (FIPS 203/204/205, 2024.8) — https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards
- Wikipedia, "NIST Post-Quantum Cryptography Standardization" — https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography_Standardization
- BoanNews, "[Column] Selection and Use of KpqC Competition Algorithms" — https://m.boannews.com/html/detail.html?idx=135674
- Samsung SDS Insights, "The Great Transition to PQC" — https://www.samsungsds.com/kr/insights/the-great-transition-to-pqc.html
In one line: PQC is classical-computer public-key and signature technology that replaces RSA/ECC — which collapse under Shor's algorithm — with algorithms built on quantum-hard problems such as lattice, code, and hash; set against NIST FIPS 203/204/205 finalization and Korea's KpqC and 2035 migration master plan, its core is a proactive, gradual transition via crypto inventory, crypto-agility, and hybrid in response to the HNDL threat.