PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond LWE: Post-Quantum Assumptions under a Counterfactual Break of the Dihedral Coset Problem

Ramses Fernandez

arXiv:2610.36731v1cs.CR

TL;DR

The survey asks what a genuine efficient DCP breakthrough would imply for cryptographic assumptions, and at which parameters. It composes published reductions with explicit conditions and audits structured and heuristic routes; its sufficient guarantees reach specified lattice factors, but do not certify attacks on deployed parameters.

  • Problem

    The consequences of a genuine efficient DCP solver for cryptographic assumptions, and the parameters at which reductions support them, require careful analysis.

    Source: §1.1 · p. 4, §1.3 · p. 6

  • Method

    The survey distinguishes three DCP solver hypotheses and composes published reductions while auditing sample, state-preparation, success, and parameter conditions.

    Source: §1.5 · pp. 7–8

  • Results

    Under HReg(f), the compositions give worst-case GapSVP at eO(n^(1+2f)) and SIVP at O(n^(3/2+2f)); the analyzed 2024 LWE regime is already covered for f < 1/2 but excludes deployed parameters.

    Source: §1.5 · p. 8

  • Takeaways & Limitations

    A solver for a proof assumption does not by itself produce a forgery, and concrete applications require matching the reductions’ sample, distribution, and success conditions.

    Source: §1.5 · p. 8, §2.7 · p. 18

    Known hidden-subgroup measurement and sample-complexity bounds apply to specified models and do not establish computational lower bounds.

    Source: §9.2 · p. 83

Abstract

from arXiv · show

A refuted 2026 claim of an efficient quantum algorithm for the Dihedral Coset Problem (DCP) motivates this survey of the consequences of a genuine breakthrough. We distinguish a noiseless cyclic coset-state solver, a solver with a prescribed failure exponent, and an extrapolated-state solver. Regev's rare-corruption observation already makes the first hypothesis sufficient for lattice algorithms at some polynomial approximation factors; the witnessing algorithm determines the quantitative bounds. We compose unstructured reductions with explicit sample, state-preparation and success conditions, and compare their sufficient guarantees with more than thirty lattice and non-lattice assumptions. We restate the structured state conversion of Wen and Zheng and audit its forward parameter certificate; the printed bound supplies no certificate at the ML-KEM ring and modulus. We use an explicit affine embedding for heuristic gap estimates, explain the lossiness connection from decision NTRU to search Ring-LWE, and distinguish ordinary from module uniqueness. Chen's withdrawn 2024 quantum algorithm for LWE and a proposed repair of its post-processing would, if correct, reach only a many-sample, small-noise LWE regime that the failure-exponent hypothesis already covers for exponents below $1/2$, and no deployed parameter set. Tables separate rigorous consequences, heuristic comparisons and unverified applications, and distinguish solving a proof assumption from attacking a scheme. Classical structural attacks on Classic McEliece, which do not involve DCP but put the concrete security of the scheme under revision, are summarised here and analysed in detail in a companion paper. The survey closes with open questions and a scenario-planning checklist that requires a complete efficient reduction.

1 Introduction

This introduction frames a counterfactual survey of what specified efficient dihedral solvers imply through known reductions, emphasizing parameter, sample, preparation, and success conditions while distinguishing sufficient consequences from deployed-scheme attacks. It also guides readers through the survey and defines notation for problem variants, reduction bounds, and conclusion classifications.

1.1 Post-quantum cryptography and the place of LWE

  • LWE’s worst-case-to-average-case connection and versatility help explain its role in lattice cryptography, including ML-KEM and ML-DSA.The introduction situates the survey among post-quantum standards and prior quantum and lattice surveys, then outlines explicit reduction compositions, structured-state auditing, assumption comparisons, and open questions.Source: §1.1 · p. 3, §1.2 · p. 4, §1.6 · pp. 9–10

1.2 Previous surveys and research context

  • The survey’s contribution is a selective parameter-and-assumption audit of solver domains, samples, state preparation, success losses, and concrete embedding promises, not a priority claim for known reductions.It treats the structured connection of as a reduction to audit and distinguishes heuristic comparisons from concrete attack-estimation literature.Source: §1.2 · pp. 4–5

1.3 The Simon episode

  • The August 2026 Simon preprint claimed a polynomial-time DCP solver, but published counterexamples and formal analyses found its specified algorithm's information-retention and adaptive-selection steps insufficient.The October 2026 response invoked post-selection, but the cited bound covers processing of the retained state and allows at most an inverse-acceptance-probability increase in distinguishing advantage.Source: §1.3 · pp. 6–7

1.4 Why a counterfactual survey

  • The survey compares noiseless cyclic, prescribed-failure, and extrapolated-state hypotheses, whose quantitative requirements and routes are distinct.Regev’s rare-corruption observation makes the noiseless hypothesis sufficient for some polynomial-factor lattice algorithms, while a prescribed failure exponent determines quantitative bounds; the extrapolated-state route remains separate. The survey records sufficient guarantees and limitations, not a prediction or migration recommendation.Source: §1.4 · p. 7

1.5 Summary of results

  • The three solver hypotheses yield distinct, parameter-qualified lattice consequences, but the analysed routes do not certify attacks on the deployed instances discussed.Under HReg(f), the stated guarantees include GapSVP at eO(n^(1+2f)), SIVP at O(n^(3/2+2f)), and sample-dependent SIS results; HHS gives these for some solver-dependent f. The restricted HEDCP[ℓ] route has explicit sample and preparation requirements and gives SIVP and SIS guarantees of about n^3 and n^(5/2), up to logarithmic factors. Standard-noise LWE and several other lattice and non-lattice assumptions have no certificate from these compositions; these limits are not security proofs or measured margins.Source: §1.5 · p. 8
  • The survey also evaluates withdrawn or conditional LWE claims and reports that classical structural attacks have put Classic McEliece’s concrete security under revision.Its analysis places Chen’s withdrawn algorithm [77] and Zhang’s conditional repair [227] within a many-sample, small-noise regime covered by HReg(f) for f < 1/2, but not standard-noise LWE or deployed parameter sets. The companion paper [107] examines the McEliece attacks in detail.Source: §1.2 · p. 6, §1.5 · pp. 8–9

1.7 How to read this survey

  • The survey outlines its notation and reduction statements, while directing readers to primary sources for full proofs, version-specific premises, and algorithmic details.It notes that readers with different aims can follow different paths through the survey.Source: §1.7 · p. 10

1.8 Notation

  • The glossary specifies lattice and LWE/SIS notation, including dimension, sample count, modulus, noise, solution bounds, and ring or module variants.It also defines the survey’s gap notation and heuristic NTRU density ratio, which is not a unique-SVP gap.Source: §1.8 · pp. 10–11
  • The notation distinguishes noiseless, failure-parameter, and extrapolated variants of the Dihedral Coset Problem and names structured EDCP.It also defines the EDCP state count and records a sufficient state-count condition for bounded width and inverse-polynomial success.Source: §1.8 · p. 11
  • Conclusion labels distinguish certified consequences, conditional comparisons or applications, open questions, and connections outside the analyzed reductions.Separate symbols classify rigorous, heuristic, open, and unverified claims, as well as explicit attacks, solvable proof assumptions, and guarantees that are no longer informative.Source: §1.8 · p. 12

