Paper 2017/221

A Hybrid Lattice Basis Reduction and Quantum Search Attack on LWE

Florian Göpfert, Christine van Vredendaal, and Thomas Wunderer

Abstract

Recently, an increasing amount of papers proposing post-quantum schemes also provide concrete parameter sets aiming for concrete post-quantum security levels. Security evaluations of such schemes need to include all possible attacks, in particular those by quantum adversaries. In the case of lattice-based cryptography, currently existing quantum attacks are mainly classical attacks, carried out with quantum basis reduction as subroutine. In this work, we propose a new quantum attack on the learning with errors (LWE) problem, whose hardness is the foundation for many modern lattice-based cryptographic constructions. Our quantum attack is based on Howgrave-Graham's Classical Hybrid Attack and is suitable for LWE instances in recent cryptographic proposals. We analyze its runtime complexity and optimize it over all possible choices of the attack parameters. In addition, we analyze the concrete post-quantum security levels of the parameter sets proposed for the New Hope and Frodo key exchange schemes, as well as several instances of the Lindner-Peikert encryption scheme. Our results show that - depending on the assumed basis reduction costs - our Quantum Hybrid Attack either significantly outperforms, or is at least comparable to all other attacks covered by Albrecht--Player--Scott in their work "On the concrete hardness of Learning with Errors". We further show that our Quantum Hybrid Attack improves upon the Classical Hybrid Attack in the case of LWE with binary error.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. PQCrypto 2017
Keywords
Lattice-based cryptographyLWEquantum attackhybrid attackpublic-key encryption
Contact author(s)
twunderer @ cdc informatik tu-darmstadt de
History
2017-04-18: revised
2017-03-04: received
See all versions
Short URL
https://ia.cr/2017/221
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/221,
      author = {Florian Göpfert and Christine van Vredendaal and Thomas Wunderer},
      title = {A Hybrid Lattice Basis Reduction and Quantum Search Attack on LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2017/221},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/221}},
      url = {https://eprint.iacr.org/2017/221}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.