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

Xinwei Gao; Jintai Ding; Saraswathy RV; Lin Li; Jiqiang Liu

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: RLWE Post Quantum Key Exchange Implementation Analysis
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: 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},
      url = {https://eprint.iacr.org/2017/1178}
}