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

Martin R. Albrecht

Abstract

We present novel variants of the dual-lattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKW-style algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL v2.0 yields revised security estimates. Our techniques scale the exponent of the dual-lattice attack by a factor of $$(2\,L)/(2\,L+1)$$ when $$\log q = \Theta{\left(L \log n\right)}$$, when the secret has constant hamming weight $$h$$ and where $$L$$ is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of $$2^{h}$$ operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with $n=1024$ and $\log_2 q \approx {47}$, while the techniques described in this work lead to estimated costs of 68 bits (SEAL v2.0) and 62 bits (HElib).

Note: minor corrections

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
learning with errorscryptanalysishomomorphic encryption
Contact author(s)
martin albrecht @ royalholloway ac uk
History
2017-05-06: last of 2 revisions
See all versions
Short URL
https://ia.cr/2017/047

CC BY

BibTeX

@misc{cryptoeprint:2017/047,
author = {Martin R.  Albrecht},
title = {On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL},
howpublished = {Cryptology ePrint Archive, Paper 2017/047},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/047}},
url = {https://eprint.iacr.org/2017/047}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.