Algebraic Algorithms for LWE
ePrint 2014/1018
PreprintSource checked
- Time bound
- O(2ω D log₂(n/D) · σq log q) if D=o(n); O(2ω n log₂(D/n) · σq log q) if n=o(σ² log n); D=8σ² log₂ n+1
- Space bound
- Replace ω by 2 in the two time exponents.
- Source / version date
- 26 Feb 2015
- Comparison variant
- Gaussian error · algebraic bounds
- Cost scale
- Parameter-dependent time and space expressions
- Parameters
- Prime q polynomial in n; σ=αq/√(2π); D=8σ²log₂n+1; 2≤ω<3.
- Error distribution
- Discrete Gaussian error with standard-deviation convention σ.
- Secret distribution
- Arbitrary secret in Z_q^n.
- Sample budget
- As many samples as the linearization construction requires; exponential/subexponential sample counts are permitted.
- Objective
- Recover the secret.
- Cost model
- Classical dense linear algebra over Z_q; field-operation count.
- Assumptions
- Gaussian-tail truncation and algebraic linearization as analyzed in Theorem 4.
- Success guarantee
- As in the paper’s truncation/linearization construction; not a limited-sample guarantee.
Assumptions and source notes
Refined historical analysis of linearization, distinct from the conditional Gröbner-basis improvement. Bounds are recorded as source asymptotic expressions.
Source location
§4, Theorem 4, pp. 8–9; D_AG definition; multiplicative σq log q factor
Version: ePrint 2014/1018 revised 26 February 2015
Selected earlier references
Selected sources cited by this paper.
- New Algorithms for Learning in Presence of Errors
Sanjeev Arora · Rong Ge · 2011
Refines the linearization analysis and replaces it by conditional Gröbner-basis solving. §1; §§3–5; reference [5]
- On the concrete hardness of Learning with Errors
Martin R. Albrecht · Rachel Player · Sam Scott · 2015
Compares its algebraic bounds with contemporaneous lattice-reduction cost models. §1 and reference [4]
BibTeXDownload .bib
@misc{albrecht-cid-faugere-perret2014-algebraic,
author = {Martin R. Albrecht and Carlos Cid and Jean-Charles Faugère and Ludovic Perret},
title = {{Algebraic Algorithms for LWE}},
year = {2014},
url = {https://eprint.iacr.org/2014/1018},
keywords = {LWE, algorithmic complexity, historical literature},
cr_date = {2015-02-26},
cr_date_precision = {day},
cr_status = {preprint},
cr_venue = {Cryptology ePrint Archive, Paper 2014/1018},
cr_author_ids = {martin-r-albrecht; carlos-cid; jean-charles-faugere; ludovic-perret},
note = {Cryptology ePrint Archive, Paper 2014/1018}
}