Cryptology ePrint Archive: Report 2017/1178
Comparison analysis and efficient implementation of reconciliation-based RLWE key exchange protocol
Xinwei Gao and Jintai Ding and Saraswathy RV and 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.
Category / Keywords: cryptographic protocols / RLWE, Post Quantum, Key Exchange, Implementation, Analysis
Original Publication (in the same form): Int. J. of High Performance Computing and Networking, Special Issue on: "Security and Privacy in Complex Large-scale Computing Systems for Big Data Management"
Date: received 3 Dec 2017, last revised 13 Dec 2017
Contact author: xinwei gao 7 at yandex com
Available format(s): PDF | BibTeX Citation
Version: 20171213:113720 (All versions of this report)
Short URL: ia.cr/2017/1178
[ Cryptology ePrint archive ]