On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle Attack
Africacrypt 2016
- Time bound
- Treduce(m,δ) + 216 binom(r,c) / sqrt(p·binom(2c,c)), r=4c
- Space bound
- Collision tables scale with the number of guessed/stored partial secrets; source theorem does not give a common cn memory coefficient.
- Source / version date
- 13 Apr 2016
- Comparison variant
- Binary secret and error · hybrid models
- Cost scale
- Parameter-dependent time and space expressions
- Parameters
- Fix n,m,q; r=4c guessed coordinates; reduced q-ary basis B with root-Hermite factor δ.
- Error distribution
- Independent uniform binary error in {0,1}; recentered to ±1/2 before decoding.
- Secret distribution
- Independent uniform binary secret in {0,1}^n.
- Sample budget
- Exactly the given m samples; comparisons instantiate at most m=2n.
- Objective
- Find a valid binary error and recover the secret.
- Cost model
- Nearest-plane plus meet-in-the-middle; p from Theorem 1; 2^16 operations per inner loop is an empirical estimate.
- Assumptions
- Heuristics 2 and 4; sufficient nearest-plane decoding quality for the correct residual target.
- Success guarantee
- Termination probability at least p₀=2^{−r}binom(r,2c) under Theorem 1 assumptions; amplification/restarts are additional.
Assumptions and source notes
The online expression is conditional on termination and on the source’s collision and per-loop heuristics. Basis reduction is a separate preprocessing cost. p is the admissibility/collision probability from Theorem 1, depending on the reduced-basis profile.
Source location
§3.2, Theorem 1, PDF pp. 8–9; §3.3 on preprocessing; §4 sample cap
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}
}