Paper 2015/1092

Post-quantum key exchange - a new hope

Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe

Abstract

In 2015, Bos, Costello, Naehrig, and Stebila (IEEE Security & Privacy 2015) proposed an instantiation of Ding's ring-learning-with-errors (Ring-LWE) based key-exchange protocol (also including the tweaks proposed by Peikert from PQCrypto 2014), together with an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. In this work we revisit their instantiation and stand-alone implementation. Specifically, we propose new parameters and a better suited error distribution, analyze the scheme's hardness against attacks by quantum computers in a conservative way, introduce a new and more efficient error-reconciliation mechanism, and propose a defense against backdoors and all-for-the-price-of-one attacks. By these measures and for the same lattice dimension, we more than double the security parameter, halve the communication overhead, and speed up computation by more than a factor of 8 in a portable C implementation and by more than a factor of 27 in an optimized implementation targeting current Intel CPUs. These speedups are achieved with comprehensive protection against timing attacks.

Note: Fixed several typos and details in the failure analysis (Section D).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. USENIX Security 2016
Keywords
Post-quantum key exchangeRing-LWEhigh-speed softwarevectorization
Contact author(s)
newhope @ cryptojedi org
History
2019-07-10: last of 9 revisions
2015-11-10: received
See all versions
Short URL
https://ia.cr/2015/1092
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1092,
      author = {Erdem Alkim and Léo Ducas and Thomas Pöppelmann and Peter Schwabe},
      title = {Post-quantum key exchange - a new hope},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1092},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1092}},
      url = {https://eprint.iacr.org/2015/1092}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.