Title: **Non-Committing Encryption as a QROM Playground** Talk om [[PQ-NCE and SIMstar]]/[[Proof of NCE-CPA in the QROM]] ved [[ProTeCS'24]], [[12024-05-25]] (ikke tatt opp). Outline: ![[IMG_6598.jpeg]] En av de uformelle vinnerne av [Best Slides Award](https://www.esat.kuleuven.be/cosic/blog/the-real-best-paper-of-eurocrypt-2024-and-also-the-protecs-workshop/) ved [[Eurocrypt'24]]. ### Talk outline The two main benefits of the ROM—which become challenges in the QROM—are preimage awareness, i.e. extraction of a query to the random oracle, and adaptive reprogrammability. It is known that any proof of NCE security requires both. Techniques for preimage awareness: - [[The Compressed-Oracle Technique]] - [[Fully Quantum OW-PCA]]? Techniques for adaptive reprogrammability: - [[One-way to hiding]], superseded by - [[Adaptive O2H]], superseded by - [[The resampling lemma]], superseded by - [[The reprogramming lemma]] *Programming*, as is done in the random oracle, is not a problem, since it is guaranteed to happen on unqueried values; only *reprogramming* is, which is what happens in the challenge oracle (to prepare for the subsequent programming). This is dealt with by the resampling lemma. If the adversary has any advantage in noticing the simulation, then the qPCA reduction will have *the same advantage* in halting with a preimage. ![[IMG_6432.jpeg]] ### Submission Dear ProTeCS Programme Committee, I present here two ideas for a talk I might hold at the ProTeCS workshop. One revolves around an open question uncovered in a recent work, while the other presents preliminary results from an ongoing project. Both projects are currently in an early stage—the choice to include either would help inform which project takes precedence until then, so that I may include any further developments in my talk. #### Option 1 **Title:** Selective Opening Attacks in the CCA setting: SIM vs IND **Speaker:** Hans Heum Based on work by Hans Heum, Carlo Brunetta, and Martijn Stam. PKC notions need to be updated when considering the possibility of the adversary corrupting senders and receivers (also known as "openings"). Several approaches have appeared in the literature, such as Selective Opening Attacks (SOA) and non-interactive Non-Committing Encryption (NCE). In a recent work *(cite)* (to be presented at PKC 2024), we systemized the various approaches to PKE security, and showed that they fall into four broad categories depending on their underlying philosophy: simulation-based vs. indistinguishability based, each with an a priori and an posteriori variant. Thus we get the following four approaches to security in the presence of openings, in order of increasing strength: 1. A priori indistinguishability, captured in multi-user notions of IND-CPA/IND-CCA with corruptions. 2. A posteriori indistinguishability, captured in notions of Indistinguishability SOA. 3. A posteriori simulatability, captured in notions of Simulatability SOA. 4. A priori simulatability, captured in Non-Committing Encryption. Stronger notions imply the weaker ones, and in the opposite direction separations are known, making the four philosophies fall neatly into a strict hierarchy of strength. This neat picture is however challenged by an exception: While it is certainly expected, it is currently unknown whether SSO-CCA implies ISO-CCA. In this talk I will show where the simple reduction from SSO-CPA to ISO-CPA breaks down in the CCA setting. I will then compare to the situation absent corruptions, where a similar open question stood between SEM-CCA (a posteriori simulatability) and IND-CCA (a priori indistinguishability) for a decade, before being resolved in the early 2000s. I ask whether we might look to this history for possible ways towards an implication, and present a few ideas. #### Option 2 **Title:** Non-Committing Encryption as a QROM Playground **Speaker:** Hans Heum Based on work by Hans Heum and Christian Majenz. (Non-interactive) Non-Committing Encryption (NCE) is a very strong security goal. Indeed, Nielsen *(cite)* showed that the notion is unachievable in the standard model, and indeed in any model that does not allow programming an ideal object. And yet the notion has turned out useful, both as an intermediary notion to achieving other, more realistic notions of security *(cite)*, and in instantiating MPC protocols that would otherwise require information-theoretically secured channels *(cite)*. The necessity of programmable ideal objects makes constructing post-quantum NCE an interesting challenge. Indeed, in showing that the canonical NCE construction achieves NCE-CPA security in the QROM, we find we have to pull out "every tool in the box", such as: - The compressed oracle technique *(cite)* - The one-way to hiding lemma *(cite)* - The resampling lemma *(cite)* - Fully-quantum OW-PCA *(cite)* Thus, post-quantum NCE really is a QROM playground. In this talk, I will present an overview of the proof structure, and how each of the above tools serve to answer a particular challenge when taking the proof from the ROM to the QROM. Time permitting, I will end on a brief discussion of how the construction may be upgraded to achieve NCE-CCA, and the additional challenges presented by CCA security in the QROM.