Projects per year
Abstract
We present novel variants of the duallattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKWstyle algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL yields revised security estimates. Our techniques scale the exponent of the duallattice attack by a factor of (2L)/(2L+1)(2L)/(2L+1) when logq=Θ(Llogn)logq=Θ(Llogn), when the secret has constant hamming weight hh and where LL is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of 2h2h operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with n=1024n=1024 and log2q≈47log2q≈47, while the techniques described in this work lead to estimated costs of 68 bits (SEAL) and 62 bits (HElib).
Original language  English 

Title of host publication  Annual International Conference on the Theory and Applications of Cryptographic Techniques 
Subtitle of host publication  EUROCRYPT 2017: Advances in Cryptology 
Publisher  Springer 
Pages  103129 
Number of pages  27 
ISBN (Electronic)  9783319566207 
ISBN (Print)  9783319566191 
DOIs  
Publication status  Epub ahead of print  1 Apr 2017 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer, Cham 
Volume  10210 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Projects
 2 Finished

Multilinear Maps in Cryptography
Paterson, K.
Eng & Phys Sci Res Council EPSRC
31/01/14 → 30/01/17
Project: Research