Optimal Key Consensus in Presence of Noise

Zhengzhong Jin; Yunlei Zhao

Paper 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.

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

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: post-quantum cryptography lattice key exchange public-key encryption
Contact author(s): ylzhao @ fudan edu cn
History: 2019-02-15: last of 5 revisions; 2017-10-31: received; See all versions
Short URL: https://ia.cr/2017/1058
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1058,
      author = {Zhengzhong Jin and Yunlei Zhao},
      title = {Optimal Key Consensus in Presence of Noise},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1058},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1058}
}