Cryptology ePrint Archive: Report 2017/1058

Optimal Key Consensus in Presence of Noise

Zhengzhong Jin and Yunlei Zhao

Abstract: In this work, we abstract some key ingredients in previous key exchange protocols based on LWE and its variants, by introducing and formalizing the building tool, referred to as key consensus (KC) and its asymmetric variant AKC. KC and AKC allow two communicating parties to reach consensus from close values obtained by some secure information exchange. We then discover upper bounds on parameters for any KC and AKC. KC and AKC are fundamental to lattice based cryptography, in the sense that a list of cryptographic primitives based on LWE and its variants (including key exchange, public-key encryption, and more) can be modularly constructed from them. As a conceptual contribution, this much simplifies the design and analysis of these cryptosystems in the future.

We then design and analyze both general and highly practical KC and AKC schemes, which are referred to as OKCN and AKCN respectively for presentation simplicity. Based on KC and AKC, we present generic constructions of key exchange (KE) from LWR, LWE, RLWE and MLWE. The generic construction allows versatile instantiations with our OKCN and AKCN schemes, for which we elaborate on evaluating and choosing the concrete parameters in order to achieve a well-balanced performance among security, computational cost, bandwidth efficiency, error rate, and operation simplicity.

Category / Keywords: cryptographic protocols / post-quantum cryptography, lattice, key exchange, public-key encryption

Date: received 31 Oct 2017, last revised 15 Feb 2019

Contact author: ylzhao at fudan edu cn

Available format(s): PDF | BibTeX Citation

Note: Correct two more typos, and add a note on random lifting with LWR-based KE.

Version: 20190215:160622 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]