2 Preliminaries

This section gathers background needed throughout the survey. It retains details because the counterfactual’s reach depends on classical results’ exact forms, reduction factors, sample use, and quantum-algorithm tolerances.

2 Preliminaries

  • The section collects background used in the rest of the survey.Its length reflects the need to retain details that affect later conclusions.Source: §2 · p. 12
  • The counterfactual’s reach depends on the exact form of several classical results and the approximation factors in worst-case reductions.Source: §2 · p. 12
  • Reduction sample use and quantum-algorithm error tolerance are details that are easy to lose in a summary.Source: §2 · p. 12

2.1 Lattices and Gaussian measures

The section defines lattices and their geometric quantities, then relates the q-ary lattices underlying LWE and SIS. It introduces discrete Gaussian measures and the smoothing parameter as recurring tools in worst-case to average-case reductions.

2.1 Lattices and Gaussian measures

  • A lattice is a discrete additive subgroup generated by linearly independent basis vectors, with determinant measuring its covolume and successive minima recording independent-vector lengths.The first successive minimum is the shortest nonzero vector length.Source: §2.1 · p. 12
  • Discrete Gaussian measures assign coset points weights proportional to exp(−π∥x∥²/s²), while the smoothing parameter marks when a reduced Gaussian is close to uniform.Gaussian measures control sample lengths and independence and form the technical heart of the worst-case to average-case reductions discussed.Source: §2.1 · pp. 12–13
  • The q-ary lattices used for LWE and SIS are dual up to scaling, and their determinants are q^n and q^(m−n) when A has full rank modulo prime q.Source: §2.1 · p. 13

2.2 Lattice problems and their complexity

The section defines the lattice problems used in the survey and gives reductions relating them. It frames approximation factors as the relevant scope of the counterfactual, not as universal hardness bounds.

2.2 Lattice problems and their complexity

  • SIVPγ asks for d independent vectors within γλ_d(L), uSVPγ uses a λ₂/λ₁ gap promise, and BDDδ seeks the closest vector to a point within δλ₁(L).Source: §2.2 · p. 13
  • uSVP, BDD, and GapSVP reduce to one another with losses up to n/log n; in particular, BDD_1/(2γ) reduces to uSVPγ and uSVPγ to BDD_1/γ.These connections supported worst-case GapSVP foundations for two cryptosystems at factors O(n^2.5) and O(n^2), respectively.Source: §2.2 · p. 13
  • Approximation factors shape the problems’ complexity, but cited polynomial-time basis-reduction guarantees are not lower bounds against other algorithms or every structured lattice.The counterfactual asks which polynomial factors follow through the specified reductions.Source: §2.2 · p. 13

2.3 Algorithms and concrete security

The section outlines the algorithm families used in lattice-security estimates and the limits of those estimates. BKZ’s cost model links polynomial approximation factors to large blocks and exponential cost, but is not an algorithm-independent lower bound.

Basis reduction

  • BKZ generalizes LLL by calling an exact SVP solver on projected sublattices, and its standard cost model associates polynomial approximation factors with large blocks and exponential cost.The root Hermite factor decreases slowly with block size; this is a model description, not an algorithm-independent lower bound.Source: §2.3 · p. 14

Exact SVP

  • Exact SVP algorithms range from enumeration and classical or quantum sieving to provable discrete-Gaussian sampling, with different time and memory guarantees.The cited quantum sieve runs in time 2^0.2570d+o(d), while the cited provable algorithm uses time and space 2^d+o(d).Source: §2.3 · p. 14

Estimating schemes

  • Concrete lattice-security estimates model primal, dual, and other attacks, but do not bound algorithms enabled by a future solver.The estimator methodology supports concrete cost estimates; primal attacks use an embedding lattice, while dual attacks use short vectors to distinguish LWE samples from uniform.Source: §2.3 · p. 14

2.4 Learning with Errors

The section presents LWE as both a sample-based problem and a lattice problem, with security depending on parameters such as noise, samples, and secret distribution. It also describes reductions connecting LWE to worst-case lattice problems and its use in encryption.

LWE definition and special parameters

  • LWE samples encode a linear function of a secret with error, and the section treats the number of samples as a security parameter in its own right.Very small errors can make LWE tractable with enough samples, while limited samples support a hardness result for binary errors.Source: §2.4 · pp. 14–15

Secret distributions

  • Under normal-form reduction conditions, LWE with a uniform secret reduces to LWE with a secret drawn from the error distribution, but bounded deployed secrets require checking conversion costs.The section notes that precise bounded distributions and sample costs still need to be checked.Source: §2.4 · p. 14

LWE as a lattice problem

  • LWE can be viewed as a closest-vector problem, while short-secret embeddings yield ordinary-uSVP instances only under shortest-vector and separation conditions.The Gaussian-heuristic comparison depends on the embedding parameters and number of samples.Source: §2.4 · pp. 14–15

Regev’s cryptosystem

  • Regev’s encryption scheme uses LWE public-key samples, subset sums for bit encryption, and decision-LWE for semantic security.Correctness relies on the accumulated error remaining small.Source: §2.4 · p. 15

Worst-case hardness

  • Regev’s theorem reduces efficient LWE solving, for αq > 2√n, to efficient quantum algorithms for worst-case SIVP and GapSVP within eO(n/α).The proof alternates a classical LWE-based BDD step with a quantum step that narrows discrete-Gaussian samples; the quantum step is the only quantum part.Source: §2.4 · p. 15

Related reductions and algorithms

  • LWE reductions cover polynomial-modulus hardness, search-to-decision conversions under specified conditions, and special-parameter algorithms whose feasibility depends on error and sample counts.The cited dimension expansion obtains polynomial-modulus hardness at a larger dimension; quantum search-to-decision for prime q uses two distinguisher invocations.Source: §2.4 · p. 15

2.5 The Short Integer Solution problem

SIS asks for a short nonzero vector in a modular kernel, and worst-case lattice reductions establish its hardness for suitable parameters. The problem underlies lattice-based hashes and signatures and connects to LWE distinguishing.

Definition and existence

  • SIS seeks a nonzero modular-kernel vector of norm at most β, and a solution is guaranteed when β ≥ √m q^n/m by Minkowski’s theorem.The kernel vectors form the q-ary orthogonal lattice.Source: §2.5 · p. 15

Worst-case hardness

  • For q ≥ β·ω(√n log n), SIS is at least as hard as worst-case SIVP within β·eO(√n) factors.The section also records earlier reductions and parameter improvements leading to this form.Source: §2.5 · p. 15

