Paper 2026/1053

Beyond 128 Bits: The Concrete Security of EKE

Abstract

Can a relevant cryptographic primitive, when instantiated over the NIST P-256 elliptic curve, achieve a bit-security level exceeding $128$ bits? Yes. We formally prove that the well-known password-authenticated key exchange protocol $\mathsf{EKE}$, introduced by Bellovin and Merritt (S&P 1992), achieves a generic security level of $128+\frac{1}{2}\log_2(N)$ bits, where $N$ denotes the size of the password space. To prove this result, we introduce and develop a new approach for showing that breaking a cryptosystem with a prescribed advantage requires solving many instances of an underlying computational assumption. To this end, we formulate the Hidden-Target Diffie-Hellman assumption. In this assumption, the adversary is given a set of $N$ Diffie-Hellman challenge instances. The Diffie-Hellman key of one uniformly random instance is designated as the hidden target. The adversary does not know which instance is the target, but may output an arbitrary subset of candidate solutions and succeeds only if this subset contains the target. We formally prove that breaking the Hidden-Target Diffie-Hellman assumption with probability greater than $(k-1)/N$ requires solving at least $k$ of the $N$ Diffie-Hellman instances. We then show that the security of $\mathsf{EKE}$ in the ideal-cipher model is equivalent to the Hidden-Target Diffie-Hellman assumption. A somewhat surprising consequence of this equivalence is that $\mathsf{EKE}$ achieves the claimed generic security level of $128+\frac{1}{2}\log_2(N)$ bits. Moreover, the equivalence implies that $\mathsf{EKE}$ remains secure even in settings where the hardness of $\mathsf{DLOG}$ or $\mathsf{CDH}$ is weaker than expected: an adversary may still need to solve on the order of hundreds or thousands of discrete logarithm instances in order to succeed, a task that may remain infeasible even for powerful attackers, including those equipped with early quantum computers.