Category index
129 variants, organized by problem and scientific regime.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
BDDClassical · basis-relative radiusClassical · ProvableClosest-vector search with distance promised relative to the supplied Gram–Schmidt basisWorst case1— BDDClassical · polynomial query and adviceClassical · ProvablePreprocessed exact decoding; polynomial online time and advice, variable radiusWorst case3— BDDClassical · preprocessing/radius tradeoffsClassical · ProvableReusable exact BDD data structures with explicit decoding radiusWorst case2— BDDClassical · total cost · radius dependentClassical · ProvableExact BDD on arbitrary Euclidean lattices; decoding radius is specified per result and preprocessing is includedWorst case1— LWEBKW · q ≍ n², width ≍ n · 8n samplesClassical · ProvableUniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); m=(8+o(1))n original samplesUniform random equations20.92765 LWEBKW · q ≍ n², width ≍ n · Θ(n log n) samplesClassical · ProvableUniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); Θ(n log n) original samplesUniform random equations20.721348 LWEBKW · q ≍ n², width ≍ n · unlimited samplesClassical · ProvableUniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); Unlimited fresh samplesUniform random equations20.53014 LWEBKW · Regev · polynomial samples · quantumQuantum · Heuristic list modelq ≍ n²; σ = q/(√(2πn) (log₂ n)²); polynomially many fresh samplesLWE distribution31.6168 LWEBKW · Regev · polynomial samplesClassical · Heuristic list modelq ≍ n²; σ = q/(√(2πn) (log₂ n)²); polynomially many fresh samplesLWE distribution31.6399 LWEBKW · Regev · quantum / GroverQuantum · Heuristic list modelq ≍ n²; σ = q/(√(2πn) (log₂ n)²); independent fresh samplesLWE distribution30.8782 LWEBKW · Regev · unlimited samplesClassical · Heuristic list modelq ≍ n²; σ = q/(√(2πn) (log₂ n)²); independent fresh samplesLWE distribution60.8917 CM actionQuantum · cyclic class group · polynomial qubitsQuantum · ConditionalCM action inversion, including CRS/CSIDH, with cyclic class group and source sampling assumptionsCyclic ideal class group1— CVPApproximate search · EuclideanClassical · ProvableApproximate Euclidean search CVP; each result states its factor γ or error parameter δWorst case3— CVPConstant approximation · arbitrary normClassical · ProvableFor every ε > 0, some constant γ_ε approximates search CVP in any normWorst case10.802 CVPConstant approximation · ℓp normsClassical · ProvableFor every ε > 0 and fixed p ∈ [1,∞], some constant γ(p,ε) approximates full-rank CVP_pWorst case10.802 CVPExact · worst caseClassical · ProvableExact Euclidean CVP, arbitrary targetsWorst case21 CVPCVP · Haar-random latticesClassical · ProvableFix the target model, success probability and whether preprocessing is allowedHaar random0— CVPHeuristic · classicalClassical · HeuristicExact Euclidean CVP; include all target-dependent workArbitrary lattice; heuristic spherical-list model20.292481 CVPExact · general ℓp normsClassical · ProvableExact search CVP for every fixed 1 < p < ∞, target in the lattice spanWorst case22 CVPExact · polyhedral normsClassical · ProvableExact search CVP for rational polyhedral norms, target in the lattice spanWorst case12 CVPProvable · polynomial spaceClassical · ProvableExact Euclidean CVP with polynomial workspaceWorst case30.5 CVPExact · polynomial-space query · compact basisClassical · ProvableExact Euclidean CVPP with polynomial-space query computation and an explicitly bounded compactness cWorst case; c-compact basis supplied as advice1— CVPHeuristic · preprocessing query costClassical · HeuristicExact CVPP query time; preprocessing and storage bounded by 2^{n+o(n)}Fixed lattice; arbitrary target20.059 CVPApproximate decision · polynomial adviceClassical · ProvableEuclidean GapCVPP with polynomial-size lattice-dependent advice and polynomial query timeWorst case2— CVPApproximate search · polynomial adviceClassical · ProvableEuclidean search CVPP with polynomial-size lattice-dependent advice and polynomial query timeWorst case3— CVPCVP with preprocessing · query costClassical · ProvableSeparate lattice-dependent preprocessing from per-target query timeArbitrary targets21 DGSAbove smoothing · batch samplingClassical · ProvableDGS above the lattice smoothing parameter; output 2^{n/2} samplesWorst case10.5 DGSClassical · centered · arbitrary width · inverse-polynomial errorClassical · ProvableOne centered sample; (1+1/f(n),2^{-f(n)}) accuracy for polynomial fWorst case20.413 DGSArbitrary width · worst caseClassical · ProvableCentered DGS on arbitrary Euclidean lattices; any positive widthWorst case30.292 DGSClassical · supplied basis · Gram–Schmidt widthClassical · ProvableShifted discrete Gaussian sampling above a supplied-basis widthWorst case1— DGSClassical · supplied basis · parallel onlineClassical · ProvableShifted DGS with width controlled by the basis operator normWorst case1— DGSClassical · q-ary supplied basis · onlineClassical · ProvableShifted DGS over integral q-ary lattices with integral shiftWorst case1— DGSClassical · shifted · distance-relative widthClassical · ProvableShifted Gaussian samples with width above dist(t,L)/f(n)Worst case11 DGSClassical · shifted · above smoothing · 2^{0.2075n} batchClassical · ProvableJointly independent shifted-Gaussian approximation; s >= 3 eta_{1/2}(L)/2Worst case10.292481 DGSClassical · shifted · above smoothing · one sampleClassical · ProvableOne shifted sample at s >= alpha eta_{1/2}(L), fixed alpha > 1Worst case10.292481 Finite-field DLPFixed extension degree · classical heuristicClassical · HeuristicQ=p^n with n fixed and p growingfinite fields of arbitrary fixed extension degree11.922999 Finite-field DLPFixed characteristic · provenClassical randomized · ProvableF_{p^n}, with p fixed; randomized expected timeall extension fields of fixed prime characteristic1— Generic DLPClassical · randomized low storageClassical randomized · Heuristic random-walk modelGroup order r; expected generic group operations; no representation-specific index calculusprime-order cyclic groups10.5 Generic DLPQuantum · abelian groupsQuantum · ProvableCoherent efficient group operations and order information as requiredefficiently represented cyclic groups1— Finite-field DLPPrime fields · classical heuristicClassical · HeuristicNo deliberately supplied special-form modulus; includes full relation generation and logarithm computationgeneral prime fields F_p31.901884 Finite-field DLPPrime fields · quantumQuantum · source dependentLogical circuit and classical post-processing; assumptions stated per paperprime fields1— Finite-field DLPSpecial prime fields · classical heuristicClassical · Heuristicp = r^e − s with r and s small; exploitable representation suppliedspecial-form prime fields F_p11.526286 Finite-field DLPSmall characteristic · heuristic L(1/3)Classical · Heuristicp ≤ n^{o(√n)} in the cited function-field-sieve analysisF_{p^n} with restricted characteristic11.526286 Finite-field DLPSmall characteristic · heuristic expressionsClassical · HeuristicCharacteristic growth and field presentations as specified in each sourcesmall-characteristic finite fields2— Finite-field DLPSmall characteristic · provenClassical randomized · ProvableF_{p^n} with n > p in the cited theoremall finite fields of small characteristic1— ECDLPAnomalous prime-field curvesClassical · ProvableTrace one; p-adic lift techniquescurves E/F_p with #E(F_p)=p1— ECDLPBinary fields · quantum resource boundsQuantum · Provable circuit analysisLogical Toffoli count and logical qubits; scalar-multiplication variant specifiedelliptic curves over F_{2^n}1— ECDLPGeneric prime-order groups · classical low storageClassical randomized · Heuristic random-walk modelGroup order r; rho and negation-map variants; no anomalous-curve promiseprime-order elliptic-curve subgroups10.5 ECDLPGeneric prime-order groups · classical square-root storageClassical · source-dependent average-case analysisGroup order r; baby-step/giant-step variants; O(sqrt(r)) group-element storageprime-order elliptic-curve subgroups10.5 ECDLPPrime fields · quantum resource boundsQuantum · Provable circuit analysisLogical Toffoli count and logical qubits; no physical error-correction overheadelliptic curves over prime fields1— LWEFHE range · custom regimeClassical · Regime dependentLarge-modulus LWE; define the q-to-noise and dimension scalingLWE distribution0— Goppa-KRClassical · conditional concrete estimatesClassical · Conditional estimatesFix parameter set, source version, solver assumptions and memory-cost modelSpecified Classic McEliece parameter sets2— Goppa-SDClassical · public-code decodingClassical · Source analysisFix (n,k,t) or an explicit asymptotic familyBinary Goppa public codes0— IFPGeneral integers · proven deterministicClassical deterministic · ProvableUnconditional deterministic bit complexityarbitrary positive integers40.2 IFPGeneral integers · heuristic · L(1/3)Classical · HeuristicGeneral-purpose factorization; no special low-degree polynomial form suppliedgeneral composite integers31.901884 IFPGeneral integers · heuristic · L(1/2)Classical · HeuristicWorst dependence on N, including balanced semiprimesgeneral composite integers11 IFPGeneral integers · proven randomized · L(1/2)Classical randomized · ProvableUnconditional expected-time bounds; randomness allowedarbitrary composite integers11 IFPQuantum · polynomial-time expressionsQuantum · source dependentLogical circuits plus classical post-processing; conditional and unconditional claims labelled separatelygeneral composite integers3— Small-factor IFPHeuristic · dependence on smallest factorClassical randomized · HeuristicExpected small-factor cost, including polynomial arithmetic overhead in log NN with smallest prime divisor p11.414214 IFPSpecial form · heuristic · L(1/3)Classical · HeuristicN = r^e ± s with r and |s| bounded; polynomial representation suppliedspecial-form composites11.526286 Binary decodingBinary · full GV distanceClassical · Source analysisBinary random linear codes; full Gilbert–Varshamov distance; maximum over ratesRandom binary linear codes100.0885 Binary decodingBinary · half distanceClassical · Asymptotic analysisHalf-distance decoding; worst asymptotic rateRandom binary codes80.0453 Binary decodingQuantum · full GV distanceQuantum · Source analysisQuantum ISD for random binary codes at full GV distance; maximum over ratesRandom binary linear codes70.058326 Binary decodingQuantum · polynomial qubits · full GVQuantum · Source asymptotic analysisFull GV distance; maximum over rates; polynomial quantum workspaceRandom binary codes20.06035 Binary decodingQuantum · R = 0.454 · full GVQuantum · Source asymptotic analysisk/n = 0.454; t/n = H₂⁻¹(0.546) ≈ 0.125869Random binary codes10.057866 Binary decodingQuantum ISD · fixed-rate templateQuantum · Asymptotic analysisSpecify code rate R, relative error weight τ, QRAM access and qubit cost before comparingRandom binary codes0— LPNDecision · fixed noise · unlimited samplesClassical · ProvableDecisional LPN; constant Bernoulli error probability 0 < p < 1/2; unlimited samplesUniform random equations21 LPNClassical · noise probability 1/√nClassical · ProvableBernoulli error probability p = n^{-1/2}; unlimited fresh samplesUniform random equations11.442695 LPNClassical · memory coefficient ≤ 1/2Classical · HeuristicConstant Bernoulli noise; limiting memory coefficient ≤1/2 on the n/log₂n scaleUniform random equations31.807355 LPNClassical · memory coefficient ≤ 2/3Classical · HeuristicConstant Bernoulli noise; limiting memory coefficient ≤2/3 on the n/log₂n scaleUniform random equations21.333333 LPNClassical · fixed noise · polynomial samplesClassical · ProvableConstant Bernoulli noise; n^{1+δ} samples for each fixed δ > 0Uniform random equations1— LPNQuantum · memory coefficient ≤ 1/2Quantum · HeuristicConstant Bernoulli noise; limiting memory coefficient ≤1/2 on the n/log₂n scaleUniform random equations11.637624 LPNQuantum · memory coefficient ≤ 2/3Quantum · HeuristicConstant Bernoulli noise; limiting memory coefficient ≤2/3 on the n/log₂n scaleUniform random equations11.333333 LWEBinary error · conditional algebraic boundsClassical · Conditional: semi-regularityUniform errors in {0,1}, arbitrary secret over an odd prime field; linear and quasilinear sample regimes remain separate parameter contractsUniform random LWE samples; explicit parameter contract2— LWEBinary secret and error · hybrid modelsClassical · Heuristic / model-dependentUniform binary secret and error; exact finite n,m,q and preprocessing cost specifiedUniform random LWE samples; explicit parameter contract2— LWEDecision · binary secret and error · n samplesClassical · ProvableDecisional LWE; both secret and errors uniform in {0,1}; n samples; prime modulus q=Θ(n²)Uniform random equations10.346574 LWEDual lattice · parameterized modelsClassical · Heuristic / model-dependentDecision-LWE with Gaussian errors, with q(n), Gaussian width and sample availability specified per entryUniform random LWE samples; explicit parameter contract3— LWEGaussian error · algebraic boundsClassical · Mixed: theorem / conditionalSearch-LWE over prime fields; arbitrary full secret and explicit Gaussian width, with algebraic sample requirementsUniform random LWE samples; explicit parameter contract3— LWELWE · custom regimeClassical · Regime dependentSpecify dimension, modulus, error, secret, and samplesLWE distribution0— LWELattice decoding · parameterized modelsClassical · Heuristic / model-dependentSearch-LWE through BDD; basis reduction, enumeration parameters and target success probability stay explicitUniform random LWE samples; explicit parameter contract2— Filtering applies to this page. Browse a problem to see all its variants.