Chapter 10: PQC Research and Open Problems¶
10.1 Open Security Problems¶
Despite the NIST standardization of PQC algorithms, significant open security questions remain.
10.1.1 Lattice Security Analysis¶
BKZ Algorithm Progress¶
The BKZ (Block Korkine-Zolotarev) algorithm is the primary classical algorithm for solving lattice problems. Its practical efficiency determines PQC security levels.
| Year | BKZ Development | Impact on Security Estimates | Reference |
|---|---|---|---|
| 1987 | BKZ original | Baseline lattice reduction | Schnorr-Euchner |
| 2011 | BKZ 2.0 | Preprocessing with “tours”; \(\sim\)20% efficiency gain | Chen-Nguyen |
| 2016 | G6K sieve | GPU-accelerated sieving; faster BKZ oracle | Ducas et al. |
| 2021 | Filtered PNJ-BKZ | Progressive BDGL sieving; tighter analysis | Ducas et al. |
| 2024 | Chen et al. (preprint) | Improved quantum enumeration; re-analysis of RLWE security | Under review |
2024 Chen et al. Preprint
In 2024, a preprint by Chen, Zhang, and colleagues claimed improved attacks on RLWE-based systems. After initial review, the community found the analysis was partially correct but did not break current NIST parameters. The incident highlighted the ongoing need for conservative parameter selection and continuous security analysis. NIST parameters include significant security margins above current best attacks.
Module Structure and Security¶
An open question: does the module structure of MLWE (vs. plain LWE) introduce exploitable structure? Current analysis suggests module structure is either as hard as or only slightly easier than plain LWE with equivalent parameters, but this is an active research area.
10.1.2 Code-Based Security Gaps¶
-
ISD improvements: Information Set Decoding algorithms (Prange, Stern, BJMM, MMT, DOOM) continue to improve. HQC parameters are designed with 10–15 bit security margin over current best ISD.
-
Quasi-cyclic structure: Does the quasi-cyclic structure of HQC codes introduce algebraic weaknesses beyond SDP? Research ongoing.
-
Decoding failure probability: Any non-zero decoding failure rate in a KEM can be exploited; HQC’s parameters target \(2^{-128}\) failure probability.
10.1.3 Isogeny-Based Security After SIDH¶
Post-SIDH isogeny research focuses on:
-
CSIDH security: The GAIP (Group Action Inverse Problem) underlying CSIDH — quantum security analysis still evolving. Recent attacks suggest CSIDH-512 provides only \(\sim\)73-bit quantum security.
-
SQIsign security: Based on non-linear hidden path problem; believed hard for quantum computers, but proof is elusive.
-
Higher-dimensional extensions: SQIsignHD uses degree-2\(^k\) isogenies to speed up SQIsign but introduces new security assumptions.
10.2 Active Research Areas¶
10.2.1 Threshold PQC¶
Threshold signatures allow \(t\)-of-\(n\) parties to jointly sign without any single party holding the complete secret key:
-
FROST-ML-DSA: Threshold variant of ML-DSA; active IETF draft.
-
TECDSA-PQC: Classical TECDSA extended with PQC components.
-
Applications: Multi-party signing for blockchain, HSM backup, cloud KMS.
-
Challenge: Rejection sampling in ML-DSA complicates threshold constructions.
10.2.2 Zero-Knowledge Proofs from PQC¶
ZK-SNARKs and other zero-knowledge proof systems classically use pairings (BLS12-381), which are quantum-vulnerable. PQC ZK alternatives:
| System | Basis | Description | Proof size | Status |
|---|---|---|---|---|
| FAEST | AES-MPC | AES circuit in MPC-in-the-head | 5–6 KB | NIST R2 candidate |
| Banquet | AES-MPC | 3-party AES OWF; smaller proof | 17 KB | Research |
| Picnic | LowMC-MPC | MPC-in-the-head from LowMC | 12–40 KB | Mature |
| STARK | Hash | Scalable transparent; no trusted setup | 300+ KB | Deployed |
| Dilithium-G | Lattice | ZK proofs of ML-DSA signature knowledge | 10+ KB | Research |
10.2.3 Quantum-Safe Key Derivation¶
Key derivation functions (KDFs) and key agreement protocols require analysis for quantum safety:
-
HKDF with ML-KEM: HKDF-SHA256 remains quantum-safe (Grover gives 128-bit security with 256-bit outputs).
-
PQC in TLS 1.3 KDF: The TLS 1.3 handshake KDF (HKDF) is quantum-safe; only key exchange needs PQC upgrade.
-
Session key independence: Each TLS session uses a fresh ML-KEM key; compromise of one session does not affect others.
10.2.4 Blockchain and Post-Quantum Consensus¶
-
Ethereum’s PQC roadmap: Ethereum (post-Merge) uses BLS12-381 for validator signatures (quantum-vulnerable). The Ethereum roadmap includes a PQC transition, estimated 2030+.
-
PQC-friendly VRFs: Verifiable Random Functions for PoS consensus need PQC versions; lattice-based VRFs under research.
-
PQC STARKs for scaling: STARKs (hash-based, quantum-safe) already deployed for Ethereum L2 scaling (StarkNet, Polygon zkEVM).
10.3 Quantum Computing Progress¶
Understanding the actual timeline of CRQC development is critical for migration planning.
| Year | Organization | Milestone | Qubits |
|---|---|---|---|
| 2019 | “Quantum supremacy” — Sycamore (random circuit sampling) | 53 | |
| 2021 | IBM | Eagle processor | 127 |
| 2022 | IBM | Osprey processor | 433 |
| 2023 | IBM | Condor + Heron processors | 1121 |
| 2024 | Willow chip — below-threshold error correction | 105 | |
| 2025 | IBM | “Quantum-centric supercomputing” roadmap updates | 4000+ |
CRQC Timeline Estimates
-
Near-term (now–2030): No CRQC capable of breaking RSA-2048. Current devices too noisy and small. However, HNDL risk is real.
-
Medium-term (2030–2035): Potential emergence of early CRQCs with limited capability. NIST deprecation deadline.
-
Long-term (2035+): High probability of full CRQCs. All classical public-key cryptography at risk.
-
Key metric: Breaking RSA-2048 with Shor’s algorithm requires \(\sim\)4000 logical qubits with fault tolerance \(\sim 10^{-12}\), requiring millions of physical qubits. Current devices: 1000–4000 physical qubits with error rates \(\sim 10^{-3}\).
10.4 Post-Quantum Secure Multi-Party Computation (MPC)¶
MPC allows multiple parties to jointly compute a function without revealing their inputs. Classical MPC uses:
-
Oblivious Transfer (OT) based on LWE — already PQC-secure.
-
Garbled circuits based on AES — quantum-safe with AES-256.
-
Secret sharing (Shamir) based on information-theoretic security — inherently quantum-safe.
Key open problems in PQC MPC:
-
Efficient PQC-based OT extensions (replacing Diffie-Hellman based OT).
-
PQC-friendly commitments for MPC protocols.
-
Threshold FALCON signing without floating-point complications.
10.5 Research on Advanced PQC Constructions¶
10.5.1 Attribute-Based Encryption (ABE) from Lattices¶
ABE allows decryption based on attributes (“decrypt if age \(>\) 18 AND country = US”). Lattice-based ABE:
-
Boneh-Boyen-Gentry (BBG) ABE is quantum-vulnerable (pairing-based).
-
LWE-based ABE schemes exist but are significantly larger and slower.
-
Garg-Gentry-Halevi-Raykova (GGHR) provides lattice ABE with bounded attributes.
10.5.2 Functional Encryption from Lattices¶
Functional encryption allows computing arbitrary functions on encrypted data:
-
Inner-product FE: Well-studied from LWE (ABDP scheme, 2020).
-
General FE: Constructible from indistinguishability obfuscation (iO), which has lattice constructions but is extremely inefficient.
-
Applications: Encrypted analytics, privacy-preserving ML.
10.5.3 Fully Homomorphic Encryption (FHE)¶
FHE, introduced by Gentry in 2009, allows computation on encrypted data. All practical FHE schemes are lattice-based:
| Scheme | Basis | Best For | Library |
|---|---|---|---|
| BFV | RLWE | Integer arithmetic; exact computation | SEAL (Microsoft) |
| BGV | RLWE | Integer arithmetic; batching | HEAAN, HElib |
| CKKS | RLWE | Approximate real arithmetic; ML | SEAL, OpenFHE |
| TFHE | LWE | Boolean circuits; fast bootstrapping | TFHE, Concrete |
| FHEW | LWE | Boolean; gate-by-gate | FHEW |
FHE performance (2025): TFHE performs \(\sim\)10,000 boolean gates/second on GPU; CKKS achieves \(\sim\)10 ms per 1024-element vector multiplication. Still 100–10,000\(\times\) slower than plaintext computation, but advancing rapidly.
10.6 Open-Source Research Tools¶
| Project | Language | Focus | License |
|---|---|---|---|
| liboqs | C | Unified PQC API; all algorithms | MIT |
| PQClean | C | Clean standalone implementations | MIT |
| mlkem-native | C/ASM | Production ML-KEM; formal verification | Apache 2 |
| SUPERCOP | C | Performance benchmarking | Public domain |
| pqm4 | C/ASM | ARM Cortex-M4 PQC | MIT |
| lattice-estimator | Python | Security estimation for lattice problems | Apache 2 |
| fpylll | Python | LLL/BKZ reduction library | LGPL |
| G6K | C++/Python | Lattice sieving; BKZ oracle | MIT |
| Microsoft SEAL | C++ | BFV/CKKS FHE library | MIT |
| OpenFHE | C++ | Multi-scheme FHE | BSD-2 |
| Concrete (Zama) | Rust | TFHE FHE compiler | BSD-3 |
| ChipWhisperer | Python | Side-channel analysis hardware+software | GPL/MIT |
| SCALib | Python | Statistical side-channel analysis | BSD-3 |
| NTRU Prime tools | Python | NTRU Prime implementation | CC0 |
10.7 Security Estimation: lattice-estimator¶
The lattice-estimator is the standard tool for estimating the concrete security of lattice-based schemes:
# Install: pip install lattice-estimator
from estimator import *
from estimator.lwe_parameters import LWEParameters
from estimator import ND # noise distributions
# ML-KEM-768 parameters (MLWE, k=3, n=256, q=3329, eta=2)
# Analyze as equivalent LWE with n_eff = k*n = 768
params_mlkem768 = LWEParameters(
n=768, # Effective dimension
q=3329, # Modulus
Xs=ND.CenteredBinomial(2), # Secret distribution (eta=2)
Xe=ND.CenteredBinomial(2), # Error distribution (eta=2)
m=768+32, # Number of LWE samples (public key + ciphertext)
tag="ML-KEM-768"
)
# Run all standard attacks
print("=== ML-KEM-768 Security Estimates ===")
result = LWE.estimate(params_mlkem768, deny_list=["arora-gb"])
# Print best attack cost
for attack, cost in result.items():
print(f" {attack}: {cost.get('rop', '?'):.1f} bit security")
# Expected output (approximately):
# ML-KEM-768 Security Estimates:
# usvp: 174.3 bit security
# dual: 171.8 bit security
# dual_hybrid: 168.4 bit security
# All > 160 bits classical security -> Level 3 confirmed
10.8 Conferences and Key Publications¶
| Venue | Description |
|---|---|
| CRYPTO | Annual IACR flagship conference; premier cryptography venue |
| EUROCRYPT | IACR European conference; strong PQC track |
| ASIACRYPT | IACR Asian conference; growing PQC presence |
| PQCrypto | Dedicated annual PQC conference (started 2006) |
| CHES | Cryptographic Hardware and Embedded Systems; SCA/implementation |
| CCS / ACM | ACM CCS, IEEE S&P, USENIX Security — applied PQC |
| IACR ePrint | Pre-print server: eprint.iacr.org; real-time research |
10.9 Summary and Future Outlook¶
-
Lattice security analysis continues: BKZ improvements, module structure questions, quantum enumeration improvements require ongoing monitoring.
-
The 2024 Chen et al. preprint demonstrated that community scrutiny is essential; NIST parameter margins provide important safety buffers.
-
Isogeny-based cryptography (SQIsign, CSIDH) remains promising for ultra-compact keys but awaits maturity.
-
Threshold PQC, zero-knowledge proofs, and attribute-based encryption from lattices are major active research frontiers.
-
FHE (lattice-based) is advancing rapidly; practical deployments for medical data analysis, ML inference expected by 2027–2030.
-
CRQC timeline: No CRQC before 2030, high risk 2030–2035, near-certain by 2040. HNDL means action is required now.
-
South Korea’s KPQC, Chinese national standards, and European research programs demonstrate global investment in PQC.
-
The lattice-estimator, G6K sieve tools, and IACR ePrint are essential resources for tracking the security state of PQC algorithms.
Final Recommendation
The field of post-quantum cryptography has matured from theoretical research to concrete deployable standards. The NIST standards (ML-KEM, ML-DSA, SLH-DSA, and HQC) represent the current best available algorithms with well-analyzed security margins. The time to migrate is now: deploy hybrid PQC for internet-facing services, begin cryptographic inventory, update PKI infrastructure, and build crypto-agile systems that can adapt to future algorithm changes. The quantum threat is not science fiction — it is an engineering problem with a known solution.