Paper 2018/361

Two-message Key Exchange with Strong Security from Ideal Lattices

Zheng Yang, Yu Chen, and Song Luo


In this paper, we first revisit the generic two-message key exchange (TMKE) scheme (which will be referred to as KF) introduced by Kurosawa and Furukawa (CT-RSA 2014). This protocol is mainly based on key encapsulation mechanism (KEM) which is assumed to be secure against chosen plaintext attacks (IND-CPA). However, we find out that the security of the KF protocol cannot be reduced to IND-CPA KEM. The concrete KF protocol instantiated from ElGamal KEM is even subject to key compromise impersonation (KCI) attacks. In order to overcome the flaws of the KF scheme, we introduce a new generic TMKE scheme from KEM. Instead, we require that the KEM should be secure against one-time adaptive chosen ciphertext attacks (OT-IND-CCA2). We call this class of KEM as OTKEM. In particular, we propose a new instantiation of OTKEM from Ring Learning with Errors (Ring-LWE) problem in the standard model. This yields a concrete post-quantum TMKE protocol with strong security. The security of our TMKE scheme is shown in the extended Canetti-Krawczyk model with perfect forward secrecy (eCK-PFS).

Available format(s)
Publication info
Published elsewhere. MAJOR revision.CT-RSA 2018
Contact author(s)
zheng yang @ rub de
2018-04-18: received
Short URL
Creative Commons Attribution


      author = {Zheng Yang and Yu Chen and Song Luo},
      title = {Two-message Key Exchange with Strong Security from Ideal Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2018/361},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.