Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.39844

Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT

James Bartusek, Jake Januzelli

quant-phcs.CRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

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.

AI Summary

The paper asks whether classical random-oracle UC-security proofs for KEM-based encrypted key exchange, (O)EKE, and Masny–Rindal oblivious transfer survive quantum oracle access when instantiated with post-quantum KEMs. It establishes negative simulation-security results alongside positive, weaker game-based guarantees. Masny–Rindal OT fails post-quantum simulation security for any correct KEM. Ideal-cipher and two-round-Feistel OEKE fail to realize the specified UC PAKE functionality; the attack also extends to several (O)EKE variants. The obstruction is input extraction: a simulator cannot fix the receiver’s choice bit or initiator’s password while preserving the environment’s view. The construction combines coherent honest behavior with a computationally indistinguishable dummy branch that detects measurement disturbance, using environment-held entanglement. The impossibility allows non-black-box simulators and arbitrary simulated oracle responses. Under post-quantum public-key uniformity and key unpredictability, Masny–Rindal OT satisfies a game in which predicting the sender’s output at a random index succeeds with probability at most $1/2+\operatorname{negl}$. Two-Feistel OEKE with a salted random-oracle KDF satisfies stand-alone game-based PAKE security: for password min-entropy $\gamma$, key-distinguishing advantage is at most $2^{-\gamma}+\operatorname{negl}$. Proofs use measure-and-reprogram and quantum rewinding. An advantage-tight one-way-to-hiding theorem transfers search bounds to distinguishing bounds, assuming an efficiently checkable target set and allowing polynomial runtime overhead. The attacks do not demonstrate recovery of both OT outputs or an immediate practical compromise. Concrete compositional consequences, efficient simulation-secure replacement compilers, concurrent BPR-style PAKE security, and ideal-cipher game-based security remain open.

No sign of AI-generated textAI use disclosed
AI tools were used to find the central idea behind the proof of \zcref[S]{thm:search-to-decision} (advantage-tight one-way to hiding) and to aid with proofreading, checking of technical details, and polishing.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

CAKE requires programming - On the provable post-quantum security of (O)CAKE

Kathrin Hövelmanns, Andreas Hülsing, Mikhail Kudinov +1 more

In this work we revisit the post-quantum security of KEM-based password-authenticated key exchange (PAKE), specifically that of (O)CAKE. So far, these schemes evaded a security proof considering quantum adversaries. We give a detailed analysis of why this is the case, determining the missing proof techniques. To this end, we first provide a proof of security in the post-quantum setting, up to a single gap. This proof already turns out to be technically involved, requiring advanced techniques to reason in the QROM, including the compressed oracle and the extractable QROM. To pave the way towards closing the gap, we then further identify an efficient simulator for the ideal cipher. This provides certain programming abilities as a necessary and sufficient condition to close the gap in the proof: we demonstrate that we can close the gap using the simulator, and give a meta-reduction based on KEM-anonymity that shows the impossibility of a non-programming reduction that covers a class of KEMs that includes Kyber / ML-KEM.

•Jul 25, 2025•0 citations

Post-Quantum Anonymity of Key Encapsulation Mechanism and Its Applications in Password Authenticated Key Exchange Protocols

JiaYv An, Yankun Gao, Lei Han

Driven by advances in the standardization of NIST’s Post-Quantum Cryptography (PQC) algorithms, research on constructing Password Authenticated Key Exchange (PAKE) protocols using Key Encapsulation Mechanisms (KEMs) has gained considerable attention. Several PAKE protocols have established precise security requirements for the underlying KEM. Arriaga et al. introduced a PAKE protocol called CHIC, which requires the KEM to achieve anonymity under plaintext-checkable attacks (ANO-1PCA). An anonymous KEM does not leak any information about which public key was used for encryption. It protects the identities and privacy of participants and is critical in preventing identity-guessing attacks, therefore, anonymity is also called key-privacy. The anonymity of NIST PQC Round-3 candidates has recently been analyzed, some of which satisfied ANO-CCA.Huguenin-Dumittan and Vaudenay proposed two efficient constructions, TCHand TH, to create KEM from public-key encryption (PKE) schemes. Jiang et al. introduced TRHbased on TH. These constructions can transform any OW-CPA PKE into an IND-qCCA KEM efficiently and avoid re-encryption. However, prior to this work, no research has been conducted to determine whether these constructions preserve or lift anonymity.In this paper, we proved that for any OW-CPA, DS-IND PKE, the construction KEMRH= TRH[PKE,H] achieves ANO1-CCA in the quantum random oracle model (QROM). We then construct a KEM called KyberRH, and provide an algorithm for the CHIC protocol using KyberRH.

IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)•Nov 14, 2025•1 citation

On Classical Cryptographic Protocols in Post-Quantum World

István Vajda

In post-quantum approach, we consider classical (non-quantum) protocols and primitives which are run by honest parties on classical computers and our aim is to keep their security in an environment where the adversary can rely on quantum computers [3].In particular, even a harder goal is set by requiring provable security guaranties in a concurrent running environment as we aim computational UC-security.Unruh [16] conjectured that classical arguments of computational UC-security remain usable in a postquantum world as long as the underlying computational UC-secure primitives are also computationally quantum UC-secure.Our proposed technique (full factorization) aims at reducing the original protocol into a statisticallysecure protocol by turning the protocol into a hybrid one where all cryptographic primitives are substituted by appropriate ideal functionalities.The considered set of primitives consists of secret key and public key encryption as well as digital signature.This way and by applying the Unruh's Quantum Lifting Theorem as well as the Quantum Universal Composition Theorem we gain a computationally quantum UC-secure protocol from a classical UC-secure protocol.We consider quantum standard-security, where the adversary can send only classical inputs to honest algorithms, i.e. honest machines cannot receive quantum superposition of inputs If we add also the practical need of efficiency our example is the class of protocols built from symmetric key primitives.A practical (fast) implementation could be based on AES encryption algorithm with appropriate key size as long as we live with the wide belief that this algorithm is secure against a quantum adversary.

International Journal of Computer Network and Information Security•Aug 8, 2017•5 citations

SoK: PQC PAKEs Design, Security and Performance

Nouri Alnahawi, David Haas, Erik Mauß +1 more

Password Authenticated Key Exchange (PAKE) establishes secure communication channels using passwords for authentication. Currently, standardized PAKEs rely on classical asymmetric cryptography. However, these PAKEs may become insecure should the expected quantum threat become a reality. Despite the growing interest in realizing quantum-safe PAKEs, they did not receive much attention from the ongoing Post-Quantum Cryptography (PQC) integration efforts. Hence, there is a significant awareness gap compared to PQC primitives subject to the official standardization processes. We provide a comprehensive overview of existing PQC PAKEs, classify their design rationales and authentication methods, and address aspects related to their security and performance. We identify PAKE designs that are still unexplored in the PQC realm and discuss the possibility of their adaptation. Thus, we offer a detailed reference for future work on PQC PAKEs.

IACR Communications in Cryptology•Aug 3, 2026•0 citations

On Migration to Quantum-Safe Cryptography

Jan Oupický

