Paper 2017/1178

Comparison analysis and efficient implementation of reconciliation-based RLWE key exchange protocol

Xinwei Gao, Jintai Ding, Saraswathy RV, Lin Li, and Jiqiang Liu

Abstract

Error reconciliation is an important technique for Learning With Error (LWE) and Ring-LWE (RLWE)-based constructions. In this paper, we present a comparison analysis on two error reconciliation-based RLWE key exchange protocols: Ding et al. in 2012 (DING12) and Bos et al. in 2015 (BCNS15). We take them as examples to explain core idea of error reconciliation, building key exchange over RLWE problem, implementation, real-world performance and compare them comprehensively. We also analyse a LWE key exchange “Frodo” that uses an improved error reconciliation mechanism in BCNS15. To the best of our knowledge, our work is the first to present at least 128-bit classic (80-bit quantum) and 256-bit classic (>200-bit quantum) secure parameter choices for DING12 with efficient portable C/C++ implementations. Benchmark shows that our efficient implementation is 11x faster than BCNS15 and one key exchange execution only costs 0.07ms on a 4-year-old middle range CPU. Error reconciliation is 1.57x faster than BCNS15.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Int. J. of High Performance Computing and Networking, Special Issue on: "Security and Privacy in Complex Large-scale Computing Systems for Big Data Management"
Keywords
RLWEPost QuantumKey ExchangeImplementationAnalysis
Contact author(s)
xinwei gao 7 @ yandex com
History
2017-12-13: last of 2 revisions
2017-12-08: received
See all versions
Short URL
https://ia.cr/2017/1178
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1178,
      author = {Xinwei Gao and Jintai Ding and Saraswathy RV and Lin Li and Jiqiang Liu},
      title = {Comparison analysis and efficient implementation of reconciliation-based RLWE key exchange protocol},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1178},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1178}},
      url = {https://eprint.iacr.org/2017/1178}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.