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

summary

Video file (mp4)

The gist

Encrypted key exchange (EKE) and Masny-Rindal OT are highly efficient methods for compiling essentially any Key Encapsulation Mechanism (KEM) into advanced cryptographic protocols like

In short

The paper investigates whether key exchange compilers like OEKE and Masny-Rindal OT are secure against quantum adversaries even when using post-quantum cryptography. It finds that these protocols fail simulation-based security, meaning they cannot be reliably simulated by a quantum computer, despite satisfying certain game-based security properties.

Key concepts

Universally Composable (UC)-secure
This term describes a strong security property where any protocol built using the underlying component (like a KEM) is also secure. The paper shows that OEKE and Masny-Rindal OT fail this property against quantum adversaries, meaning they are not universally secure.
Simulation-Based Security
This security measure checks if an adversary can create a 'simulator' that mimics the real protocol's behavior without knowing the secret inputs. The authors prove that OEKE and Masny-Rindal OT fail this test in the quantum setting, indicating they are not simulation-secure.
Game-Based Security
This is a weaker security notion where security is defined by analyzing the protocol's behavior within a specific game framework. Both OEKE and Masny-Rindal OT satisfy these game-based security definitions in the quantum random oracle model, meaning they behave correctly under certain adversarial scenarios.
Advantage-Tight One-Way to Hiding
This is a mathematical lemma used to relate the advantage of distinguishing two distributions (how hard it is to tell them apart) to the advantage of a search problem. It helps prove that the protocol's security bounds translate into meaningful distinguishing limits.

Terminology used across episodes

This episode discusses

The paper

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

James Bartusek, Jake Januzelli

Columbia University

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 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 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 game-based security. Along the way, we establish a novel ``advantage-tight'' one-way to hiding lemma that may be of independent interest.

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "Natural Barriers to Quantum Extraction".

Kai: Encrypted key exchange (EKE) and Masny-Rindal OT are highly efficient methods for compiling essentially any Key Encapsulation Mechanism (KEM) into advanced cryptographic protocols like Password-Authenticated Key Exchange (PAKE) and Oblivious…

Mira: First, who's behind it and why it matters.

Paper summary: Mira: To wrap up on "Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT," the authors are highlighting that despite their classical UC-security proofs, OEKE and Masny-Rindal OT don't translate directly into security in the quantum adversarial model. Kai They show this by proving that there are structural weaknesses, like the inability to extract inputs from a simulator, which thwart any attempt to use an extractor against them.

Lev: So when we look at the title, "Natural Barriers," it implies these aren't flaws in our implementation of post-quantum KEMs themselves, but rather inherent limitations in how these compilers are constructed for protocol compilation.

Kai: That’s right; they are showing that even with strong post-quantum primitives plugged in, the compiler itself creates a barrier against quantum extraction, meaning the security doesn't hold up as expected. Mira The main implication is that relying solely on classical security proofs for these compilers isn't enough when moving into the quantum realm because of these specific simulation failures.

Lev: From a researcher perspective, this tells us we have to re-evaluate how we justify the security of compiled protocols in a quantum setting; it points toward needing stronger assumptions than just what was guaranteed classically.

Kai: It gives us a clearer picture of where the current practical candidates for PAKE and OT might fall short when subjected to a quantum attacker, which is important context for anyone building systems with these primitives. Mira The authors are essentially saying that we can't just plug in any post-quantum KEM and expect the resulting protocol to inherit all its security guarantees automatically.

Conclusion: Kai: That title really hits home because it sounds like these aren't just simple bugs in the code, but fundamental structural walls that exist within the way these compilation methods are set up.

Mira: I agree with Kai; it suggests a limitation in the design of OEKE and Masny-Rindal OT that surfaces specifically when you consider quantum adversaries trying to pull out secret bits.

Lev: From my side, if these barriers are real, it means that even if we could build a perfect quantum computer, the protocol itself has a built-in mechanism that prevents an attacker from extracting the input without some kind of luck or specific error in the system.

Kai: Exactly; it’s about proving there’s a barrier against any attempt by an extractor to get the password or choice bit out of these schemes.

Mira: And what's interesting is that this doesn't just apply to one type of KEM; it shows a general family of these compilers has this issue, which is pretty big for the whole field.

Lev: If we think about running this on real hardware, it means we can’t just assume that because the underlying primitives are secure against quantum attacks, the resulting compiled protocol will automatically be secure in the same way.

Kai: So these results point toward a need to look beyond just the math of the KEM and really scrutinize how these compilers are constructed to ensure they don't inadvertently create exploitable weaknesses.

Mira: That's precisely what this work suggests; we have to be careful about what we assume about the security of compiled protocols when you move into a quantum context.

Lev: It sets a high bar for error correction research too, because if these structural flaws are real, it tells us how much overhead we might need to add just to compensate for the protocol design itself.

Kai: Right, so this isn't just about finding new quantum attacks; it's about understanding the inherent limitations of the compilation process itself when facing a quantum adversary.

Mira: Indeed, this paper lays out that specific structural weaknesses are present in OEKE and Masny-Rindal OT that prevent them from achieving certain levels of simulation-based security against quantum adversaries.

Lev: It's a sobering thought for anyone trying to deploy these protocols in a real system where you have to account for the actual computational power and noise limitations of the hardware.

Kai: It makes me wonder what this means practically for building next-generation secure communication channels that rely on these advanced techniques.

More episodes

← Home