Learning With Errors
Recover or distinguish a noisy linear system.
19 variants · 39 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
LWEBKW · Regev · unlimited samplesClassical · Heuristic list modelq ≍ n²; σ = q/(√(2πn) (log₂ n)²); independent fresh samplesLWE distribution60.8917 LWEBKW · Regev · quantum / GroverQuantum · Heuristic list modelq ≍ n²; σ = q/(√(2πn) (log₂ n)²); independent fresh samplesLWE distribution30.8782 LWEBKW · Regev · polynomial samplesClassical · Heuristic list modelq ≍ n²; σ = q/(√(2πn) (log₂ n)²); polynomially many fresh samplesLWE distribution31.6399 LWEBKW · Regev · polynomial samples · quantumQuantum · Heuristic list modelq ≍ n²; σ = q/(√(2πn) (log₂ n)²); polynomially many fresh samplesLWE distribution31.6168 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— 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— 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 · unlimited samplesClassical · ProvableUniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); Unlimited fresh samplesUniform random equations20.53014 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 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— 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— 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 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— LWEFHE range · custom regimeClassical · Regime dependentLarge-modulus LWE; define the q-to-noise and dimension scalingLWE distribution0— LWELWE · custom regimeClassical · Regime dependentSpecify dimension, modulus, error, secret, and samplesLWE distribution0—