Cryptology ePrint Archive: Report 2017/424

HILA5: On Reliability, Reconciliation, and Error Correction for Ring-LWE Encryption

Markku-Juhani O. Saarinen

Abstract: We describe a new reconciliation method for Ring-LWE that has a significantly smaller failure rate than previous proposals while reducing ciphertext size and the amount of randomness required. It is based on a simple, deterministic variant of Peikert's reconciliation that works with our new ``safe bits'' selection and constant-time error correction techniques. The new method does not need randomized smoothing to achieve non-biased secrets. When used with the very efficient ``New Hope'' Ring-LWE parametrization we achieve a decryption failure rate well below $2^{-128}$ (compared to $2^{-60}$ of the original), making the scheme suitable for public key encryption in addition to key exchange protocols; the reconciliation approach saves about $40 \%$ in ciphertext size when compared to the common LP11 Ring-LWE encryption scheme. We perform a combinatorial failure analysis using full probability convolutions, leading to a precise understanding of decryption failure conditions on bit level. Even with additional implementation security and safety measures the new scheme is still essentially as fast as the New Hope but has slightly shorter messages. The new techniques have been instantiated and implemented as a Key Encapsulation Mechanism (KEM) and public key encryption scheme designed to meet the requirements of NIST's Post-Quantum Cryptography effort at very high security level.

Category / Keywords: Ring-LWE, Reconciliation, Post-Quantum Encryption, New Hope

Original Publication (with minor differences): Accepted to SAC 2017, Ottawa, Ontario, Canada, August 16 - 18, 2017. http://sacworkshop.org/SAC17/SAC2017.htm

Date: received 16 May 2017, last revised 13 Jul 2017

Contact author: mjos at iki fi

Available format(s): PDF | BibTeX Citation

Version: 20170713:180034 (All versions of this report)

Short URL: ia.cr/2017/424

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]