On the concrete hardness of Learning with Errors
Journal of Mathematical Cryptology 2015
- Time bound
- TBKZ(m+1,δ₀); log₂δ₀=[log₂(ε′τ α√(2e))]²/(4nlog₂q)
- Space bound
- Depends on the SVP oracle and embedding implementation.
- Source / version date
- 2 Oct 2015
- Comparison variant
- Primal embedding · Gaussian error
- Cost scale
- Parameter-dependent time and space expressions
- Parameters
- Fix n,q, Gaussian width αq; ε′>1 controls the error tail; τ≤1 and ε_τ model uSVP success; m≈√(nlog₂q/log₂δ₀).
- Error distribution
- Discrete Gaussian width αq, standard deviation αq/√(2π).
- Secret distribution
- General LWE secret.
- Sample budget
- At least optimized m samples; cap the choice by the actual sample budget.
- Objective
- Recover the secret by BDD-to-uSVP embedding.
- Cost model
- Source uses embedding factor t=||e||; success model ε_τ for gap τδ₀^m.
- Assumptions
- Gaussian heuristic for q-ary lattice minima; empirically calibrated uSVP success law.
- Success guarantee
- ε_τ·[1−(ε′exp((1−ε′²)/2))^m], under the source model.
Assumptions and source notes
Kannan embedding cost model stated with the empirical uSVP gap-to-reduction parameter τ. It is not a theorem that a root-Hermite factor alone solves every uSVP instance.
Source location
§5.5, Lemmas 5.17–5.18, pp. 190–191; Lemma 5.17 is attributed to Albrecht–Fitzpatrick–Göpfert Lemma 2
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}
}