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