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(n² · 2^{ωn(1+β)H₂(β/(1+β))+o(n)}), β=C−1/2−√(C(C−1))
Space bound: O(n² · 2^{2n(1+β)H₂(β/(1+β))+o(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; n variables; m=Cn with fixed C>1; β=C−1/2−√(C(C−1)); 2≤ω<3.
Error distribution: Independent uniform errors in {0,1}.
Secret distribution: Arbitrary s∈Z_q^n; this is binary ERROR, not an assumption of binary secret.
Sample budget: Exactly m=Cn; changing C changes the exponent.
Objective: Recover s by solving the error-free quadratic system.
Cost model: Arithmetic in Z_q; H₂(x)=−xlog₂x−(1−x)log₂(1−x). Formula follows Theorem 7 plus Proposition 1’s binomial coefficient.
Assumptions: Assumption 2: the specific quadratic equations are semi-regular.
Success guarantee: Conditional on Assumption 2 and the intended unique-solution regime.

Assumptions and source notes

Conditional linear-sample tradeoff. For m=2n the source rounds the time exponent to 0.43ωn; for m≥6.6n it reports approximately 0.344n time and 0.289n memory. Rounded decimals are not ingested as exact coefficients.

Source location

§6, Theorem 7(ii)–(iii), Eqs. (10)–(11), pp. 12–13; proof Eq. (14) and Proposition 1
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}
}