Skip to content

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.

Table 10.1. BKZ Performance and Lattice Security Estimates
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:

Table 10.2. Post-Quantum Zero-Knowledge Proof Systems
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.

Table 10.3. Quantum Computing Milestones (2019–2025)
Year Organization Milestone Qubits
2019 Google “Quantum supremacy” — Sycamore (random circuit sampling) 53
2021 IBM Eagle processor 127
2022 IBM Osprey processor 433
2023 IBM Condor + Heron processors 1121
2024 Google 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:

  1. Efficient PQC-based OT extensions (replacing Diffie-Hellman based OT).

  2. PQC-friendly commitments for MPC protocols.

  3. 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:

Table 10.4. FHE Schemes and Libraries (2024–2025)
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

Table 10.5. Open-Source PQC Research and Implementation Projects
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

Table 10.6. Key PQC Research Venues
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.