Summary
Some popular ways to safely share secret keys or choices over the internet rely on classical methods proven secure against classical computers. This paper shows these methods, specifically certain password-based and oblivious transfer protocols, are actually vulnerable when faced with future quantum computers, even if the underlying building blocks are quantum-safe. The authors prove there is no secure way to simulate these protocols perfectly against quantum attacks. However, they also identify weaker security notions where these methods still hold up. Their findings highlight important limits in designing secure quantum-era communication tools.
What this means in practice
- •For security protocol designers: Avoid relying on (O)EKE and Masny-Rindal OT as universally composable secure methods in systems expected to face quantum attacks.
- •For quantum-safe cryptography developers: Develop alternative password-authenticated key exchange and oblivious transfer protocols that provide stronger universal composability guarantees against quantum adversaries.
A theory result. No direct application yet.
Abstract
Encrypted key exchange (EKE), introduced by Bellovin and Merritt (IEEE S\&P 1992), and Masny-Rindal OT, introduced by Masny and Rindal (ACM CCS 2019), are highly-efficient methods for compiling essentially any KEM into advanced cryptographic protocols, namely password-authenticated key exchange (PAKE) and oblivious transfer (OT), by relying only on idealized symmetric-key primitives. They have become leading candidates for practically-implementable PAKE and OT due to (1) their simplicity, (2) their plug-and-play nature, allowing for flexibility in the choice of KEM, and (3) existing proofs of UC-security (in the classical adversarial model). Due to point (2) above, these compilers yield attractive candidates for efficient \emph{post-quantum} PAKE and OT, especially given the recent post-quantum KEM standardization efforts. This motivates the question of whether the (UC-)security of these compilers translates to the quantum adversarial model. In this work, we show that it does not. In particular, we prove that a general family of (O)EKE protocols, as well as Masny-Rindal OT, are \emph{not} UC-secure against quantum polynomial-time adversaries, even when instantiated with a post-quantum KEM. To establish UC-insecurity, we devise an adversarial strategy that provably thwarts any attempt by the simulator to extract its input (the password in the case of PAKE, and the receiver's choice bit in the case of OT). To complement these negative results, we establish that both compilers yield certain notions of \emph{game-based} security. Along the way, we establish a novel ``advantage-tight'' one-way to hiding lemma that may be of independent interest.