In 1994, Peter Shor developed a quantum algorithm that can efficiently solve the factorization and discrete logarithm problems. These problems are the foundation of modern cryptographic algorithms and the existence of an efficient algorithm for solving them threatens their security. Although large-scale quantum computers capable of breaking current cryptographic algorithms are not yet available, advances in quantum technology and the risk of “store now, decrypt later” attacks make it essential to prepare for migration to quantum-safe cryptography today. For the past decade, the cryptographic community has been actively developing algorithms that are not exploitable by Shor’s algorithm; such algorithms are said to be “quantum-safe” or “post-quantum.” However, cryptographic algorithms do not exist in isolation—they are components of larger cryptographic systems, such as protocols or other cryptographic primitives. Migrating these systems to use quantum-safe algorithms is therefore a complex task. This thesis studies the migration of several widely used cryptographic systems to post-quantum cryptography. In particular, we consider the migration of the public-key infrastructure (PKI), the TLS protocol, the XML Encryption and XML Signature standards, the SAML security framework, the Advanced Electronic Signature (AdES) standard, and the password-authenticated public-key encryption (PAPKE) primitive. For each topic, we analyze how the presence of quantum adversaries affects the security of existing constructions and identify components that rely on cryptographic assumptions vulnerable to quantum attacks. Based on this analysis, we propose approaches for adapting these systems to use post-quantum cryptographic algorithms. The proposed solutions are considered in two main forms: purely post-quantum and hybrid post-quantum. Purely post-quantum approaches rely exclusively on post-quantum algorithms, while hybrid post-quantum approaches combine classical and post-quantum mechanisms in order to provide security as long as at least one of the underlying assumptions remains secure. Hybrid post-quantum approaches are primarily motivated by uncertainty regarding the security of post-quantum algorithms. For each proposal, we discuss the advantages and disadvantages of the design, including deployment complexity, compatibility with existing systems, and performance considerations. In several cases, we also provide proof-of-concept implementations and evaluate their performance through benchmarks. We study post-quantum public-key infrastructures, which form a fundamental component of many other cryptographic systems. We show that constructing a purely post-quantum PKI does not fundamentally differ from constructing a classical PKI. For hybrid deployments, we propose two approaches—the composite hybrid and the parallel hybrid—which differ primarily in their implementation complexity. We also survey and analyze existing proposals for post-quantum TLS. In contrast, systems such as XML encryption and XML signatures, the SAML security framework, and the eIDAS-related AdES standard have received little attention in the context of post-quantum migration. For these systems, we outline possible migration approaches and provide proof-of-concept implementations. In addition, we present an example migration plan for a Trust Service Provider that relies on all of the discussed cryptographic systems, together with the methodology used to develop it. Finally, we consider the migration of the cryptographic primitive PAPKE. We propose a novel construction that replaces an ideal cipher with a half-ideal cipher, resulting in more efficient quantum-safe constructions and motivating the study of a new public-key encryption property called decryption robustness.

•Jun 26, 2026•0 citations

On the post-quantum security of encrypted key exchange protocols

Li Yang, Rui-Rui Zhou

We investigate the post-quantum security of the encrypted key exchange(EKE) protocols based on some basic physical parameters of ion-trap quantum computer, and show that the EKE protocol with a 40-bit password will be secure against a quantum adversary with several ion-trap quantum computers. We present a password encrypted no-key protocol to resist middle-man attack, and prove that it is also with the post-quantum security. The analysis presented here is probably of general meaning for the security evaluation of various hybrid cryptosystems.

