Code-based (McEliece, BIKE, HQC)
The most conservative PQC pillar. Quantum gives only modest sub-Grover ISD improvements — and even those need QRAM.
State of the art
Best known quantum ISD exponent for a length-n binary random linear code at rate 1/2 is 2^(0.05869 n) — Kachigar–Tillich 2017 via quantum walks on Stern/Dumer ISD, marginally tightened by Kirshanova 2018 combining MMT/BJMM with nearest-neighbor search. Classical BJMM baseline is 2^(0.0494 n); the quantum speedup is therefore ~16%, not the naïve 50% one might expect from full Grover. Engelberts–Etinski–Loyer 2024 prove the closing-result: dropping quantum near-neighbor sieving into the sieving-ISD framework yields NO improvement over Bernstein 2010 Grover-over-Prange. The bottleneck is the ISD outer loop, not the sieving subroutine. Classic McEliece (mceliece6960119) targets ~166 quantum bits; BIKE / HQC Level-1 target 128 quantum bits — all with QRAM-assuming exponents. Dinh–Moore–Russell 2011 close off the Shor-style route: quantum Fourier sampling over the symmetric group cannot recover Goppa structure.
Known dead ends (read first)
- ×Shor / non-abelian HSP attack on McEliece key recovery via code equivalence — quantum Fourier sampling over the symmetric group does not concentrate on the hidden subgroup for code-automorphism groups. — Dinh, Moore, Russell arXiv:1111.4382
- ×Quantum near-neighbor sieving as a drop-in for sieving-ISD — proven to yield NO improvement over Grover-over-Prange in the standard asymptotic model. — Engelberts, Etinski, Loyer arXiv:2408.16458
- ×May–Ozerov nearest-neighbor ISD at NIST-PQC parameter sizes — 'galactic' constants make it strictly slower than BJMM for all cryptographically relevant lengths. — Bouillaguet–Delaplace–Hamdad IACR CiC 2024; Kirshanova arXiv:1808.00714
Open sub-problems
QRAM-free quantum ISD: re-derive all quantum ISD exponents in the QROM / parallel-query model and produce revised concrete security estimates for BIKE / HQC / McEliece. No existing literature for ISD though done for lattices.
Quantum exploitation of quasi-cyclic structure in BIKE / HQC: characterize the QFT on the QC syndrome-decoding coset space; determine whether it leaks information about the sparse secret key (fresh angle, no existing literature).
Tight quantum query lower bounds for ISD via polynomial / adversary method — settle whether Grover-ISD is optimal within the Prange paradigm.
Paired donor analogies
Key papers
1111.4382acceptedCloses off the Shor-style route to McEliece: quantum Fourier sampling cannot distinguish random codes from Goppa codes.
1703.00263acceptedFirst quantum ISD to beat Grover-over-Prange: 2^(0.05869 n) via quantum walks adapted from subset-sum.
1808.00714acceptedUnifies Kachigar–Tillich with May–Ozerov nearest-neighbor; quantum versions of MMT/BJMM. Marginal further improvements.
2106.02747acceptedFirst quantum SCP → SDP reduction, adapting Regev's lattice technique to codes. Cryptographic hardness link analogous to LWE foundations.
2306.10294acceptedPurely algebraic (non-ISD) attack using quadratic-form invariants of Goppa codes. Exponential today; opens a new structural attack vector.
2310.20651acceptedDefines a quantum-superposition syndrome-decoding analog of quantum LWE; poly-time at low noise — raises whether code-based security needs re-examination under quantum-access oracles.
2408.16458acceptedFirst quantum code-sieving algorithms via quantum walks with LSF; CRITICALLY proves naïve sieving-ISD yields NO improvement over Bernstein 2010 baseline.
2104.12810acceptedExtends ISD to arbitrary weight functions / alphabets via Wagner's algorithm; quantum baselines for ROLLO and Lee-metric schemes.