On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle Attack
Africacrypt 2016
- Time bound
- Approximately 285 bit operations for (n,m,q)=(256,512,256)
- Space bound
- No numerical space estimate extracted.
- Source / version date
- 13 Apr 2016
- Comparison variant
- Binary secret and error · hybrid models
- Cost scale
- Parameter-dependent time and space expressions
- Parameters
- Fixed finite instance n=256, m=512, q=256; no q(n) asymptotic family asserted.
- Error distribution
- Independent uniform binary errors.
- Secret distribution
- Independent uniform binary secret.
- Sample budget
- At most 512=2n samples.
- Objective
- Recover the secret / valid error.
- Cost model
- Historical bit-operation estimate; source Table 1, row V. BKZ model is the empirical Eq. (1).
- Assumptions
- Hybrid collision heuristics, basis-profile model and historical lattice-reduction estimator.
- Success guarantee
- As estimated in the paper’s attack/parameter optimization.
Assumptions and source notes
Source Table 1’s concrete hybrid estimate, including the paper’s basis-reduction model. Its empirical LP-based BKZ estimate was later criticized; keep this as historical finite-instance evidence, without an asymptotic cn coefficient.
Source location
Abstract; §4, Table 1, row V, PDF p. 15; Eq. (1) for the historical BKZ estimator
Version: Author-hosted AFRICACRYPT 2016 manuscript; ePrint revision 13 April 2016
Selected earlier references
Selected sources cited by this paper.
- Lattice Decoding Attacks on Binary LWE
Shi Bai · Steven D. Galbraith · 2014
Extends the earlier partial-secret-guessing idea with meet-in-the-middle processing. Introduction related work and §3.1; reference [9]
- Algebraic Algorithms for LWE
Martin R. Albrecht · Carlos Cid · Jean-Charles Faugère · Ludovic Perret · 2014
Separates linear-sample binary-error attacks from the prior conditional quasilinear-sample algebraic result. Introduction related work and §4.1; reference [1] cites earlier five-author/title metadata for the same ePrint 2014/1018
- Better Key Sizes (and Attacks) for LWE-Based Encryption
Richard Lindner · Chris Peikert · 2011
Uses nearest-plane lattice decoding as the residual solving step and comparison baseline. §3.1 nearest-plane decoding and §4 comparison; reference [32]
- On the Efficacy of Solving LWE by Reduction to Unique-SVP
Martin R. Albrecht · Robert Fitzpatrick · Florian Göpfert · 2014
Compares the hybrid attack with an embedding-based LWE attack. §4 comparison, reducing to uSVP; reference [4]
- On the concrete hardness of Learning with Errors
Martin R. Albrecht · Rachel Player · Sam Scott · 2015
Uses prior LWE survey models to cost alternative attacks. §4 comparison; reference [5]
@misc{buchmann-goepfert-player-wunderer2016-hybrid,
author = {Johannes Buchmann and Florian Göpfert and Rachel Player and Thomas Wunderer},
title = {{On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle Attack}},
year = {2016},
url = {https://eprint.iacr.org/2016/089},
keywords = {LWE, algorithmic complexity, historical literature},
cr_date = {2016-04-13},
cr_date_precision = {day},
cr_status = {published},
cr_venue = {AFRICACRYPT 2016, LNCS 9646, pp. 24–43},
cr_author_ids = {johannes-buchmann; florian-gopfert; rachel-player; thomas-wunderer},
note = {AFRICACRYPT 2016, LNCS 9646, pp. 24–43}
}