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 EKE, introduced by Bellovin and Merritt (S&P 1992), achieves a generic security level of 128 + 1/2 log₂(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 EKE in the ideal-cipher model is equivalent to the Hidden-Target Diffie–Hellman assumption. A somewhat surprising consequence of this equivalence is that EKE achieves the claimed generic security level of 128 + 1/2 log₂(N) bits. Moreover, the equivalence implies that EKE remains secure even in settings where the hardness of DLOG or 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.