Applications

  • SIS supports lattice hash functions and signatures, including trapdoor-based preimage sampling and trapdoor-free Fiat–Shamir-with-aborts signatures.ML-DSA uses the latter design.Source: §2.5 · p. 16

Connection to LWE

  • The dual-lattice relation links SIS vectors to the dual attack on LWE, but a norm bound alone does not establish a useful distinguisher.The induced error inner product and distinguishing advantage also matter.Source: §2.5 · p. 16

2.6 Algebraically structured variants

Algebraically structured variants encode blocks of LWE data using rings, modules, or other structured algebra. Their reductions and parameter conditions vary, and the direction of a reduction determines which hardness claims it supports.

Ring-LWE

  • Ring-LWE encodes structured scalar samples in ring elements and has worst-case lattice reductions for search and decision variants under their respective conditions.The cited reductions cover ideal lattices for search Ring-LWE and, with theorem-specific error requirements, decision Ring-LWE over any number field and modulus.Source: §2.6 · p. 16

Module-LWE and Module-SIS

  • Module-LWE interpolates between Ring-LWE and LWE, and ML-KEM and ML-DSA use Module-LWE over a power-of-two cyclotomic ring with small module ranks.The section also cites worst-case reductions on module lattices and a rank-dependent reduction from Module-LWE to Ring-LWE.Source: §2.6 · p. 16

Other structured variants

  • Middle-Product LWE, Order-LWE, and related structured assumptions have reductions with parameter and algebraic conditions that determine the direction of hardness transfer.The cited results include a unified framework for algebraically structured variants; the reductions described establish hardness at least as strong as Ring-LWE, not that these variants are easier.Source: §2.6 · pp. 16–17

Short distributions and rounding

  • Results for short Module-LWE secrets or errors require specific rank and sample conditions, while LWR replaces random error with deterministic rounding.The cited bounded-error result requires sample counts close to the module rank; LWR hardness depends on q/p exceeding the LWE error sufficiently.Source: §2.6 · p. 17

Advanced assumptions

  • Succinct and decomposed LWE strengthen LWE for advanced primitives, while Continuous LWE has a worst-case lattice hardness reduction and a classical reduction from LWE.The decomposed and succinct assumptions are equivalent under appropriate parameters, and an LWE solver breaks decomposed LWE only through the proved reduction.Source: §2.6 · p. 17

2.7 NTRU

NTRU key recovery is a short-vector problem in a rank-two module lattice, while its decision version connects to search Ring-LWE through a lossiness argument. The section distinguishes this connection from other NTRU reductions and parameter-specific attacks.

NTRU key recovery

  • NTRU key recovery seeks the short pair (f, g) in a rank-two module lattice, where ring rotations create additional short vectors and ring-dependent uniqueness bounds.The ratio gh(Lh)/∥(f, g)∥ = Θ(√q/σ) measures how much shorter the key is than a typical lattice vector.Source: §2.7 · p. 17

NTRU variants

  • Stehlé and Steinfeld’s Gaussian-key NTRU variant has a public key statistically close to uniform, making its ciphertexts Ring-LWE samples and reducing security to Ring-LWE.Source: §2.7 · p. 17

Decision NTRU and Ring-LWE

  • Decision NTRU reduces to search Ring-LWE through lossiness, but composing this connection with a dihedral solver requires matching sample count, secret and error distributions, and success probability.The relation hf − g = 0 is homogeneous and is not a sample from the standard Ring-LWE distribution.Source: §2.7 · p. 18

NTRU reductions

  • Worst-case approximate SVP on ideal lattices reduces to an average-case search variant of NTRU, while another average-case search variant reduces to decision NTRU.Source: §2.7 · p. 18

Parameter-specific attacks

  • For certain large-modulus NTRU families, the norm map enables lower-dimensional key-recovery attacks, and dense sublattices improve lattice reduction beyond expectations.NTRU Prime uses a prime-degree field with a large Galois group to avoid exploitable algebraic structure.Source: §2.7 · p. 18

2.8 Hidden subgroups, dihedral cosets and hidden shifts

This section relates hidden-subgroup and hidden-shift problems to dihedral coset states, then surveys algorithms and reductions connecting those states to lattice problems and LWE. The resulting consequences depend on solver conditions, parameters, and available state or sample counts.

The hidden subgroup problem

  • For finite groups, coset states contain enough information to identify a hidden subgroup, though extracting it may take exponential time; abelian groups admit polynomial-time Fourier-sampling methods.For non-abelian groups, weak Fourier sampling suffices for normal subgroups, while strong sampling helps for some groups and fails for others.Source: §2.8 · p. 18

Kuperberg’s sieve

  • Kuperberg’s sieve combines labeled qubits to zero low-order bits until the label reveals secret parity, solving noiseless cyclic DCP in subexponential resources.The algorithms use 2^O(√log N) time; Regev’s polynomial-space variant has an additional √log log N factor in the exponent [200], and the algorithms consume a subexponential number of coset states [200].Source: §2.8 · pp. 18–19

DCP with failure parameter

  • DCP with failure parameter f tolerates a fraction of arbitrary bad registers, and a solver yields uSVP_γ with γ = Θ(n^(1/2+2f)) [199].An algorithm solving a 1/poly(log N) fraction of legal subset-sum instances yields DCP_f with f = 1, and thus a reduction for Θ(n^2.5)-unique-SVP [199].Source: §2.8 · p. 19

Extrapolated DCP

  • EDCP generalizes DCP states to superpositions over multiple secret multiples, with uniform and Gaussian amplitude functions as its main instantiations [61].For n = 1 and support {0, 1}, EDCP is DCP without bad registers.Source: §2.8 · p. 19

LWE and EDCP

  • Quantum polynomial-time reductions connect LWE and EDCP, but the forward conversion’s sample range, state count, and width conditions constrain which LWE parameters are covered [61].The conversion from LWE uses m = Ω(κ) samples; its proof restricts m, and the ℓ output states must all be valid. Conversely, ℓ Gaussian EDCP states yield ℓ LWE samples under stated width conditions.Source: §2.8 · p. 19

Structured EDCP connections

  • Wen and Zheng extend the connection to Module-LWE through IP-M-EDCP, which reduces to plain EDCP; the first ordinary EDCP output has modulus qd + 1.The printed forward bound supplies no ML-KEM certificate; cited quasi-polynomial EDCP algorithms require more samples than the reductions provide and do not apply to deployed moduli.Source: §2.8 · p. 20, Figure 1 · p. 21

Hidden shifts

  • Coset sampling reduces abelian hidden shift on Z_N to DCP, but the converse is unknown; generalized hidden shifts connect conceptually to EDCP [61, 80].For generalized hidden shift with M = N^ε, Childs and van Dam gave a polynomial-time algorithm for fixed ε > 0 [80].Source: §2.8 · p. 20

Map of relations

  • The figure maps reductions from lattice problems through dihedral coset problems to hidden-subgroup and hidden-shift problems, with tags denoting solver hypotheses and parameter-qualified connections.Its structured edges do not imply a certificate at ML-KEM parameters, and the HEDCP tag covers only its stated polynomial-modulus Gaussian domain.Source: §2.8 · pp. 20–21, Figure 1 · p. 21

