LWE · BKW · q ≍ n², width ≍ n · unlimited samples

BKW · q ≍ n², width ≍ n · unlimited samples

Uniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); Unlimited fresh samples

2 results · 2 papers

ClassicalProvableUniform random equations2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	An Improved BKW Algorithm for LWE with Applications to Cryptography and LatticesPaul Kirchner · Pierre-Alain FouqueCrypto 2015Source BibTeX / detailsclassical provable LWE BKW	29 Jun 2015	2^{(1/(1/2+2 ln 2)+o(1)) n}	2^{(1/(1/2+2 ln 2)+o(1)) n}	PublishedSource checked
2	On the Asymptotic Complexity of Solving LWEGottfried Herold · Elena Kirshanova · Alexander MayDesigns, Codes and Cryptography 2018Source BibTeX / detailsclassical provable LWE BKW	2018	2^{(2/[2(2−1+1/2)]+o(1)) n}	2^{(2/[2(2−1+1/2)]+o(1)) n}	PublishedSource checked

Comparison definition & assumptions

Regime: Uniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); Unlimited fresh samples
Computation: Classical
Rigor: Provable
Instances: Uniform random equations
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Uniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); Unlimited fresh samples
Comparison rules: Use q=Θ(n²), Gaussian width s=Θ(n), and exactly the displayed asymptotic sample budget. Constant Gaussian normalizations do not change these exponents. These are interior parameters c_q=2,c_s=1; they are not the Regev q≈n²,width≈n^{3/2}/polylog(n) regime.
Tags: BKW, Gaussian noise, sample budget