Round-reduced modular construction of asymmetric password-authenticated key exchange

Password-Authenticated Key Exchange (PAKE) establishes a shared key between two parties who hold the same password, assuring security against offline password-guessing attacks. The asymmetric PAKE (a.k.a. augmented or verifier-based PAKE) strengthens this notion by allowing one party, typically a server, to hold a one-way hash of the password, with the property that a compromise of the server allows the adversary to recover the password only via the offline dictionary attack against this hashed password. Today’s client-to-server Internet authentication is asymmetric, with the server holding only a (salted) password hash, but it relies on client’s trust in the server’s public key certificate. By contrast, cryptographic PAKE literature addresses the password-only setting, without assuming certified public keys, but it commonly does not address the asymmetric PAKE setting which is required for client-to-server authentication. The asymmetric PAKE (aPAKE) was defined in the Universally Composable (UC) framework by the work of Gentry et al. [15], who also provided a generic method of converting a UC PAKE to UC aPAKE, at the cost of two additional communication rounds. Motivated by practical applications of aPAKEs, in this paper we propose alternative methods for converting a UC PAKE to UC aPAKE, which use only one additional round. Moreover, since this extra message is sent from client to server, it does not add any round overhead in applications which require explicit client-to-server authentication. Importantly, this round-complexity reduction in the compiler comes at virtually no cost, since with respect to local computation and security assumptions our constructions are comparable to that of Gentry et al. [15].