3 The claimed algorithms: strategy and status

This section reconstructs ’s proposed replacement for Regev’s subset-sum uncomputation and assesses challenges to it, including whether the October 2026 response addresses them. It also considers the unresolved adaptive-choice issue, the scope of the formal refutation, and Chen’s withdrawn direct-LWE claim and Zhang’s conditional repair in a narrow regime already reached by HReg(f) [77, 227].

3 The claimed algorithms: strategy and status

  • The section relies on the October 7 preprint and analyses that predate that revision; Lean verifies theorems about formal models, while model-to-draft correspondence is argued in natural language.The authors mark their own informal intuition and assessment as such.Source: §3 · pp. 21–22

3.1 The template: Regev’s reduction from DCP to subset sum

  • Regev’s template uses a subset-sum solver succeeding on a 1/poly(log N) fraction of instances to enable uncomputation and solve DCP, but such modular subset sum is not known to be easy [199, Thm. 1.3].The template prepares a superposition, partially measures the subset sum, and coherently removes selection bits before reading a bit of the hidden shift.Source: §3.1 · p. 22

3.2 Simon’s strategy

  • [214] replaces Regev’s subset-sum uncomputation with certified reversible erasure, consuming at least kn^13 coset states per output bit and repeating polynomially for each bit.The draft claims SVP approximation √n polylog(n) and LWE with α = √n polylog(n), but its LWE route requires extrapolated states; it names no deployed parameter set [214].Source: §3.2 · pp. 22–24

3.3 Why the strategy does not work

  • For [214]’s digest size, bounds distinguishing opposite-least-significant-bit secrets by Q · 2^-n/3, ruling out both claimed efficiency and correctness within its observation model.The refutation corollary allows arbitrary post-processing, including retries, adaptive stopping, and majority votes.Source: §3.3 · p. 25
  • The audit corrects Lemma 1’s constant-probability claim, leaves Lemma 3 unrepaired for the paper’s polynomial-time algorithm, and records Lemma 4 as unproved, not refuted.The published swap can change the contribution from 1 to 5 modulo 128 at n = 8; the corrected proof is formalised in Lean for n ≥ 1024, k = 24, c = 12.Source: §3.3 · p. 26

3.4 The author’s response of October 2026

  • The October note argues post-selection makes desired outcomes likely overall, but ’s channel bound already covers post-selection and transfers to the exact procedure, so the response does not remove the barrier [120, 121, 214].The response does not address the main theorem’s bound for every channel applied to the digest-restricted state [121, 214].Source: §3.4 · pp. 28–29
  • Conditioning on acceptance can amplify distinguishing advantage by at most the inverse acceptance probability; larger gains require exponentially rare events and exponentially many expected samples.The audit estimates acceptance at order 1/n and no bias for its two-copy calculation, pending a guard estimate.Source: §3.4 · p. 29
  • The response asserts without proof that adaptively choosing A matches preselection; that choice conditions on B, excluded by Hypothesis (U) [119], and conflicts with the claimed correctness at acceptance probability Ω(1/n).The clarified Lemma 3 does not resolve the issue, and the revision leaves the audit’s findings unchanged.Source: §3.4 · pp. 29–30

3.5 What the failure teaches

  • Within the coordinatewise-digest model, a digest retaining a third of each label leaves advantage at most Q · 2^-n/3; non-negligible advantage requires retaining all but O(log n) bits.This constrains the uncomputation step in Regev’s template but does not refute DCP beyond the specified observation model.Source: §3.5 · p. 30
  • Adaptive measurements require adaptive analyses, and post-selection on a non-negligible-probability event cannot create substantial information; formal bounds verify specified models, not their correspondence to the draft [119].The Lean developments verify stated bounds and some lemma-level arguments, while translating those models to the draft remains informal.Source: §3.5 · p. 30

3.6 Chen’s LWE algorithm and a proposed repair

  • Zhang’s post-processing would solve Chen’s chosen-secret instance only if a retuned front end meets its conditions and supplies run-dependent offset information, which the paper does not show how to obtain [227].The rebuttal disputes earlier pair-shift and evaluator steps; the eighth version replaces them with oracle side information, and neither paper nor rebuttal has been peer reviewed.Source: §3.6 · pp. 31–32
  • Chen’s and Zhang’s claims target many-sample, small-noise LWE, not a dihedral problem; no known reduction derives HHS, HReg(f), or HEDCP[ℓ] from such an LWE solver.The known general route to extrapolated states runs in the converse direction and covers only widths r ≥ eΩ(N^3/4ℓ^1/2), whereas HEDCP[ℓ] requires every r ≥ r0.Source: §3.6 · p. 33
  • For m ≥ 2n lg q, prime q, and β ≥ 1, Chen’s LWE regime lies within HReg(f) for every f < 1/2, whose lattice guarantees are stronger than Chen’s n^4.5-factor corollary.At the corollary’s parameters, HReg(f) applies for f < 5/4; under HEDCP[ℓ], the certified scale exceeds the corollary’s noise level when ℓ ≤ n^5/2/polylog(n).Source: §3.6 · p. 33
  • Chen withdrew the polynomial-time claim, and Zhang’s repair remains conditional on an unverified front end and offset side information; neither reaches deployed parameter sets [77, 227].Chen’s sample-count and noise conditions fail for ML-KEM and FrodoKEM, and the corrected regime adds no consequence beyond instances already reached under HReg(f) for f < 1/2.Source: §3.6 · pp. 31, 34

4 The counterfactual hypotheses and their reach

This section formalizes three counterfactual DCP solver hypotheses and gives conditional compositions to lattice and LWE-type tasks, making parameter, sample, success, and state-preparation requirements explicit. It distinguishes the guarantees and quantitative limitations of the different routes—including heuristic estimates—from actual solver behavior, without treating uncertified parameters or failed comparisons as evidence of a converse or measured security margin.

4.1 Three hypotheses

  • If a noiseless cyclic solver uses O(L^a) registers and succeeds with probability at least cL^−b, it establishes HReg(f) for every fixed f > a + b.Here L = max{1, log2 N}; the conclusion follows from the tensor-product hybrid bound for corruption probability at most L^−f and is Regev’s rare-corruption observation [199, Cor. 1.2].Source: §4.1 · pp. 34–35
  • A noiseless cyclic coset-state solver implies HReg(f) for some solver-dependent f, and HReg(f) implies HHS; no additional implication involving HEDCP is established.HReg(f) prescribes per-register corruption at most (log N)^−f, while HEDCP concerns polynomial moduli and Gaussian widths at least r0. The qualitative HReg–HHS equivalence does not give a solver-independent value of f.Source: §4.1 · p. 35
  • The extrapolation lemma converts ℓ nearly balanced two-point states into EDCP states using O(ℓ/πρ) samples, with success at least p − 2^−Ω(ℓ).For Gaussian inputs truncated at |j| ≤ tr, the stated conditions give πρ ≥ 1/2 and ε ≤ 3eπt/r when r ≥ 7t; the cyclic-to-vector-group translation remains unresolved. Efficient injective functions also prepare polynomially many noiseless DCP registers for hidden shift.Source: §4.1 · p. 36