arXiv:1305.5640•May 24, 2013•8 citations
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.
The paper asks whether classical random-oracle UC-security proofs for KEM-based encrypted key exchange, (O)EKE, and Masny–Rindal oblivious transfer survive quantum oracle access when instantiated with post-quantum KEMs. It establishes negative simulation-security results alongside positive, weaker game-based guarantees.
Masny–Rindal OT fails post-quantum simulation security for any correct KEM. Ideal-cipher and two-round-Feistel OEKE fail to realize the specified UC PAKE functionality; the attack also extends to several (O)EKE variants. The obstruction is input extraction: a simulator cannot fix the receiver’s choice bit or initiator’s password while preserving the environment’s view. The construction combines coherent honest behavior with a computationally indistinguishable dummy branch that detects measurement disturbance, using environment-held entanglement. The impossibility allows non-black-box simulators and arbitrary simulated oracle responses.
Under post-quantum public-key uniformity and key unpredictability, Masny–Rindal OT satisfies a game in which predicting the sender’s output at a random index succeeds with probability at most 1/2+negl⁡1/2+\operatorname{negl}1/2+negl. Two-Feistel OEKE with a salted random-oracle KDF satisfies stand-alone game-based PAKE security: for password min-entropy γ\gammaγ, key-distinguishing advantage is at most 2−γ+negl⁡2^{-\gamma}+\operatorname{negl}2−γ+negl. Proofs use measure-and-reprogram and quantum rewinding. An advantage-tight one-way-to-hiding theorem transfers search bounds to distinguishing bounds, assuming an efficiently checkable target set and allowing polynomial runtime overhead.
The attacks do not demonstrate recovery of both OT outputs or an immediate practical compromise. Concrete compositional consequences, efficient simulation-secure replacement compilers, concurrent BPR-style PAKE security, and ideal-cipher game-based security remain open.
In this work we revisit the post-quantum security of KEM-based password-authenticated key exchange (PAKE), specifically that of (O)CAKE. So far, these schemes evaded a security proof considering quantum adversaries. We give a detailed analysis of why this is the case, determining the missing proof techniques. To this end, we first provide a proof of security in the post-quantum setting, up to a single gap. This proof already turns out to be technically involved, requiring advanced techniques to reason in the QROM, including the compressed oracle and the extractable QROM. To pave the way towards closing the gap, we then further identify an efficient simulator for the ideal cipher. This provides certain programming abilities as a necessary and sufficient condition to close the gap in the proof: we demonstrate that we can close the gap using the simulator, and give a meta-reduction based on KEM-anonymity that shows the impossibility of a non-programming reduction that covers a class of KEMs that includes Kyber / ML-KEM.
Driven by advances in the standardization of NIST’s Post-Quantum Cryptography (PQC) algorithms, research on constructing Password Authenticated Key Exchange (PAKE) protocols using Key Encapsulation Mechanisms (KEMs) has gained considerable attention. Several PAKE protocols have established precise security requirements for the underlying KEM. Arriaga et al. introduced a PAKE protocol called CHIC, which requires the KEM to achieve anonymity under plaintext-checkable attacks (ANO-1PCA). An anonymous KEM does not leak any information about which public key was used for encryption. It protects the identities and privacy of participants and is critical in preventing identity-guessing attacks, therefore, anonymity is also called key-privacy. The anonymity of NIST PQC Round-3 candidates has recently been analyzed, some of which satisfied ANO-CCA.Huguenin-Dumittan and Vaudenay proposed two efficient constructions, TCHand TH, to create KEM from public-key encryption (PKE) schemes. Jiang et al. introduced TRHbased on TH. These constructions can transform any OW-CPA PKE into an IND-qCCA KEM efficiently and avoid re-encryption. However, prior to this work, no research has been conducted to determine whether these constructions preserve or lift anonymity.In this paper, we proved that for any OW-CPA, DS-IND PKE, the construction KEMRH= TRH[PKE,H] achieves ANO1-CCA in the quantum random oracle model (QROM). We then construct a KEM called KyberRH, and provide an algorithm for the CHIC protocol using KyberRH.
In post-quantum approach, we consider classical (non-quantum) protocols and primitives which are run by honest parties on classical computers and our aim is to keep their security in an environment where the adversary can rely on quantum computers [3].In particular, even a harder goal is set by requiring provable security guaranties in a concurrent running environment as we aim computational UC-security.Unruh [16] conjectured that classical arguments of computational UC-security remain usable in a postquantum world as long as the underlying computational UC-secure primitives are also computationally quantum UC-secure.Our proposed technique (full factorization) aims at reducing the original protocol into a statisticallysecure protocol by turning the protocol into a hybrid one where all cryptographic primitives are substituted by appropriate ideal functionalities.The considered set of primitives consists of secret key and public key encryption as well as digital signature.This way and by applying the Unruh's Quantum Lifting Theorem as well as the Quantum Universal Composition Theorem we gain a computationally quantum UC-secure protocol from a classical UC-secure protocol.We consider quantum standard-security, where the adversary can send only classical inputs to honest algorithms, i.e. honest machines cannot receive quantum superposition of inputs If we add also the practical need of efficiency our example is the class of protocols built from symmetric key primitives.A practical (fast) implementation could be based on AES encryption algorithm with appropriate key size as long as we live with the wide belief that this algorithm is secure against a quantum adversary.
Password Authenticated Key Exchange (PAKE) establishes secure communication channels using passwords for authentication. Currently, standardized PAKEs rely on classical asymmetric cryptography. However, these PAKEs may become insecure should the expected quantum threat become a reality. Despite the growing interest in realizing quantum-safe PAKEs, they did not receive much attention from the ongoing Post-Quantum Cryptography (PQC) integration efforts. Hence, there is a significant awareness gap compared to PQC primitives subject to the official standardization processes. We provide a comprehensive overview of existing PQC PAKEs, classify their design rationales and authentication methods, and address aspects related to their security and performance. We identify PAKE designs that are still unexplored in the PQC realm and discuss the possibility of their adaptation. Thus, we offer a detailed reference for future work on PQC PAKEs.
In 1994, Peter Shor developed a quantum algorithm that can efficiently solve the factorization and discrete logarithm problems. These problems are the foundation of modern cryptographic algorithms and the existence of an efficient algorithm for solving them threatens their security. Although large-scale quantum computers capable of breaking current cryptographic algorithms are not yet available, advances in quantum technology and the risk of “store now, decrypt later” attacks make it essential to prepare for migration to quantum-safe cryptography today. For the past decade, the cryptographic community has been actively developing algorithms that are not exploitable by Shor’s algorithm; such algorithms are said to be “quantum-safe” or “post-quantum.” However, cryptographic algorithms do not exist in isolation—they are components of larger cryptographic systems, such as protocols or other cryptographic primitives. Migrating these systems to use quantum-safe algorithms is therefore a complex task. This thesis studies the migration of several widely used cryptographic systems to post-quantum cryptography. In particular, we consider the migration of the public-key infrastructure (PKI), the TLS protocol, the XML Encryption and XML Signature standards, the SAML security framework, the Advanced Electronic Signature (AdES) standard, and the password-authenticated public-key encryption (PAPKE) primitive. For each topic, we analyze how the presence of quantum adversaries affects the security of existing constructions and identify components that rely on cryptographic assumptions vulnerable to quantum attacks. Based on this analysis, we propose approaches for adapting these systems to use post-quantum cryptographic algorithms. The proposed solutions are considered in two main forms: purely post-quantum and hybrid post-quantum. Purely post-quantum approaches rely exclusively on post-quantum algorithms, while hybrid post-quantum approaches combine classical and post-quantum mechanisms in order to provide security as long as at least one of the underlying assumptions remains secure. Hybrid post-quantum approaches are primarily motivated by uncertainty regarding the security of post-quantum algorithms. For each proposal, we discuss the advantages and disadvantages of the design, including deployment complexity, compatibility with existing systems, and performance considerations. In several cases, we also provide proof-of-concept implementations and evaluate their performance through benchmarks. We study post-quantum public-key infrastructures, which form a fundamental component of many other cryptographic systems. We show that constructing a purely post-quantum PKI does not fundamentally differ from constructing a classical PKI. For hybrid deployments, we propose two approaches—the composite hybrid and the parallel hybrid—which differ primarily in their implementation complexity. We also survey and analyze existing proposals for post-quantum TLS. In contrast, systems such as XML encryption and XML signatures, the SAML security framework, and the eIDAS-related AdES standard have received little attention in the context of post-quantum migration. For these systems, we outline possible migration approaches and provide proof-of-concept implementations. In addition, we present an example migration plan for a Trust Service Provider that relies on all of the discussed cryptographic systems, together with the methodology used to develop it. Finally, we consider the migration of the cryptographic primitive PAPKE. We propose a novel construction that replaces an ideal cipher with a half-ideal cipher, resulting in more efficient quantum-safe constructions and motivating the study of a new public-key encryption property called decryption robustness.
We investigate the post-quantum security of the encrypted key exchange(EKE) protocols based on some basic physical parameters of ion-trap quantum computer, and show that the EKE protocol with a 40-bit password will be secure against a quantum adversary with several ion-trap quantum computers. We present a password encrypted no-key protocol to resist middle-man attack, and prove that it is also with the post-quantum security. The analysis presented here is probably of general meaning for the security evaluation of various hybrid cryptosystems.