Cryptology ePrint Archive: Report 2018/361

Two-message Key Exchange with Strong Security from Ideal Lattices

Zheng Yang and 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).

Category / Keywords:

Original Publication (with major differences): CT-RSA 2018

Date: received 17 Apr 2018

Contact author: zheng yang at rub de

Available format(s): PDF | BibTeX Citation

Version: 20180418:203531 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]