4.2 Regev’s reduction from unique-SVP to DCP

  • Regev’s reduction maps unique-SVP to DCP with Θ(n^1/2+2f)-unique-SVP using balls, and its subset-sum connection yields a Θ(n^2.5) worst-case-to-average-case reduction.The reduction needs tolerance to bad registers and applies to ideal and module lattices satisfying ordinary uniqueness; its cube-based bound is Θ(n^1+2f).Source: §4.2 · p. 37

4.3 Technical lemmas

  • The lemmas give classical, polynomial-time, dimension-preserving reductions from BDD_{1/(2γ)} and GapSVP_{γ′}, where γ′=O(γd/log d), to uSVP_γ, while Regev’s quantum step converts qualifying dual-lattice decoders into primal Gaussian samplers.Regev’s worst-case reduction assumes αq > 2√n and an efficient search-LWE solver for every α′ ≤ α using polynomially many samples. The decoder-to-sampler step requires the stated radius, success, and coherent-implementation conditions.Source: §4.3 · pp. 38–39
  • The coherent decoder and randomized-rounding lemmas control output quality through decoder error and bound the rounding distribution’s statistical distance from a discrete Gaussian by 2ε.The decoder result applies when its error probability is at most ε on every target within the specified distance of the dual lattice.Source: §4.3 · p. 40

4.4 The reach theorem

  • Under HReg(f), unique-SVP, BDD, GapSVP, and SIVP have quantum polynomial-time algorithms at solver-dependent approximation factors, in the worst case over lattices.The results apply to ideal and module lattices as well as general lattices; the HHS corollary also yields these problems at some polynomial factors.Source: §4.4 · pp. 41–42
  • Under HReg(f), search-LWE is solved for m ≥ 2n lg q and α ≤ αReg(m), while SIS is solved for m ≥ 2n lg q and β ≥ βReg(m), subject to matrix exceptions.For m = Θ(n log q), the stated LWE noise scale is α ≤ 1/eO(n^(1+2f)); at β ≥ βReg(n), the cited SIS worst-case hardness premise is unavailable under the reduction’s conditions.Source: §4.4 · p. 41
  • Under HEDCP[ℓ], search-LWE is solved with inverse-polynomial probability when q ≤ poly(n), m ∈ Mq(n), and α < αE(n,m,ℓ), with largest certified bound α < 1/eO(ℓn).For ML-KEM’s q = 3329 and n = 768, Mq(n) consists of roughly 1.35n ≤ m ≤ 5n; the restricted-ball composition certifies only α ≈ n^-2, γ ≈ n^3, and β ≈ n^(5/2), up to polylogarithmic factors.Source: §4.4 · p. 41
  • Under HHS, hidden shift is solved for qualifying free and transitive cyclic actions, and the generalized hypothesis extends the result to free and transitive abelian actions.The action size and generator must be known, and the action evaluation must be quantum-polynomial-time with public or efficiently recoverable inputs, consistent encodings, and polynomial total cost.Source: §4.4 · p. 42

4.5 Proofs of the compositions

  • Under HReg(f), SIVP has a quantum polynomial-time algorithm returning n independent vectors of length at most γ⋆Reg(n)λn(L), except with probability 2^-Ω(n).The proof composes a reliable bounded-distance decoder with discrete-Gaussian sampling and selects independent short vectors.Source: §4.5 · p. 43
  • Under HReg(f), SIS with prime q and m ≥ 2n lg q yields a nonzero short lattice vector for all but a q^-n fraction of matrices.The composition samples from a dual-lattice Gaussian and uses a decoder whose success probability is amplified to control error.Source: §4.5 · p. 43
  • Under HEDCP[ℓ], search-LWE secret recovery has inverse-polynomial success for m samples when α < αE(n,m,ℓ), with the proof accounting for preparation precision and solver success.The analysis bounds preparation and implementation errors relative to the solver’s inverse-polynomial success, and uses fixed inverse-polynomial precision targets.Source: §4.5 · p. 44
  • The ℓ factor in the noise bound cannot be absorbed into a constant: at fixed width and inverse-polynomial success, the information-theoretic sample lower bound is ℓ ≥ (n log N − log(1/p))/(2 log(1 + r)).The bound applies to algorithms receiving ℓ G-EDCP states with uniformly random secret and independent uniformly random offsets.Source: §4.5 · p. 45
  • Under admissibility conditions (B1)–(B3), the ball reduction’s sufficient noise bound is at most 1/(2r0κℓm); this calculation certifies a largest noise scale at most 1/eΩ(n2).Source: §4.5 · p. 46
  • Under HEDCP[ℓ], the composition gives worst-case BDD1/gE in BQP and solves SIVP within eO(ℓn^2), while SIS is solved for β > βE(n, m, ℓ).The SIS guarantee requires the stated modulus, sample-count and βE < q/2 conditions; its success probability is at least 1/poly(n) over a uniform matrix and internal randomness.Source: §4.5 · p. 46

4.6 The sample-count obstruction

  • Both LWE routes require many more than n samples, whereas the cited passive ML-KEM and ML-DSA public-key instances provide about n samples under a secret.The passage says no additional independent samples under the same secret are assumed in this passive setting; interactive access or auxiliary keys need separate analysis.Source: §4.6 · p. 49
  • The affine-embedding gap estimate is heuristic, requiring the planted vector to be shortest and its gap to match the estimate; a result below the comparison bound is inconclusive.For τ comparable to σ, the estimate agrees to first order with qm/D divided by σ√(2πe), under the stated logarithmic-growth condition.Source: §4.6 · pp. 49, 51
  • At m = n, the restricted ball construction supplies no certificate, and even its width bound implies polynomially many states are 2^-Ω(n)-close to states independent of s.The theorem's admissible sample set excludes m = n; at these parameters its width is below 1/(c√n κℓ).Source: §4.6 · pp. 49, 51
  • At m = n, comparing the first-order gap estimate with Γf,A(2n + 1) gives only a heuristic sufficient test; ML-KEM heuristic normalised gaps are about 0.3–0.4, and the printed structured bound certifies none at its ring and modulus.A finite-dimensional bound and the actual embedding promise remain necessary for a rigorous certificate.Source: §4.6 · p. 51
  • The two analysed unstructured constructions lose a factor qn/m in sufficient noise guarantees, and more samples alone do not certify the standard Regev and dual-Regev noise rate even at m = Θ(n log q).Structured embeddings still require their actual gap and distribution promises.Source: §4.6 · p. 51

