NewHope without reconciliation

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

Paper 2016/1157

NewHope without reconciliation

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

Abstract

In this paper we introduce NewHope-Simple, a variant of the NewHope Ring-LWE-based key exchange that is using a straight-forward transformation from Ring-LWE encryption to a passively secure KEM (or key-exchange scheme). The main advantage of NewHopeLP-Simple over NewHope is simplicity. In particular, it avoids the error-reconciliation mechanism originally proposed by Ding. The explanation of his method, combined with other tricks, like unbiasing the key following Peikert's tweak and using the quantizer $D_{4}$ to extract one key bit from multiple coefficients, takes more than three pages in the NewHope-Simple paper. The price for that simplicity is small: one of the exchanged messages increases in size by from bytes to bytes. The security of NewHopeLP is the same as the security of NewHope; the performance is very similar.

Note: Added a discussion about concurrent related work by Jin and Zhao

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Post-quantum key exchange NewHope code simplicity
Contact author(s): newhope @ cryptojedi org
History: 2017-11-09: revised; 2016-12-21: received; See all versions
Short URL: https://ia.cr/2016/1157
License: CC BY

BibTeX

@misc{cryptoeprint:2016/1157,
      author = {Erdem Alkim and Léo Ducas and Thomas Pöppelmann and Peter Schwabe},
      title = {{NewHope} without reconciliation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/1157},
      year = {2016},
      url = {https://eprint.iacr.org/2016/1157}
}