LWE / Small secret · guessing and lattice reduction

Lattice Decoding Attacks on Binary LWE

Shi Bai · Steven D. Galbraith

ACISP 2014

PublishedSource checked

Time bound: min_0≤k≤n 2^k · C_lattice(n−k,m,q,σ)
Space bound: Space of the chosen residual lattice solver, plus polynomial storage.

Source / version date: 21 Feb 2017
Comparison variant: Small secret · guessing and lattice reduction
Cost scale: Parameter-dependent time and space expressions
Parameters: Fix n,m,q, error standard deviation σ and k guessed secret coordinates.
Error distribution: Independent discrete Gaussian errors, standard deviation σ.
Secret distribution: Uniform binary secret in {0,1}^n for the 2^k factor; ternary guessing would cost 3^k.
Sample budget: m original samples, preserved after subtracting a candidate partial secret; no extra oracle samples assumed.
Objective: Recover the entire secret.
Cost model: Exhaust partial secret values then apply a specified residual lattice attack C_lattice.
Assumptions: Residual solver’s cost/success assumptions; expected or repeated cost must use a consistent success target.
Success guarantee: The correct guess reduces to the smaller instance; overall success follows the residual solver.

Assumptions and source notes

An early explicitly described guessing/lattice hybrid. This basic binary-secret formula is distinct from the later meet-in-the-middle hybrid with a binary error distribution.

Source location

§6.4, p. 12, combining the lattice attack with exhaustive search
Version: Full ePrint version last revised 21 February 2017; first ePrint 16 December 2013; ACISP 2014

Selected earlier references

Selected sources cited by this paper.

Better Key Sizes (and Attacks) for LWE-Based Encryption
Richard Lindner · Chris Peikert · 2011
Uses the earlier lattice decoding analysis as a baseline before exploiting small secrets. §4 standard lattice attack and reference [15] in the checked full ePrint
On the Efficacy of Solving LWE by Reduction to Unique-SVP
Martin R. Albrecht · Robert Fitzpatrick · Florian Göpfert · 2014
Uses prior BDD-to-uSVP embedding and its practical success model. §4.3 embedding discussion; reference [2] in ACISP 2014 edition
New Algorithms for Learning in Presence of Errors
Sanjeev Arora · Rong Ge · 2011
Explains why very small errors are only meaningful with an explicit restricted sample budget. §3 related work; reference [4] in full ePrint
Lattice-based Cryptography
Daniele Micciancio · Oded Regev · 2009
Uses earlier random q-ary lattice security and distinguishing analysis as context. §4 and references; ACISP 2014 reference [20]

Primary source ↗

BibTeXDownload .bib

@misc{bai-galbraith2013-binary-lwe,
  author = {Shi Bai and Steven D. Galbraith},
  title = {{Lattice Decoding Attacks on Binary LWE}},
  year = {2014},
  url = {https://eprint.iacr.org/2013/839},
  keywords = {LWE, algorithmic complexity, historical literature},
  cr_date = {2013-12-16},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {ACISP 2014, LNCS 8544, pp. 322–337; DOI 10.1007/978-3-319-08344-5_21},
  cr_author_ids = {shi-bai; steven-d-galbraith},
  note = {ACISP 2014, LNCS 8544, pp. 322–337; DOI 10.1007/978-3-319-08344-5_21}
}