Paper 2017/1058

Optimal Key Consensus in Presence of Noise

Zhengzhong Jin and Yunlei Zhao


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
post-quantum cryptographylatticekey exchangepublic-key encryption
Contact author(s)
ylzhao @ fudan edu cn
2019-02-15: last of 5 revisions
2017-10-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhengzhong Jin and Yunlei Zhao},
      title = {Optimal Key Consensus in Presence of Noise},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1058},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.