LWE / Lattice decoding · parameterized models

Better Key Sizes (and Attacks) for LWE-Based Encryption

Richard Lindner · Chris Peikert

CT-RSA 2011

PublishedSource checked

Time bound: T_reduce(B) + poly(m) ∏_i=1^m d_i
Space bound: Polynomial working space for depth-first search; the ∏d_i output set need not all be retained.

Source / version date: 30 Nov 2010
Comparison variant: Lattice decoding · parameterized models
Cost scale: Parameter-dependent time and space expressions
Parameters: Fix n,q,m,s, reduced basis B and positive integer branching factors d_1,…,d_m.
Error distribution: Continuous Gaussian D_s with density proportional to exp(−π||e||²/s²); wide discrete Gaussian approximated by it.
Secret distribution: General LWE secret; lattice target is As+e mod q.
Sample budget: m given LWE samples; no unlimited-sample substitution.
Objective: Recover the error and secret by lattice decoding.
Cost model: NearestPlanes visits ∏d_i leaves, each polynomial work; include basis reduction in total time.
Assumptions: Success probability formula uses independent Gaussian projections; basis-profile estimates can additionally use GSA.
Success guarantee: P = ∏_i erf(d_i ||b_i*||√π/(2s)); choose d to meet an explicit target P.

Assumptions and source notes

The post-reduction search cost is a tradeoff in the branching vector d. The Gaussian success formula is exact for continuous noise; transferring it to discrete LWE is an approximation. The original empirical BKZ seconds fit is not treated as an asymptotic bound.

Source location

§4, Lemma 4.1, p. 11, and Eq. (4.1), p. 12
Version: Author manuscript dated 30 November 2010

Selected earlier references

Selected sources cited by this paper.

Lattice-based Cryptography
Daniele Micciancio · Oded Regev · 2009
Compares the proposed decoding attack with the earlier dual distinguishing analysis and parameter choices. §1.2 and §4 introductory comparison; reference [MR09]

Primary source ↗

BibTeXDownload .bib

@misc{lindner-peikert2010-lwe,
  author = {Richard Lindner and Chris Peikert},
  title = {{Better Key Sizes (and Attacks) for LWE-Based Encryption}},
  year = {2011},
  url = {https://eprint.iacr.org/2010/613},
  keywords = {LWE, algorithmic complexity, historical literature},
  cr_date = {2010-11-30},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {CT-RSA 2011, LNCS 6558, pp. 319–339},
  cr_author_ids = {richard-lindner; chris-peikert},
  note = {CT-RSA 2011, LNCS 6558, pp. 319–339}
}