LWE / Gaussian error · algebraic bounds

Algebraic Algorithms for LWE

Martin R. Albrecht · Carlos Cid · Jean-Charles Faugère · Ludovic Perret

ePrint 2014/1018

PreprintSource checked

Time bound: O(2^{n[ω(1+C_A)H₂(C_A/(1+C_A)) + πlog₂(e)/(4A²)]})
Space bound: O(2^{n[2(1+C_A)H₂(C_A/(1+C_A)) + πlog₂(e)/(4A²)]})

Source / version date: 26 Feb 2015
Comparison variant: Gaussian error · algebraic bounds
Cost scale: Parameter-dependent time and space expressions
Parameters: Prime q(n) sufficiently large for degree n/A; error σ=√n/√(2π); A≥1 fixed; C_A is the degree-of-regularity constant from Lemma 6 / Proposition 3; C_1≈1.41.
Error distribution: Discrete Gaussian with standard deviation σ=√n/√(2π), hence width αq=√n.
Secret distribution: Arbitrary secret in Z_q^n.
Sample budget: m≈exp(πn/(4A²)); exponential oracle samples required.
Objective: Recover the secret.
Cost model: Field operations; ω is the chosen dense linear-algebra exponent; H₂ is binary entropy.
Assumptions: Assumption 1: semi-regularity of the generated high-degree LWE equations.
Success guarantee: At least 1−2/(π√n), conditional on the stated algebraic assumption.

Assumptions and source notes

Conditional on the generated equations being semi-regular. A=1 gives the paper’s rounded time exponent (2.35ω+1.13)n and rounded memory exponent 5.85n. These are historical algebraic bounds, not best overall LWE exponents.

Source location

§5, Lemma 6 and Theorem 5, pp. 10–11; Eq. (6)
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]

Primary source ↗

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}
}