Lattice Decoding Attacks on Binary LWE
ACISP 2014
- Time bound
- Treduce(d+1,δ), with d=m+n and δd≲(qmσn)1/d/(σ√(2πe))
- Space bound
- Depends on the reduction/enumeration subroutine.
- Source / version date
- 21 Feb 2017
- Comparison variant
- Small secret · rescaled primal
- Cost scale
- Parameter-dependent time and space expressions
- Parameters
- Fix n,m,q and Gaussian error standard deviation σ; ternary secret for the displayed determinant; d=m+n.
- Error distribution
- Independent discrete Gaussian error, standard deviation σ; no fixed universal σ(n) is assumed.
- Secret distribution
- Uniform ternary {−1,0,1}^n for displayed formula; binary {0,1}^n uses (2σ)^n determinant factor and recentering.
- Sample budget
- m available samples; source may discard rows. For ternary scaling, optimized d≈√(n(log₂q−log₂σ)/log₂δ) if allowed by m.
- Objective
- Recover small secret and error.
- Cost model
- ISIS embedding, rescaling, then CVP/uSVP decoding; displayed gap uses the Gaussian heuristic.
- Assumptions
- Random-lattice Gaussian heuristic and reduction-success model.
- Success guarantee
- Model-dependent recovery; experiments do not establish an arbitrary-lattice guarantee.
Assumptions and source notes
The ternary-secret scaling increases determinant by σ^n. For binary secrets the source uses scaling 2σ plus recentering. First posted December 2013 and published ACISP 2014; this record conservatively dates the fully checked revised PDF.
Source location
§§6.1–6.2, pp. 10–11, determinant scaling, gap discussion, Lemma 1 and Eq. (6)
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]
@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}
}