LWE / Sparse secret · dual reductions

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

Martin R. Albrecht

Eurocrypt 2017

PublishedSource checked

Time bound: O(2^h · C(n/2,α,q)); more generally O(p_h,d⁻¹·C(n−n/d,α,q))
Space bound: Space of the reduced-dimension solver C.

Source / version date: 18 May 2017
Comparison variant: Sparse secret · dual reductions
Cost scale: Parameter-dependent time and space expressions
Parameters: Fix h≥0 and d>1 independent of n; p_{h,d}=lim_{n→∞}binom(n−h,n/d)/binom(n,n/d)=(1−1/d)^h.
Error distribution: Original error distribution/width αq is retained by the zero-support branch.
Secret distribution: Uniform support of Hamming weight h with small ternary nonzero values; basic support argument does not depend on their magnitudes.
Sample budget: Same original sample budget passed to residual instances; residual solver requirements remain explicit.
Objective: Solve LWE using independent support-avoidance trials and a residual solver C.
Cost model: C(N,α,q) is cost at the fixed required high success probability; d=2 gives p=2^{−h}.
Assumptions: Uniform/random sparse support; high-success residual solver; fixed h,d.
Success guarantee: Constant support-avoidance probability per trial, amplified by O(1/p_{h,d}) trials.

Assumptions and source notes

Exploits the event that a discarded coordinate subset misses the sparse support. C denotes a specified residual LWE solver, so this is a reduction/tradeoff rather than a standalone universal LWE exponent.

Source location

Section Sparse secrets, Asymptotic behaviour lemma and following d=2 remark
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}
}