Paper 2025/1573

OneTwoPAKE: Two-Round Strong Asymmetric PAKE with Ideal Security

Abstract

Strong Asymmetric Password-Authenticated Key Exchange (saPAKE) enables a client, holding only a low-entropy password, to repeatedly establish shared high-entropy session keys with a server holding a digest of the expected password. Integrally, the only online attacks afforded to the adversary are those inevitable impersonation and dictionary attacks. As opposed to previous modeling, saPAKE addionally requires that any offline password search against the server’s storage takes place after adaptive server compromise. We present OneTwoPAKE, the first saPAKE protocol to simultaneously: 1. realize the full (unweakened ) strong aPAKE functionality; 2. not admit a speedup in an offline password search; (aka, has simulation-rate of 1 ); 3. use only a single round trip, with the client speaking first; and 4. avoid generic algebraic models. Similar to prior work, we instantiate our saPAKE from an OPRF over insecure channels secure against adaptive server compromise. In contrast to prior work, our OPRF is online-extractable and input-committing, enabling our protocol to realize the full saPAKE functionality. Of independent interest are our OPRF functionality and construction. We introduce the first formal model of such an OPRF, and our OPRF protocol is the first Dodis-Yampolskiy-based OPRF proven UC-secure against malicious adversaries without authenticated channels. Our framework demonstrates the feasibility of achieving all of the above properties simultaneously. Though our constructions are not as efficient as those of prior work, our saPAKE boasts the minimal round complexity, achieves full security, and, in terms of idealized models, relies only on the random oracle model. As future work may further close the efficiency gap, our framework may lead to practically deployable solutions.