LWE / Dual lattice · parameterized models

On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL

Martin R. Albrecht

Eurocrypt 2017

PublishedSource checked

Time bound: T_BKZ(m,β) + M·[T_rerandomize(m) + T_BKZ(m,β′)], with β′≤β
Space bound: Reduced basis plus M short dual vectors, if stored.

Source / version date: 18 May 2017
Comparison variant: Dual lattice · parameterized models
Cost scale: Parameter-dependent time and space expressions
Parameters: Fix n,q, Gaussian width αq, lattice dimension m, block sizes β,β′ and required relation count M.
Error distribution: Discrete Gaussian width αq.
Secret distribution: General LWE secret; this amortization does not require a short secret.
Sample budget: Works on the available LWE matrix; reuses it, unlike fully independent fresh-sample amplification.
Objective: Decision-LWE with amplified distinguishing advantage.
Cost model: One BKZ-β preprocessing followed by sparse unimodular rerandomization and cheaper BKZ-β′; source instantiation β′=2.
Assumptions: Cheap rerandomization yields short, adequately random relations; dependence can be ignored in the statistical test.
Success guarantee: Target advantage determines M; source estimates use dual-vector norm inflation by a factor of two.

Assumptions and source notes

Reuses an expensive reduced basis to generate many shorter dual relations. The claimed reduction relies on relations being sufficiently short and sufficiently random; fixed-sample correlations remain a heuristic.

Source location

Section Amortising costs, Algorithm 1 and its Heuristic paragraph
Version: Author TeX commit 2fc91ddbe45e21d7c337bfc658e4fd8926dd887c, 18 May 2017; associated ePrint last revised 6 May 2017

Selected earlier references

Selected sources cited by this paper.

Better Key Sizes (and Attacks) for LWE-Based Encryption
Richard Lindner · Chris Peikert · 2011
Explains why extrapolating the empirical BKZ seconds model gives misleading asymptotic LWE estimates. Preliminaries, LP model subsection; reference RSA:LinPei11 in author source
On the concrete hardness of Learning with Errors
Martin R. Albrecht · Rachel Player · Sam Scott · 2015
Refines earlier dual attack costing by amortizing generation of short dual relations. Preliminaries and Amortising costs; reference JMC:AlbPlaSco15
Lattice Decoding Attacks on Binary LWE
Shi Bai · Steven D. Galbraith · 2014
Applies the earlier secret/error lattice scaling idea to a dual attack. Introduction and Modulus switching section; reference ACISP:BaiGal14

Primary source ↗

BibTeXDownload .bib

@misc{albrecht2017-dual-small-secret,
  author = {Martin R. Albrecht},
  title = {{On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL}},
  year = {2017},
  url = {https://eprint.iacr.org/2017/047},
  keywords = {LWE, algorithmic complexity, historical literature},
  cr_date = {2017-05-06},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {EUROCRYPT 2017, LNCS 10210, pp. 103–129; DOI 10.1007/978-3-319-56614-6_4},
  cr_author_ids = {martin-r-albrecht},
  note = {EUROCRYPT 2017, LNCS 10210, pp. 103–129; DOI 10.1007/978-3-319-56614-6_4}
}