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: Scaled-dual log₂ cost ≈ [2L/(2L+1)] · (unscaled-dual log₂ cost), in the stated sparse-FHE regime
Space bound: Depends on the chosen dual-lattice solver.

Source / version date: 18 May 2017
Comparison variant: Sparse secret · dual reductions
Cost scale: Parameter-dependent time and space expressions
Parameters: q(n) with log₂q=L log₂n+O(L), fixed L>0, constant Gaussian width αq=8 and fixed sparse weight h (source example h=64); source scaled dimension m′=2n.
Error distribution: Discrete Gaussian width αq=8, i.e. standard deviation 8/√(2π), independent of n.
Secret distribution: Uniform sparse ternary secret of fixed Hamming weight h, as in the source’s HElib asymptotic model.
Sample budget: Enough samples for the selected dual-lattice dimension; actual m must be enforced when instantiating.
Objective: Decision-LWE under a scaled dual-lattice attack.
Cost model: Relative exponent scaling 2L/(2L+1) against the corresponding unscaled dual model.
Assumptions: Source lattice-reduction and small-secret scaling model; fixed h and L are essential.
Success guarantee: Use the same target distinguishing advantage in both compared dual cost models.

Assumptions and source notes

A relative improvement in the source’s fixed-width sparse-FHE regime q=n^L·2^{O(L)}. It is not a universal exponent for LWE and need not beat exhaustive sparse-secret search when h is constant.

Source location

Abstract and Section Modulus switching / asymptotic behaviour
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}
}