### Analysis of Error-Correcting Codes for Lattice-Based Key Exchange

Tim Fritzmann, Thomas Pöppelmann, and Johanna Sepulveda

##### Abstract

Lattice problems allow the construction of very efficient key exchange and public-key encryption schemes. When using the Learning with Errors (LWE) or Ring-LWE (RLWE) problem such schemes exhibit an interesting trade-off between decryption error rate and security. The reason is that secret and error distributions with a larger standard deviation lead to better security but also increase the chance of decryption failures. As a consequence, various message/key encoding or reconciliation techniques have been proposed that usually encode one payload bit into several coefficients. In this work, we analyze how error-correcting codes can be used to enhance the error resilience of protocols like NewHope, Frodo, or Kyber. For our case study, we focus on the recently introduced NewHope Simple and propose and analyze four different options for error correction: i) BCH code; ii) combination of BCH code and additive threshold encoding; iii) LDPC code; and iv) combination of BCH and LDPC code. We show that lattice-based cryptography can profit from classical and modern codes by combining BCH and LDPC codes. This way we achieve quasi-error-free communication and an increase of the estimated post-quantum bit-security level by 20.39% and a decrease of the communication overhead by 12.8%.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. International Conference on Selected Areas in Cryptography. Springer, Cham, 2018. S. 369-390.
DOI
10.1007/978-3-030-10970-7_17
Keywords
post-quantum key exchangeNewHope Simpleerror-correcting codes
Contact author(s)
tim fritzmann @ gmail com
History
2019-11-14: last of 2 revisions
See all versions
Short URL
https://ia.cr/2018/150

CC BY

BibTeX

@misc{cryptoeprint:2018/150,
author = {Tim Fritzmann and Thomas Pöppelmann and Johanna Sepulveda},
title = {Analysis of Error-Correcting Codes for Lattice-Based Key Exchange},
howpublished = {Cryptology ePrint Archive, Paper 2018/150},
year = {2018},
doi = {10.1007/978-3-030-10970-7_17},
note = {\url{https://eprint.iacr.org/2018/150}},
url = {https://eprint.iacr.org/2018/150}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.