Paper 2023/170 Original: eprint.iacr.org/2023/170 ↗

EKE Meets Tight Security in the Universally Composable Framework

Abstract

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