On the concrete hardness of Learning with Errors
Journal of Mathematical Cryptology 2015
- Time bound
- minδ₀,d: P(d,δ₀)≥ε [TBKZ(m,δ₀) + tnode ∏i di]
- Space bound
- Depends on the selected lattice reduction and enumeration implementation.
- Source / version date
- 2 Oct 2015
- Comparison variant
- Lattice decoding · parameterized models
- Cost scale
- Parameter-dependent time and space expressions
- Parameters
- Fix n,q,m, Gaussian width αq, target success ε, per-node cost and reduced-basis profile.
- Error distribution
- Gaussian width αq; discrete/continuous approximation as in the decoding analysis.
- Secret distribution
- General LWE secret.
- Sample budget
- Survey allows unlimited samples; a finite deployment must enforce its actual m cap.
- Objective
- Recover the secret by BDD decoding.
- Cost model
- Minimize total preprocessing plus enumeration over δ₀ and branch counts d.
- Assumptions
- Basis-profile model (typically GSA) and Gaussian-coordinate decoding probabilities.
- Success guarantee
- P(d,δ₀)=∏_i erf(d_i||b_i*||√π/(2αq))≥ε.
Assumptions and source notes
Explicit optimization of the reduction/enumeration balance. The source observes that Lindner–Peikert’s example choices were not necessarily optimal. This records a cost model, not a new universal exponent.
Source location
§5.4, pp. 187–189, equation defining t_dec(ε) and discussion of optimizing Lindner–Peikert
Version: Journal of Mathematical Cryptology 9(3), published 2 October 2015
Selected earlier references
Selected sources cited by this paper.
- New Algorithms for Learning in Presence of Errors
Sanjeev Arora · Rong Ge · 2011
Analyzes the small-error algebraic linearization algorithm as one LWE solving strategy. §5.6, Arora–Ge and Gröbner bases; reference [12]
- Better Key Sizes (and Attacks) for LWE-Based Encryption
Richard Lindner · Chris Peikert · 2011
Optimizes and compares reduction plus nearest-planes decoding costs. §5.4 and reference [52]
- On the Efficacy of Solving LWE by Reduction to Unique-SVP
Martin R. Albrecht · Robert Fitzpatrick · Florian Göpfert · 2014
Imports the embedding gap estimate into its primal LWE cost model. §5.5, Lemma 5.17 attributed to [10, Lemma 2]
- Lattice Decoding Attacks on Binary LWE
Shi Bai · Steven D. Galbraith · 2014
Analyzes the earlier small-secret rescaled embedding in a common cost framework. §6.3, Lemma 6.4 and reference [14]
@misc{albrecht-player-scott2015-concrete,
author = {Martin R. Albrecht and Rachel Player and Sam Scott},
title = {{On the concrete hardness of Learning with Errors}},
year = {2015},
url = {https://eprint.iacr.org/2015/046},
keywords = {LWE, algorithmic complexity, historical literature},
cr_date = {2015-01-20},
cr_date_precision = {day},
cr_status = {published},
cr_venue = {Journal of Mathematical Cryptology 9(3), pp. 169–203; DOI 10.1515/jmc-2015-0016},
cr_author_ids = {martin-r-albrecht; rachel-player; sam-scott},
note = {Journal of Mathematical Cryptology 9(3), pp. 169–203; DOI 10.1515/jmc-2015-0016}
}