SoK - Public Key Encryption with Openings

## Neste steg - [ ] 🎓 Hente inn det klassiske beviset jeg jobbet med i København #### Fullførte steg - [x] 🎓 Fikse git - [x] 🎓 Få dokumentet til å kompilere riktig - [x] 🎓 Sette opp rough struktur for JC full version - [x] 🎓 Gjenreise NCE-CCA-konstruksjonen ### Info Title: **SoK: Public Key Encryption with Openings** Status: Published at [[PKC'24]]. Authors: Carlo Brunetta, Hans Heum, Martijn Stam Full version: https://eprint.iacr.org/2023/1337 Talk: https://www.youtube.com/watch?v=-mmUMvj2gMA Abstract (full version): > When modelling how public key encryption can enable secure communication, we should acknowledge that secret information, such as private keys or the randomness used for encryption, could become compromised. Intuitively, one would expect unrelated communication to remain secure, yet formalizing this intuition has proven challenging. Several security notions have appeared that aim to capture said scenario, ranging from the multi-user setting with corruptions, via selective opening attacks (SOA), to non-committing encryption (NCE). Remarkably, how the different approaches compare has not yet been systematically explored. > > We provide a novel framework that maps each approach to an underlying philosophy of confidentiality: indistinguishability versus simulatability based, each with an a priori versus an a posteriori variant, leading to four distinct philosophies. In the absence of corruptions, these notions are largely equivalent; yet, in the presence of corruptions, they fall into a hierarchy of relative strengths, from IND-CPA and IND-CCA at the bottom, via indistinguishability SOA and simulatability SOA, to NCE at the top. > > We provide a concrete treatment for the four notions, discuss subtleties in their definitions and asymptotic interpretations and identify limitations of each. Furthermore, we re-cast the main implications of the hierarchy in a concrete security framework, summarize and contextualize other known relations, identify open problems, and close a few gaps. > > We end on a survey of constructions known to achieve the various notions. We identify and name a generic random-oracle construction that has appeared in various guises to prove security in seemingly different contexts. It hails back to Bellare and Rogaway's seminal work on random oracles (CCS'93) and, as previously shown, suffices to meet one of the strongest notions of our hierarchy (single-user NCE with bi-openings). Puts in a system and relates [[Multi-User Security]], [[Selective Opening Attacks]], and [[Non-Committing Encryption]]. Contained in my PhD thesis, [[Cryptology in the Crowd]]. ### Deleted commented-out text worth keeping around ##### Mentioned as something sitting in between CPA and CCA: > chosen plaintext attacks with decryption oracles (CPAD)~\cite{EC:LiMic21}. ##### On restricted SSO > MSM: As the NCE to SSO implication has a restriction, was wondering what the restricted SSO would imply, but it seems not very obvious (plus perhaps not the right time to address). ##### On the novelty of our NCE-to-SSO reduction > (This is) a result that was previously shown for sender openings~\cite{EC:FHKW10} and receiver openings~\cite{AC:HazPatWar15} > MSM: not true, those results are not tight! > MSM: Recall BelYil's open problem? >> *We would imagine that security under the MPC definitions of the above works implies both SOA-K and SOA-C but are not aware of this claim having been formally established.* > >HH (08-06): Yes! Just saw it myself and came here to leave a note about it. Nice to know we answered a question they posed (and were apparently the first to do so). ##### On the explanation of Nielsen's impossibility result > MSM: The explanation above (and elsewhere of Yang et al.) is fine, but, fwiw, neither really makes very clear why the impossibility is specific to receiver openings; to me, the argument sounds like it might well apply to sender openings (which I know it does not). ##### On [[Quantum-enabled deniable encryption]] (see the note) ##### On [[Tweaked NCE]] (see the note) ##### On [[Imperfect correctness]] Fra [[SoK - Public Key Encryption with Openings]] (kursivparantesen er slettet) > Turning to receiver openings, Bellare et al.~\cite{EC:BDWY12} also identified a feature called decryption verifiability, which captures that anyone given a tuple consisting of public key, private key, ciphertext and message, should be able to *(thought: how would imperfect correctness impact here?)* verify that the ciphertext is an honest encryption of the message (for some definition of "honest"). They showed that no scheme that is decryption verifiable can be SSO-recop secure, even for independent, uniform sampling. ##### On [[Message samplers]] (see the note) ### Old working notes (no-ml) In preparation for camera ready, some hboxes really do get overfilled a bit too much currently (Jan 11): - p.2 IND-CPA/IND-CCA - fix: write "IND-CPA resp. IND-CCA" instead - p.21 through - rephrased sentence from "allowing for" to "which allows for", which was enough to trigger a line break. - p.26 ISO-CPA-sendop - fix: rewrote "For instance, an implication ..." to "For instance, an implication such as ..." to force linebreak; to balance, removed the redundant "main" in "main downward implications" from end of paragraph (there are no downward implications that are not "main"). - p.29 (class-restricted) - wrote "class restricted" instead (which should anyway be more consistent with our avoidance of hyphenation in terms like Public Key and Selective Opening). Then again, the problem may be compiler dependent—leave for Springer to figure out? Publish in: - Journal of Crypto? - Communications of Crypto? https://cic.iacr.org - January 8 - ✅ PKC? PKC submission - changes from v1 to v2: - Sec 1: - delegated part of future directions to full version only - removed Roadmap, and tacked the paragraph on supp. mat. onto the end of the previous subsection. - Sec. 3: - delegated remark about a posteriori indistinguishability being reminiscent of KEM notions to full version only - skipped a few lineshifts in 3.2 - all historical remarks delegated to supp. mat. - delegated the SSO' figure to full version only - Sec. 4: - added back in main body: - most of Implications - all of Separations - SSO vs NCE - ... though I skipped the separation into subsections, to save space + didn't seem necessary Rebuttal notes: - For the moving stuff from the supplementary to main body, we can indicate a willingness but also stress that page limits would force us to then also move something away. We can also explain explicitly our rationale for including/excluding in the main body as we did - For the constructions it's more a survey, so we could state that's partly why we didn't prioritize it - It might make sense to estimate what the various additionally suggested inclusions would cost (page wise). For instance, including Table 2 in a self-contained way I reckon would easily set you back a page, but an executive summary thereof highlighting what's the main missing one can be a lot shorter. - For the notation, we can say we prefer to keep as is, both approaches (abbreviations vs symbols) have pros and cons and we wanted to avoid alphabet soups and try to keep the goal--power idea as much as possbile, notwithstanding the further prefixing with parameters - So for the Shannon bit, there's no obvious reference for our notion (other than the lecture notes from UoB, but that's not an acceptable source here) Rebuttal, first draft: > We thank the reviewers for their comments and feedback. Several reviewers mention that it is a shame that our survey of known constructions did not fit into the main body. Fundamentally, we agree, but given the space constraints we opted to focus on a complete and self-contained presentation of our systematization, which is mainly concerned with definitions, whereas the chapter on constructions is really more of a survey than a systematization. > We are open to the idea of moving things up from the supplementary materials into the main body, but stress that this would have to come at the expense of what is already in the main body. For example: presenting Table 2 in the main body in a self-contained way would likely cost us a page or more, and we struggle to see how this could be done without detriment to the flow of the text. Meanwhile a paragraph summarizing the main findings of Table 2, and the survey at large, should be doable in half a page or less, making this a more realistic option. The same goes for Reviewer A's request for discussion around applications, and Reviewer B's request for a discussion surrounding single-bit vs multi-bit notions (also feeding into applications). > > Re. Reviewer A’s concern about information-theoretic a posteriori indistinguishability: This is a rather rare notion, and we are not aware of any sources that explicitly discuss it (and its anomaly). We don’t see an alternative definition that *would* be satisfiable without uniform sampling of messages, as surely Pr(M = m0) = Pr(M = m1) must be a prerequisite for the notion to hold, before introducing a ciphertext into the mix. If the reviewer has a different definition of a posteriori indistinguishability in mind, we would be curious to see it. We do find it interesting though that the dependence on a uniform message distribution seems to mirror the similarly annoying dependence of notions of ISO on efficiently conditionally resampleable message distributions. > > Re. Reviewer B's concern about notation: We aimed for a notation that avoided an all-too-common alphabet soup of notions, and rather stuck as closely as possible to the GOAL-POWER distinction, with prefixes for certain parameters and (symbolic) postfixes for openings. Both approaches have pros and cons in terms of readability vs succinctness, and while we like our chosen notation, we are open to the alternative at the reviewers' insistence. > > Re. lack of references when introducing transmission openings: This due to, as far as we know, BY12 being the only ones to discuss the transmission opening prior to the present work. As to applications thereof, between BY12 and the present article, it has been well established that transmission openings add no real strength to notions of security (with the notable exception of Full-ISO, which we argue should be abandoned). Thus we feel that the main interest of transmission openings lies in the fact that they are pointless. Intro feedback, Martijn, 290823 (to be addressed for published version): >Well, what I had in mind is hard to express, which is why editing is difficult as well. However, I definitely had expected more synchrony between intro and main body. As is, in the intro we don't really express any of our findings beyond the high-level taxonomy (for instance, the CCA gap or the role of the message sampler). The open problems in the intro seem completely disjoint from those in the main body (that seem like an afterthought in the current write up). -> Add a "Findings"/"Open problems" paragraph above the Applications paragraph? Struktur: 1. Introduction 2. Preliminaries 1. Notation 2. PKE Syntax 3. Security Notions 3. Confidentiality with Openings 1. Four Kinds of Opening 2. Four Philosophies of Confidentiality 3. A Priori Indistinguishability with Opening (IND) 1. (...) 2. Opening Challenges 4. A Posteriori Indistinguishability with Selective Opening (ISO) 1. (...) 2. Alternative Samplers 3. (...) 4. Full ISO 5. A Posteriori Simulatability with Selective Opening (SSO) 1. (...) 2. SSO implies ISO 3. Historical Remarks 7. A Priori Simulatability with Selective Opening (NCE) 1. (...) 2. NCE implies SSO 3. Historical Remarks 8. Known Relations (to-be-restructured) 1. Multi-user tightness losses 2. Implications and separations in the CPA setting 3. Implications and separations in the CCA setting 4. Constructions 1. NCE in the Programmable Random Oracle Model: [[Bellare–Rogaway Encryption]] 1. Similar to [[REACT transform]]?? 2. Maybe, but Bellare–Rogaway Encryption still predates it, and is the name of a *technique*, not a scheme. The correct phrasing then (if yes) is that the REACT transform *employs* the BRE technique to achieve IND-CCA security. 3. In light of this, an open problem appears: does the REACT transform achieve NCE-CCA security? 4. Similar question for the FO transform, which was already shown to achieve SSO-CCA from (?) by Jiaxin and Runzhi. 2. Weakening the Assumptions 3. A Priori Indistinguishability and Tightness 5. Concluding Remarks Missing NCE literature? - Go through Joseph's map of works - Go through the NCE citations provided in "Related Work" of this paper: https://eprint.iacr.org/2017/664.pdf - Vi bør også snakke om [[Deniable Encryption]] Things that would be pushed to appendix to make fit within 30 pages: - [x] Sect. 1: Applications - [ ] Sect. 2: Asymptotic versus concrete - (leaving this one in place for now) - [ ] Sect. 3: - [ ] Four kinds of opening - (leaving this one in place for now) - [ ] Theorem proofs - (Carlo will fix) - [ ] Asymptotic interpretations - (Carlo will fix) - [x] Free-bit with bi-openings - [x] Alternative samplers discussion - [ ] SSO’ figure - (leaving this one in place for now) - [x] Sect. 4: everything except ingress and main figure - [x] The entirety of Sect. 5 Based on Martijn's feedback: - [ ] Ditch roadmap (or reintegrate or whatever he was saying). - [ ] Shorten discussion around the four openings and philosophies, ideally a full page shorter than at present. - [ ] Reintroduce Sect. 4.2 Implications to main body, and leave the rest for supp. mat.? - [ ] Sect. 4.1 Hybridization would also be nice ... - [ ] Would be nice to have the constructions-Table somewhere in main body, either at the end or – maybe better – in the introduction. *** Se også: [[Message samplers]], [[Message re-samplers]], [[Tanker om transformasjoner]]