aiqbench analysis
This research identifies critical vulnerabilities in popular cryptographic compilers like Encrypted Key Exchange and Masny-Rindal OT when exposed to quantum adversaries, even when paired with post-quantum key encapsulation mechanisms. The study demonstrates that Universal Composability security fails in the quantum model due to specific adversarial strategies that prevent simulators from extracting necessary inputs, effectively breaking the security guarantees of these widely adopted protocols. Consequently, developers relying on these plug-and-play solutions for password-authenticated key exchange or oblivious transfer must reconsider their designs as current proofs do not hold against future quantum computing threats.
Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT
arXiv:2609.39844v1 Announce Type: new 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.
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.
Quantum Physics (quant-ph); Cryptography and Security (cs.CR)
arXiv:2609.39844 [quant-ph]
(or arXiv:2609.39844v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2609.39844 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 338 words