4.7 The window outside the reach

  • Theorem 4.17’s lattice routes require their stated gap or approximation-factor guarantees, and HHS or HEDCP[ℓ] compositions require solver-dependent bounds or their own sample, distribution, and gap conditions.Failure to certify an instance gives no converse about solver behavior; the “window outside the reach” is not a measured security margin, and solving a SIS proof assumption is distinct from forging a signature.Source: §4.7 · p. 51

4.6 The sample-count obstruction

  • For ML-KEM-type parameters, the public-key and compressed-ciphertext comparisons are about 0.4 and 0.3, while the model curve crosses one near m = 1.85n; none certifies actual gaps or attacks.The ML-DSA-type value is about 11 only in the separate full-t scenario, while the published-key estimate is about 0.3.Source: §4.6 · p. 51, Figure 5 · p. 52

4.7 The window outside the reach

  • Conditional application panels require their instance or preparation certificates, while the ordinary-EDCP solver in the structured panel has exponential modulus in the ring degree, not supplied by the polynomial-modulus hypothesis.The dual-decoding and Gaussian-sampling routes do not follow by reversing a worst-case-to-average-case hardness reduction, and the research-question boxes assert no additional reduction.Source: §4.7 · p. 52

5 The Wen–Zheng route: recovered map and audited scope

The section separates an exact structured-state conversion from a restricted forward construction: its printed certificate gives no feasible width at the ML-KEM ring and modulus, while the adapter still needs a complete audit.

Forward construction premises

  • The forward theorem assumes power-of-two d=poly(κ), constant k, m=O(log κ), an unramified prime q, and specified Gaussian inputs and prime-ideal norms.Bounded, centred-binomial, compressed, or rounded inputs require separate conversion; the invoked regularity argument requires m>k.Source: §5 · pp. 52–53

Preparation and success conditions

  • The preparation guarantee requires negligible individual trace error and constant joint good-branch probability; composed recovery succeeds with probability at least cp−ε.Errors must be budgeted against both L and the target solver's success probability p.Source: §5 · p. 53

Exact state conversion

  • Measuring an ideal product-amplitude IP-M-EDCP state yields one ordinary EDCP state of dimension k, modulus Q, and the same secret, preserving state count and not increasing trace distance.The construction works for every secret and arbitrary offsets, independently of the secret distribution.Source: §5 · p. 53

Coset-state solver route

  • For polynomially bounded R bounded below by a positive constant, the two-point filter yields a noiseless coset state with heralded probability at least 1/poly(kd log q).A solver needing J registers requires O((J+log(1/δ))/pR) ideal EDCP preparations to obtain them except with probability δ.Source: §5 · p. 54

Polynomial-modulus adapter

  • The proposed polynomial-modulus adapter has additional width and sample requirements, and its fixed ledger does not explicitly propagate invoked routines' sample overheads.The source-stated route therefore still needs a complete search, width, success, and sample audit before supporting an HEDCP[ℓ] consequence.Source: §5 · pp. 52–54

Forward certificate audit

  • At d=256, q=3329, k∈{2, 3, 4}, C≥8, and L≥1, the printed certificate has no feasible positive width for any t.Even the most permissive tested case, k=2 and L=1, gives Amax<0.009217.Source: §5 · p. 54

Many-sample route

  • The many-independent-sample route avoids amplification but retains the modulus, state-count, width, and distribution conditions, and the ML-KEM obstruction remains.States generated from the same input do not count as additional independent ring samples.Source: §5 · p. 55

6 Consequences for the LWE family

The section compares sufficient DCP-based guarantees with LWE-family assumptions and cryptographic instances, while requiring each route's sample, distribution, and embedding promises. It finds no deployed-parameter certificate for the few-sample Module-LWE cases considered.

6 Consequences for the LWE family

  • The classification assigns conclusions only after checking sample counts, noise, matrix structure, and the selected embedding's promises.Under HHS the bounds depend on the solver's witness; heuristic comparisons and unresolved applications are distinguished from rigorous consequences.Source: §6 · pp. 55–56

6.1 Unstructured LWE

  • With sufficiently many samples and sufficiently small noise, the stated theorems certify LWE under HReg(f) and HEDCP[ℓ], but not many-sample LWE at standard noise.For Regev's and the dual cryptosystem parameter regimes, the survey records no attack certificate under the three hypotheses; FrodoKEM's heuristic comparisons remain unresolved.Source: §6.1 · pp. 56–57

6.2 Ring- and Module-LWE

  • Structured-instance conclusions require the actual planted-vector and gap promises; the audited Wen–Zheng certificate supplies no deployed attack certificate.The Module-LWE-to-Ring-LWE heuristic comparison does not improve the displayed gap estimate, and the cited worst-case reductions do not themselves provide reverse-direction algorithms.Source: §6.2 · pp. 57–58, §6.3 · p. 59

6.3 Middle-product, order-based and unified variants

  • The reviewed middle-product and order-based hardness reductions do not supply reverse-direction algorithms, and no additional EDCP-based certificate is established for these variants.Any future structured reduction requires its own parameter and state-preparation audit.Source: §6.3 · pp. 58–59

6.4 Rounding, short secrets and strengthened assumptions

  • For unstructured LWR with m≥2n lg q, the stated BDD gap is p/(2√m), and the theorem solves it when p≥4√m γu(m+1).Structured Module-LWR needs an instance-specific embedding check; shorter secret and error widths improve the stated heuristic gap, while discrete-secret CLWE transfers only when its LWE output is in reach. Transfers for strengthened assumptions require matched parameters and access models.Source: §6.4 · pp. 59–60

6.5 Search, decision and quantum auxiliary states

  • Search-to-decision and quantum auxiliary-state connections transfer algorithms only with their stated reduction parameters, oracle interfaces, distributions, and resource conditions.The surveyed connections do not give a DCP-based algorithm for SIS at signature-sized norm bounds.Source: §6.5 · p. 60

6.6 Advanced primitives

  • The illustrative FHE public-key gap is much larger than the model d^(1/2+2f), but this is conditional and does not classify all FHE parameters.Evaluation and bootstrapping keys cannot automatically be counted as independent LWE samples.Source: §6.6 · p. 60

6.7 Consequences for the lattice standards

  • For the few-sample Module-LWE standards considered, the unstructured routes and printed structured certificate provide no deployed-parameter attack certificate.ML-KEM fails the printed width test; ML-DSA's full-t rows are a separate conditional scenario, and solving its Module-SIS proof assumption alone does not yield a forgery. FN-DSA also fails the ordinary-uSVP promise.Source: §6.7 · pp. 61–62

7 Other lattice assumptions: reach and limitations

This section examines the reach and limitations of DCP-based reductions for SIS, unstructured CVP-based encryption, and NTRU. It reports no certified deployed NTRU or LIP attack from the reductions considered, treats deployed-parameter gap estimates as conditional comparisons rather than attack thresholds, and distinguishes these limits from a structural Hawk attack and the scope of the heuristic embedding analysis.

