Paper 2016/089

On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle Attack

Johannes Buchmann, Florian Göpfert, Rachel Player, and Thomas Wunderer

Abstract

The security of many cryptographic schemes has been based on special instances of the Learning with Errors (LWE) problem, e.g., Ring-LWE, LWE with binary secret, or LWE with ternary error. However, recent results show that some subclasses are weaker than expected. In this work we show that LWE with binary error, introduced by Micciancio and Peikert, is one such subclass. We achieve this by applying the Howgrave-Graham attack on NTRU, which is a combination of lattice techniques and a Meet-in-the-Middle approach, to this setting. We show that the attack outperforms all other currently existing algorithms for several natural parameter sets. For instance, for the parameter set n = 256, m = 512, q = 256, this attack on LWE with binary error only requires 2^85 operations, while the previously best attack requires 2^117 operations. We additionally present a complete and improved analysis of the attack, using analytic techniques. Finally, based on the attack, we give concrete hardness estimations that can be used to select secure parameters for schemes based on LWE with binary error

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Africacrypt 2016
Keywords
Learning with ErrorsLattice-based CryptographyCryptanalysisNTRUHybrid Attack
Contact author(s)
fgoepfert @ cdc informatik tu-darmstadt de
History
2016-04-13: last of 2 revisions
2016-02-02: received
See all versions
Short URL
https://ia.cr/2016/089
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/089,
      author = {Johannes Buchmann and Florian Göpfert and Rachel Player and Thomas Wunderer},
      title = {On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2016/089},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/089}},
      url = {https://eprint.iacr.org/2016/089}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.