Category index
129 variants, organized by problem and scientific regime.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
LWEPrimal embedding · Gaussian errorClassical · Heuristic / model-dependentSearch-LWE through BDD-to-uSVP embedding with a specified empirical gap-to-reduction modelUniform random LWE samples; explicit parameter contract1— LWESmall secret · guessing and lattice reductionClassical · Heuristic / model-dependentSecret guessing followed by a reduced-dimension Gaussian-error lattice attack; distribution and guessed coordinates explicitUniform random LWE samples; explicit parameter contract1— LWESmall secret · rescaled primalClassical · Heuristic / model-dependentBinary or ternary secret with Gaussian error; secret/error scaling and available sample count specifiedUniform random LWE samples; explicit parameter contract1— LWESparse secret · dual reductionsClassical · Heuristic / model-dependentFixed Hamming weight sparse secrets with q, error width, weight and reduction parameters specifiedUniform random LWE samples; explicit parameter contract2— MinRankClassical · specified dimensions and target rankClassical · Model dependentMinRank over F_q with m matrices of size a×b and target rank rSpecified matrix distribution0— MQBoolean · classical · algebraic assumptionsClassical · Conditionalm=n quadratic equations over F_2 satisfying the source algebraic hypothesesAlgebraic regularity assumptions10.792 MQBoolean · classical · worst caseClassical · ProvableDegree at most 2 over F_2; n variables; polynomially many explicitly represented equationsArbitrary Boolean quadratic systems30.6943 MQBoolean · quantum gates · algebraic assumptionsQuantum · Conditionalm=n quadratic equations over F_2; sequential quantum gate complexityAlgebraic regularity assumptions10.462 MQBoolean · quantum mesh · algebraic assumptionsQuantum · Conditionalm=n over F_2; mesh time exponent with an explicit area budgetMesh-connected quantum computation10.45743 MQF_3 · classical · worst caseClassical · ProvableFixed q=3, degree d=2, n variables, explicitly represented equationsArbitrary quadratic systems over F_310.696 MQF_4 · classical · worst caseClassical · ProvableFixed q=4, degree d=2, n variables, explicitly represented equationsArbitrary quadratic systems over F_410.698 MQOverdetermined · algebraic solversClassical · ConditionalQuadratic systems over F_q with fixed m/n > 1; q and density fixedSpecified equation density0— Ordinary isogenyClassical · horizontal isogeniesClassical · HeuristicTwo ordinary curves over F_q with the same cardinality and endomorphism ringSame endomorphism ring10.25 Ordinary isogenyQuantum · GRHQuantum · Conditional on GRHHorizontally isogenous ordinary elliptic curves over F_qSame endomorphism ring10.866025 q-SDClassical · parameterized alphabetClassical · Source asymptotic analysisFix q, R=k/n, τ=t/n and bit-vs-field-operation modelRandom q-ary codes0— q-SDClassical · polynomial memoryClassical · Source asymptotic analysisFix q, R and τ; polynomial workspaceRandom q-ary codes0— Rank-SDClassical · general m/nClassical · Source asymptotic analysisFix q,m/n,k/n,r/nRandom rank-metric codes0— Rank-SDClassical · m = n · worst parametersClassical · Source asymptotic analysisExtension degree m=n; worst decoding parameters in the source conventionRandom rank-metric codes10.1481 RSA factoringBalanced semiprimes · classical heuristicClassical · HeuristicNo special polynomial form, partial factors or weak keys suppliedRSA-type balanced semiprimes21.901884 RSA factoringBalanced semiprimes · quantumQuantum · ProvableLogical quantum computation with polynomial classical post-processingRSA-type balanced semiprimes1— SIDHClassical · known endomorphism ringClassical · HeuristicSIDH with known endomorphism ring of the starting curve; source factorization conditionsSIDH public auxiliary torsion images1— SIDHClassical · polynomial timeClassical · ProvableSIDH key recovery including a random starting curveSIDH public auxiliary torsion images1— SISEuclidean SIS · custom regimeClassical · Regime dependentSpecify q(n), m(n), and the output norm bound β(n)Uniform matrix0— SSIPGeneral curves · classical · heuristicClassical · HeuristicAny explicit isogeny between two supersingular elliptic curves; p→∞Supersingular curves over F_{p^2}20.333333 SSIPGeneral curves · classical · unconditionalClassical · ProvableAny explicit isogeny between supersingular elliptic curves; unconditional asymptotic analysisSupersingular curves over F_{p^2}30.333333 SSIPF_p-rational curves · classical · heuristicClassical · HeuristicFind an isogeny between F_p-rational supersingular curves using small-degree isogeniesBoth curves defined over F_p10.25 SSIPF_p-rational curves · quantum · GRHQuantum · Conditional on GRHQuantum isogeny construction between F_p-rational supersingular curvesBoth curves defined over F_p10.866025 SSIPGeneral curves · quantum · GRHQuantum · Conditional on GRHQuantum explicit-isogeny construction under GRHSupersingular curves over F_{p^2}10.25 SVPConstant approximation · large-factor limitClassical · ProvableFor every fixed ε > 0, some constant μ(ε) yields μ-SVP on arbitrary Euclidean latticesWorst case50.409 SVPEnumeration · superexponential scaleClassical · ProvableExact Euclidean SVP; specify basis reduction and preprocessingArbitrary lattices40.09197 SVPApproximate decision · EuclideanClassical · ProvableEuclidean GapSVP on arbitrary lattices; approximation factor γ is stated per resultWorst case1— SVPHaar-random · quantumQuantum · ProvableHaar–Siegel random determinant-one lattices; specify coherent access and success guaranteeHaar random0— SVPClassical · Haar randomClassical · ProvableExact SVP on Haar–Siegel random unimodular latticesHaar random30.292481 SVPClassical · heuristicClassical · HeuristicEuclidean SVP under sieve heuristicsHeuristic random lists140.292481 SVPIdeal lattices · heuristicClassical · HeuristicExact Euclidean SVP in cyclotomic ideal latticesIdeal lattices10.2972 SVPClassical · ℓ∞ normClassical · ProvableExact SVP on arbitrary rational full-rank lattices; ℓ∞ normWorst case22.443 SVPKissing-constant assumptionsClassical · Conditional theoremFix a uniform kissing/point-counting bound and its exponent β before comparing c(β)Arbitrary lattices0— SVPHeuristic · minimal list spaceClassical · HeuristicExact Euclidean SVP; space ≤ 2^{(½log₂(4/3)+o(1))n}Arbitrary input; heuristic analysis50.292481 SVPClassical · all ℓp normsClassical · ProvableExact SVP on arbitrary rational full-rank lattices; Every fixed ℓp norm, 1 ≤ p ≤ ∞Worst case12.751 SVPClassical · worst caseClassical · ProvableExact Euclidean SVP on arbitrary full-rank latticesWorst case200.409 SVPQuantum · heuristicQuantum · HeuristicQuantum lattice sieving with random accessHeuristic random lists100.2563 SVPHeuristic · quantum · memory ≤ 0.1887nQuantum · HeuristicQuantum SVP; classical and quantum-addressable memory at most 2^{0.1887n+o(n)}Heuristic spherical lists50.2846 SVPHeuristic · quantum · minimal sieve-list spaceQuantum · HeuristicSequential quantum sieving; space ≤ 2^{(½log₂(4/3)+o(1))n}Arbitrary input; spherical-list heuristic50.265257 SVPQuantum · no QRAMQuantum without QRAM · Model dependentExact Euclidean SVP without coherent random access to an exponential classical databaseArbitrary lattices20.95 SVPHeuristic · parallel quantum depthQuantum parallel · HeuristicParallel quantum circuit depth with 2^{0.2075n+o(n)} quantum memoryHeuristic spherical lists10.1037 SVPQuantum · worst caseQuantum · ProvableExact Euclidean SVP; model must be specified per entryWorst case120.2469 SVPHeuristic · triple sievingClassical · HeuristicTriple lattice sieving; compare time and memory jointlyHeuristic spherical lists100.33 UOVUOV · signature forgeryClassical · Regime dependentFix q, oil/vinegar dimensions, target signature model and cost unitRandom UOV systems0— UOVUOV · key recoveryClassical · Regime dependentFix field q and oil-to-vinegar ratio o/vRandom UOV keys0— Filtering applies to this page. Browse a problem to see all its variants.