7.1 SIS and Module-SIS

  • Under stated conditions, SIS is solved above βcol, its worst-case premise is unavailable from βvoid to βcol, and below βvoid neither guarantee is reached.Under HReg(f), the displayed thresholds are βReg(m) = O(m^(3/2+2f)) and βvoid = eO(n^(1+2f)); under HEDCP[ℓ], they coincide up to polylogarithmic factors. These comparisons are sufficient guarantees, not finite-dimensional boundaries or evidence of hardness below them.Source: §7.1 · pp. 62–64
  • Solving SIS at a scheme’s proof parameters makes its hardness premise unavailable, but does not itself yield a forgery or other scheme break.The section classifies this as kind (B), distinct from an explicit attack; homogeneous SIS solutions need not provide the inhomogeneous hashed-target preimage required for a forgery.Source: §7.1 · p. 64
  • The modeled Falcon sampler exceeds its proof’s SIS norm bound even at γu = 1, while Module-SIS comparisons are heuristic and uniform-matrix bounds do not certify structured instances.The norm estimate is not an impossibility result or a bound on useful-output probability; neither this comparison nor the audited route establishes a deployed-key attack or forgery.Source: §7.1 · pp. 64–65

7.2 Unstructured CVP-based encryption

  • GGH decryption has a small-constant BDD gap rather than a large polynomial uSVP gap, leaving it outside these reductions despite its history of classical breaks.Nguyen decrypted challenge ciphertexts in dimensions up to 350; GGH-type encryption has no worst-case foundation, and its signatures also suffered classical key-recovery attacks.Source: §7.2 · p. 66

7.3 NTRU and NTRU Prime

  • NTRU key rotations obstruct the direct ordinary-uSVP route: Falcon’s cyclotomic keys have λ2 = λ1, while NTRU Prime has λ2 ≤ 3λ1.The stated route is excluded above factor 1 for Falcon and above factor 3 for NTRU Prime; ordinary Euclidean uniqueness differs from module uniqueness, and density ratios are not uSVP gaps.Source: §7.3 · pp. 66–67
  • Decision NTRU has conditional gap-based and lossiness routes through search Ring-LWE, but the stated sample and width requirements are not certified for deployed parameters.The lossiness connection neither treats (h, 0) as an ordinary Ring-LWE sample nor recovers an NTRU key; the subfield attack also supplies no fresh lower-dimensional Module-LWE sample with controlled additive error.Source: §7.3 · pp. 67–68
  • For a single NTRU public key, the reduction supplies only t = 1; its sufficient width yields a decision distinguisher, not denominator recovery.If each ∥g_i∥≤B0, the sufficient width is w ≥ 2πtB0; a short-relation promise holding with probability 1 − η costs at most η in advantage. Deployed NTRU key recovery and decryption are not established under the three hypotheses; the ordinary-uSVP obstruction is exact for power-of-two cyclotomics and excludes factors above 3 for NTRU Prime.Source: §7.3 · pp. 68–69

7.4 The Lattice Isomorphism Problem

  • LIP-based schemes include constructions by Ducas and van Woerden and Hawk, but the cited limits provide no general attack certificate.For rotations of Zn, all successive minima are equal, so there is no ordinary-uSVP promise above one; a polynomial-factor SIVP guarantee alone does not recover an exact isometry. These observations concern this class, not all LIP instances.Source: §7.4 · p. 69
  • Hawk’s reported key-recovery attack reduces to exact SVP in dimension n/2+1, not automatically to the polynomial-factor lattice guarantees considered here.It targets module algebraic structure rather than LIP itself; the reported cost estimates fell from 2^150 to 2^108 for Hawk-512 and 2^288 to 2^182 for Hawk-1024, and a Hawk-256 key was recovered in hours. The submission team withdrew Hawk.Source: §7.4 · p. 69

7.5 Heuristic gaps of deployed parameter sets

  • Table 10 reports conditional first-order heuristic gap estimates and NTRU density ratios, not necessary or sufficient cryptanalytic thresholds.Its embedding has exact dimension n + m + 1, while the table uses D = n + m; finite-dimensional certificates require the actual gap to exceed the bound for a specified failure exponent and witnessing algorithm. The estimates ignore refinements such as sublattice selection, and NTRU density ratios are not ordinary-uSVP gaps.Source: §7.5 · p. 70, Table 10 · p. 71

8 Alternatives outside lattices

This section surveys non-lattice alternatives, asking whether they admit a complete efficient reduction to the assumed coset-state problem and what a DCP counterfactual would imply for isogeny and group-action problems. It also distinguishes scheme-size profiles from security rankings and records the direction and limits of subset-sum reductions.

8.1 Code-based cryptography

  • Binary-group DCP with independent random offsets and maximally mixed corruptions is equivalent to search-LPN at noise rate τ/2, so surveyed reductions certify no attack on McEliece, HQC, or BIKE.The equivalence does not cover adversarial corruptions or establish LPN hardness; reductions to Hamming and rank decoding reach only easy regimes, while Lee-metric transfers require matching the instance’s metric, distributions, and parameters.Source: §8.1 · p. 75

8.2 Classic McEliece: structural cryptanalysis and current status

  • Recent classical structural attacks put Classic McEliece’s independent security evidence under revision, but no full-size key recovery or practical attack has been demonstrated.Conditional structural estimates are lower than Grover-accelerated decoding for the four larger parameter sets and comparable for the smallest; the BSI advises against new deployment and limits its recommendation to hybrid use.Source: §8.2 · pp. 76–77

8.3 Hash-based and symmetric-key signatures

  • Hash-based and symmetric-primitive signatures rely on hash or one-wayness assumptions, but reviewed routes add no DCP hash attack and establish no KEM from those signature premises.SLH-DSA is standardized from hash properties, while Picnic and FAEST use MPC-in-the-head constructions; these signature approaches do not themselves supply a KEM.Source: §8.3 · p. 78

8.4 Multivariate cryptography

  • Multivariate schemes have seen classical structural breaks, including Rainbow key recovery, while the reviewed quantum routes provide no DCP-based attack certificate or multivariate KEM replacement.The Rainbow break took about a weekend on a laptop at security level 1; UOV, MAYO, QR-UOV, and SNOVA remain among the candidates discussed.Source: §8.4 · pp. 78–79

8.5 Isogenies: commutative versus non-commutative

  • For CSIDH-512, class-group hidden shift yields a subexponential quantum benchmark and cyclic-DCP coverage only when coherent evaluation, group, encoding, and public-input conditions hold.The reduction applies to actions with an efficiently available group decomposition and coherent evaluation on arbitrary group elements; the required evaluation inputs must be public or efficiently recoverable.Source: §8.5 · pp. 79–80
  • SIKE was broken classically in 2022 through higher-dimensional isogeny attacks on torsion-point images, without a DCP oracle.Robert extended the attack to polynomial time for every starting curve.Source: §8.5 · p. 80
  • Replacing the hidden-shift subroutine in [50] under HHS or HabHS yields eO(p^1/4) for that composition, not an optimality claim or a bound on every attack.The replacement requires the complete public-input and evaluation conditions.Source: §8.5 · p. 80
  • FESTA and POKÉ use higher-dimensional isogenies constructively, relying on non-commutative problems with controlled torsion information; both remain Outside reach, with young assumptions [33, 32].Source: §8.5 · p. 81

