Paper 2023/706

Two-Message Authenticated Key Exchange from Public-Key Encryption

You Lyu, Shanghai Jiao Tong University
Shengli Liu, Shanghai Jiao Tong University

In two-message authenticated key exchange (AKE), it is necessary for the initiator to keep a round state after sending the first round-message, because he/she has to derive his/her session key after receiving the second round-message. Up to now almost all two-message AKEs constructed from public-key encryption (PKE) only achieve weak security which does not allow the adversary obtaining the round state. How to support state reveal to obtain a better security called IND-AA security has been an open problem proposed by Hövelmann et al. (PKC 2020). In this paper, we solve the open problem with a generic construction of two-message AKE from any CCA-secure Tagged Key Encapsulation Mechanism (TKEM). Our AKE supports state reveal and achieves IND-AA security. Given the fact that CCA-secure public-key encryption (PKE) implies CCA-secure TKEM, our AKE can be constructed from any CCA-secure PKE with proper message space. The abundant choices for CCA-secure PKE schemes lead to many IND-AA secure AKE schemes in the standard model. Moreover, following the online-extractability technique in recent work by Don et al. (Eurocrypt 2022), we can extend the Fujisaki-Okamoto transformation to transform any CPA-secure PKE into a CCA-secure Tagged KEM in the QROM model. Therefore, we obtain the first generic construction of IND-AA secure two-message AKE from CPA-secure PKE in the QROM model. This construction does not need any signature scheme, and this result is especially helpful in the post-quantum world, since the current quantum-secure PKE schemes are much more efficient than their signature counterparts.

Available format(s)
Cryptographic protocols
Publication info
Authenticated key exchangeState revealPKE
Contact author(s)
vergil @ sjtu edu cn
slliu @ sjtu edu cn
2023-05-22: approved
2023-05-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {You Lyu and Shengli Liu},
      title = {Two-Message Authenticated Key Exchange from Public-Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/706},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.