On the concrete hardness of Learning with Errors
Journal of Mathematical Cryptology 2015
- Time bound
- O(ε⁻² · TBKZ(m,δ₀)); log₂δ₀=[log₂(f(ε)/α)]²/(4nlog₂q), f(ε)=√(ln(1/ε)/π)
- Space bound
- Depends on the chosen SVP oracle inside BKZ.
- Source / version date
- 2 Oct 2015
- Comparison variant
- Dual lattice · parameterized models
- Cost scale
- Parameter-dependent time and space expressions
- Parameters
- Fix n,q(n), Gaussian width αq, target one-vector bias ε and BKZ cost model; enough samples for optimized m.
- Error distribution
- Discrete Gaussian width αq, standard deviation αq/√(2π).
- Secret distribution
- General LWE secret in Z_q^n.
- Sample budget
- Unlimited samples in this historical survey; m≈√(nlog₂q/log₂δ₀) per fresh dual-vector instance, repeated for amplification.
- Objective
- Distinguish LWE from uniform with constant final advantage.
- Cost model
- ||v||≈δ₀^m q^{n/m}; bias≈exp(−π(α||v||)²); β/log₂β≈1/(2log₂δ₀). Select the SVP-oracle cost explicitly.
- Assumptions
- Lattice-reduction/Gaussian heuristic model and independent repetitions.
- Success guarantee
- One-vector bias ε; O(ε⁻²) independent observations for constant final advantage.
Assumptions and source notes
Historical dual model combining target vector length with a stated BKZ oracle. Its rule-of-thumb relation β/log₂β≈1/(2log₂δ₀) avoids falsely extrapolating an empirical seconds fit into a subexponential LWE algorithm.
Source location
§3.2, Corollary 3.2 / Remark 3.3; §4.1, Lemma 4.1; §5.3, Lemma 5.12 and following amplification discussion
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}
}