8.6 Equivalence problems and non-abelian group actions

  • Equivalence schemes LESS, MEDS and ALTEQ use non-abelian group actions, but the analyzed reductions give no attack certificate; known Fourier-sampling limits do not prove quantum security.No corresponding proof is known for matrix-code or trilinear-form equivalence; candidate selection alone establishes neither hardness nor a break.Source: §8.6 · p. 81

8.7 Efficiency and concrete security of the alternatives

  • Classic McEliece has a large public key and short ciphertext, HQC a smaller key and larger ciphertext, and FrodoKEM sizes near ten kilobytes; these profiles establish no security ranking.Classic McEliece also needs an independent structural-attack assessment, compared with generic decoding in companion paper [107].Source: §8.7 · pp. 81–82

8.8 Subset sum

  • Subset-sum reductions run in different directions: average-case subset sum yields a DCP algorithm, while sufficiently low-density subset sum reduces to a lattice short-vector problem [199, Thm. 1.3].The first implication does not turn a DCP algorithm into a subset-sum algorithm; subset-sum encryption is classified as Open.Source: §8.8 · p. 82

9 Notes on non-commutative hidden structures

This section surveys non-abelian hidden-subgroup and hidden-shift routes, group-based cryptography, and relaxed dihedral variants. It treats limits on particular measurements as distinct from evidence that an assumption resists every DCP-enabled attack.

9.1 Where the hidden subgroup problem is easy

  • Polynomially many coset states can determine HSP information, but efficient extraction depends on structure: weak Fourier sampling handles normal subgroups, not DCP reflections, while algorithms solve specified families [103, 124, 167, 25, 133, 109, 169].Examples include affine and q-hedral groups, extraspecial groups, and certain structured semidirect products.Source: §9.1 · p. 83
  • A group name alone does not expose a cryptographic problem: a complete efficient reduction must meet the algorithm’s subgroup, presentation, and access promises.The cited HSP algorithms do not solve every problem over their groups or rule out all assumptions defined using them.Source: §9.1 · p. 83

9.2 Limitations of known measurements

  • Known measurement limits are model-specific: single-state measurements yield little information for the specified symmetric-group subgroups, while polynomial-resource entangled procedures require Ω(n log n) registers in that model.The graph-isomorphism problem itself has a classical quasi-polynomial-time algorithm [24]; the passage establishes no general lower bound for matrix-code or trilinear-form equivalence.Source: §9.2 · p. 83
  • Hidden-shift sample lower bounds constrain specified models, not computational hardness or the state budgets of cryptographic reductions [228].For the symmetric group, the cited saturated-case lower bound is Ω(√n log n); infinite-group analogues of lattice problems remain without a proved separation from other dihedral routes [145].Source: §9.2 · pp. 83–84

9.3 Group-based cryptography

  • Non-commutativity alone is insufficient for security: braid-group proposals were broken by classical attacks, and average-case hardness must be assessed independently.Conversely, hash-based and code-based assumptions can lie outside the surveyed hypotheses’ reach without non-abelian structure.Source: §9.3 · p. 84

9.4 Relaxed dihedral problems

  • The dihedral family has relaxed variants with polynomial-time or quasi-polynomial algorithms under particular extrapolation, amplitude, modulus, and sample conditions [80, 79, 27, 58].The direct compositions considered do not match all sample, amplitude, width, modulus, and running-time requirements for the standard LWE regimes examined.Source: §9.4 · p. 84

9.5 Criteria for evaluating alternative assumptions

  • Assess alternatives by checking complete reductions and access requirements, attacks at the intended distribution and parameters, and the primitive needed; formal DCP independence requires a separate model and separation argument.These checks guide assessment but are not necessary or sufficient conditions for DCP resistance.Source: §9.5 · p. 84

10 Future research and conclusions

The closing section identifies open questions, discusses hybrid-design scenario planning, and presents a checklist with worked examples. Its conclusions distinguish sufficient reduction-based guarantees from heuristic comparisons and unresolved applications, and distinguish solving proof assumptions from attacking schemes.

10.1 Open questions

  • The relation from cyclic DCP to vector EDCP remains open, as do few-sample reductions, finite-dimensional factors, and extensions of the stated lattice guarantees.The section also asks whether DCP reaches smaller-norm SIS regimes, whether NTRU admits an EDCP characterization, and how gapless lattice problems relate to promised problems.Source: §10.1 · pp. 85–86
  • Classic McEliece structural attacks need validation on its parameter distributions, including realistic costs and whether small-instance recoveries extend to full-size keys.The questions also cover structured-code attacks and gapless lattice problems; the McEliece methods are classical and Goppa-specific.Source: §10.1 · pp. 86–87

10.2 Hybrid designs

  • Hybrid security depends on component and security-model conditions; pairing schemes alone does not establish a combiner guarantee or independence of assumptions.The section describes lattice-and-code KEM combinations as designs to analyse, not as established secure combinations.Source: §10.2 · p. 87

10.3 Scenario-planning checklist

  • The checklist records sufficient consequences and unresolved premises for each assumption, and a failure to certify a step is not an impossibility result.Its stated purpose is scenario planning and dependency accounting.Source: §10.3 · p. 88, Table 14 · p. 88

10.4 Worked examples

  • Worked examples preserve distinctions between certificates and unresolved checks: ML-KEM's structured certificate has no feasible width, while FrodoKEM's embedding comparison remains unresolved.FN-DSA's ordinary-uSVP promise fails by exact rotational symmetry; CSIDH's cyclic-action route requires complete evaluation and public-input conditions, and SLH-DSA has no established DCP consequence.Source: §10.4 · pp. 88–89

10.5 Conclusions

  • A noiseless cyclic DCP solver would imply lattice algorithms at some polynomial factors, but instance-level guarantees depend on the witnessing algorithm and intervening reduction parameters and promises.The printed structured forward certificate supplies no guarantee for ML-KEM, while several embedding comparisons and a polynomial-modulus adapter remain unresolved.Source: §10.1 · pp. 85, 87, §10.5 · p. 89
  • Chen's withdrawn 2024 LWE algorithm and Zhang's proposed repair, if correct, would reach only a many-sample, small-noise regime covered by HReg(f) for f < 1/2, not deployed parameter sets.The survey also distinguishes solving a proof assumption from demonstrating an attack on a scheme.Source: §10.5 · p. 89
  • The survey's contribution is joint accounting of solver domains, reduction parameters, and evidential status—not new reduction mechanisms or an exhaustive security classification.For NTRU, rotation bounds, the module-uSVP distinction, and lossiness-oracle requirements preclude a blanket key-recovery claim; binary code-based KEMs receive no DCP-based certificate here.Source: §10.5 · pp. 89–90
Loading 2610.36731v1…