Paper 2017/424

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

Markku-Juhani O. Saarinen


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.

Available format(s)
Publication info
Published elsewhere. MINOR revision.Accepted to SAC 2017, Ottawa, Ontario, Canada, August 16 - 18, 2017.
Ring-LWEReconciliationPost-Quantum EncryptionNew Hope
Contact author(s)
mjos @ iki fi
2017-09-24: last of 10 revisions
2017-05-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Markku-Juhani O.  Saarinen},
      title = {HILA5: On Reliability, Reconciliation, and Error Correction for Ring-LWE Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/424},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.