Paper 2025/1343

A Hybrid Asymmetric Password-Authenticated Key Exchange in the Random Oracle Model

Abstract

Symmetric encryption allows us to establish a secure channel based on a shared, strong key. However, users cannot remember or cannot store such keys securely. Password-Authenticated Key Exchange (PAKE) protocols address this by using low-entropy, human-memorizable passwords to establish secure channels. PAKEs are widely used and are foundational in practical cryptographic protocols, but while cryptographic tools like Key Encapsulation Mechanism (KEM) and Signatures have been implemented to resist attacks from quantum computers, PAKEs have gained quantum security only recently. To hedge against any potential vulnerabilities in recent quantum-secure PAKEs and in their implementations, we primarily focus on hybrid PAKE constructions that compose CPace, a classically-secure PAKE, with a variant of a recently proposed quantum-secure PAKE, which we call OQUAKE. Specifically we introduce and analyze two new hybrid PAKEs designed to be efficient, easy to implement, and utilize a minimized set of standard building blocks. The first, called CPaceOQUAKE, is a hybrid symmetric PAKE that remains secure as long as either a classical or post-quantum assumption holds. The second, called CPaceOQUAKE+, is a hybrid asymmetric PAKE (aPAKE) where the server party holds a verifier that obscures the password, instead of holding the password itself. In our analysis we present the necessary security proofs in the Universal Composability framework. In particular, we prove that OQUAKE, the underlying KEM-based PAKE in our hybrid constructions, realizes a relaxed UC PAKE variant that exposes password equality to passive observers, an observation available anyway in typical applications of PAKEs where the network interactions which follow the PAKE depend on authentication success. Moreover, we prove that our variant of the PAKE(+KEM)-to-aPAKE compiler is a similarly relaxed UC aPAKE.