Paper 2023/170

EKE Meets Tight Security in the Universally Composable Framework

Xiangyu Liu, Shanghai Jiao Tong University
Shengli Liu, Shanghai Jiao Tong University
Shuai Han, Shanghai Jiao Tong University
Dawu Gu, Shanghai Jiao Tong University

(Asymmetric) Password-based Authenticated Key Exchange ((a)PAKE) protocols allow two parties establish a session key with a pre-shared low-entropy password. In this paper, we show how Encrypted Key Exchange (EKE) compiler [Bellovin and Merritt, S&P 1992] meets tight security in the Universally Composable (UC) framework. We propose a strong 2DH variant of EKE, denoted by 2DH-EKE, and prove its tight security in the UC framework based on the CDH assumption. The efficiency of 2DH-EKE is comparable to the original EKE, with only $O(\lambda)$ bits growth in communication ($\lambda$ the security parameter), and two (resp., one) extra exponentiation in computation for client (resp., server). We also develop an asymmetric PAKE scheme 2DH-aEKE from 2DH-EKE. The security reduction loss of 2DH-aEKE is $N$, the total number of client-server pairs. With a meta-reduction, we formally prove that such a factor $N$ is inevitable in aPAKE. Namely, our 2DH-aEKE meets the optimal security loss. As a byproduct, we further apply our technique to PAKE protocols like SPAKE2 and PPK in the relaxed UC framework, resulting in their 2DH variants with tight security from the CDH assumption.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2023
(Asymmetric) PAKEUC FrameworkTight Security
Contact author(s)
xiangyu_liu @ sjtu edu cn
slliu @ sjtu edu cn
dalen17 @ sjtu edu cn
2023-02-22: revised
2023-02-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiangyu Liu and Shengli Liu and Shuai Han and Dawu Gu},
      title = {EKE Meets Tight Security in the Universally Composable Framework},
      howpublished = {Cryptology ePrint Archive, Paper 2023/170},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.