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

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

Uniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); m=(8+o(1))n original samples

2 results · 1 papers

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

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	On the Asymptotic Complexity of Solving LWEGottfried Herold · Elena Kirshanova · Alexander MayDesigns, Codes and Cryptography 2018Source BibTeX / detailsclassical provable LWE BKW	2018	2^{(1/[2 ln(12/7)]+o(1)) n}	2^{(1/[2 ln(12/7)]+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/[4−2−4/8]+o(1)) n}	2^{(2/[4−2−4/8]+o(1)) n}	PublishedSource checked

Comparison definition & assumptions

Regime: Uniform-secret LWE, prime q=Θ(n²), discrete-Gaussian width s=Θ(n); m=(8+o(1))n original 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); m=(8+o(1))n original 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