Two-message Key Exchange with Strong Security from Ideal Lattices

Zheng Yang; Yu Chen; Song Luo

Paper 2018/361

Two-message Key Exchange with Strong Security from Ideal Lattices

Zheng Yang, Yu Chen, and Song Luo

Abstract

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

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Major revision. CT-RSA 2018
Contact author(s): zheng yang @ rub de
History: 2018-04-18: received
Short URL: https://ia.cr/2018/361
License: CC BY

BibTeX

@misc{cryptoeprint:2018/361,
      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},
      url = {https://eprint.iacr.org/2018/361}
}