LWE / Binary error · conditional 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(m² · 2^{ωn log₂log₂log₂(n)/(8log₂log₂(n))})
Space bound: O(m² · 2^{2n log₂log₂log₂(n)/(8log₂log₂(n))})

Source / version date: 26 Feb 2015
Comparison variant: Binary error · conditional algebraic bounds
Cost scale: Parameter-dependent time and space expressions
Parameters: Odd prime q=q(n), polynomially bounded; source regime m=O(n log log n); 2≤ω<3.
Error distribution: Independent uniform errors in {0,1}.
Secret distribution: Arbitrary s∈Z_q^n.
Sample budget: Quasilinear samples m=O(n log log n), as specified in Theorem 7(iv); not a claim for every smaller m.
Objective: Recover the secret via the generated quadratic equations.
Cost model: Field operations; dense linear-algebra exponent ω.
Assumptions: Assumption 2: semi-regularity.
Success guarantee: Conditional on semi-regularity and the intended unique-solution regime.

Assumptions and source notes

Conditional subexponential bound in a quasilinear-sample regime. The hidden sample-count constant must be retained when instantiating the result.

Source location

§6, Theorem 7(iv), Eq. (12), p. 13
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}
}