Cryptology ePrint Archive: Report 2016/1157

NewHope without reconciliation

Erdem Alkim and Léo Ducas and 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 $6.25%$ from $2048$ bytes to $2176$ bytes. The security of NewHopeLP is the same as the security of NewHope; the performance is very similar.

Category / Keywords: public-key cryptography / Post-quantum key exchange, NewHope, code simplicity

Date: received 17 Dec 2016, last revised 17 Dec 2016

Contact author: newhope at cryptojedi org

Available format(s): PDF | BibTeX Citation

Version: 20161221:163833 (All versions of this report)

Short URL: ia.cr/2016/1157

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]