### 1. Overblikk Åpent spørsmål fra [[SoK - Public Key Encryption with Openings]]. (Relatert spørsmål: [[How do IND-CCA and SEM-CCA compare in the multi-user setting?]]) Påbegynt prosjekt med Dennis Hofheinz, [[12024-05-31]], hvor vi kom til en overbevisning om at vi kan vise en seperasjon. #### Implikasjoner Dette gir i så fall noen litt luddige implikasjoner, spesielt gitt at åpninger ikke har noe med saken å gjøre: A posteriori indistinguishability og A posteriori simulatability er *incomparable* i CCA-settingen, dog begge (right?) impliserer IND-CCA. Hvis IND-CCA også impliserer ISO-CCA med transmission openings (heeey, det var det *jeg* som beviste), men vi støter på lignende problemer når vi prøver å vise at IND-CCA impliserer SSO-CCA (kanskje vi kan få separasjonen til å funke der *også*? Med mindre den simpelthen følger umiddelbart), så får vi da at uten (eller med trivielle) åpninger så er IND-CCA og ISO-CCA ekvivalente, mens SSO-CCA er *strictly stronger*—mens *med* ikke-trivielle åpninger så er ISO-CCA og SSO-CCA begge strictly stronger enn IND-CCA, men incomparable til hverandre (dog NCE-CCA impliserer begge ... right?). ## Neste steg - [ ] 📖 Sjekk ut HofRup14-paperet. #### Fullførte steg - [x] Lag github-repo, og skriv idéen fra møtet forrige fredag inn i LaTeX, samt noe om tankene over - [x] Email Dennis om møte neste uke eller uken etter - [x] 🎓 Les gjennom forrige møtes møtenotater, og ekstraher til notater i prosjektet. - [x] 🎓 Skriv noe om status. - [x] 📱 Mail om mulig nytt møte (og beklag at det tok så lang tid å komme tilbake til dette). - [x] 🎓 Prøv å fikse bugen i beviset ### Leseliste 1. [TCC:HofRup14 - Standard versus Selective Opening Security: Separation and Equivalence Results](https://iacr.org/archive/tcc2014/83490128/83490128.pdf) ### Mulige publikasjonsvenues - TCC, frist i mai (i fjor var fristen 20. mai) - AsiaCrypt (i Melbourne!), frist i mai (i fjor var fristen 26. mai) ### 3. Tanker Vi vet fra implikasjoner at med transmission openings, så må SSO-CCA implisere ISO-CCA (via IND-CCA). Kan jeg gi et direkte bevis? Trodde jeg fant et bevis—så langt kom jeg før jeg innså bugen: ![[Pasted image 20240614165522.png]] ### 4. Møter **Møte 2:** [[12024-07-05]] - If ell is very small, then the probability of the bad event happening might be noticeably different between adversary and distinguisher (e.g. simulators makes it be twice the original value). Can we make a counterexample exploiting this? - one over n squared distribution, i.e. prob of 1st message is 1, 2nd is 1 over 4, 3rd is one over 9, etc (up to normalization). Then the probability that you pick any number is still significant. Can pick the message vector a priori, but hard to split ...? (He stopped thinking about it at this point.) - Have to assume that p is bigger than the inverse of a polynomial. - Add an asymptotic interpretation. - Do we need to add a lower bound on ell in order for the - could say for all ell that is bigger than p times some constant c, plus probably some term that depends on this other c, something that would account for the difference between the probability for badm in the simulation and in the real experiment. - in the asymptotic setting, there can't be too much difference between the probabilities of badm in the real and ideal setting, otherwise we would have a way of distinguishing. - Can the simulator maximize the probability of badm? Could start with a good simulator and make it a bit worse. Like with some probability epsilon, it shuffles all the messages. In the real world, the probability of this vector being output will be bounded by badm, but in the ideal world this would now be a tuneable parameter. We need to bound the difference between badm-real and badm-ideal. - Maybe you need to invoke this assumption twice, have one distinguisher that checks the difference in badm, and a second distinguisher that works as I sketched. ("Oh, but now this becomes messy. Sorry, I am not being helpful.") - Could make distinguishing badm its own security game, and then analyze that? (Feels a bit overkill. It is *a* solution, but maybe not the best.) - Or let D be the maximum of D1 and D2, then ... (then the theorem stays clean, but the analysis becomes messy). - On counterexample - could have different samplers with different amount of state, maybe there are two samplers doing the same thing with a tradeoff that one has a higher state and the other has a longer runtime - could have all sorts of ugly corner cases - want to make a - See Magic Functions, p.46, semantic security for independent plaintexts. However, there is a catch in Theorem 7.10. For every number c there exists essentially a simulator that manages to get an advantage that is smaller than 1/n^c. This is not the usual way to define this asymptotically. Then you would want that for all (parameters), there exists a simulator. Basically the polynomial should be quantified last. But this is not what this says: Here it is important that the simulator can depend on the polynomial. This is curious, and so is the proof. "A funny proof." "Selective decommitment" is essentially the same as randomness reveal, i.e. sender opening. - see relation to bellare et al EC12 paper - in the intro they write that there is no contradiction because the magic functions paper, although they *define* SSO-CPA with sender openings the way we are used to see it, they later give an alternative definition of selective decommitment with respect to functions, which is not equivalent to SSO (as implied by the EC12 paper), and their positive result is using this definition. - What Dennis was thinking about was to show that IND-CCA implies IND-CCA' - To get around this, let's start with the case that there is precisely one challenge ciphertext in the vector. (it's ind-cca, so there is just once). And let's say the format is such that you can just insert it once. And you can only place it in its right spot in the vector. We can decrypt all the other ones, so that's fine. However, we do not know what that one is. Intuitively there is a problem: at some point, you get that before the vector was valid, and now it is rejected. As an adversary, I would look for that transition point. However, we (the dec oracle) have help. Namely, through previous choice of ciphertexts to be opened, the dec oracle can ... give hints? - three modes: normal dec, 2nd mode is hashing (?), 3rd mode is breaking. - the help is that we get the openings as well for a random subset - the intuition from the paper before was that on the one hand, the whole vector should have not too many errors. Let's say we have 3n ctxts, then we want (eg) 2n of them are consistent with a random secret vector (using reed-solomon codes to error correct). This is just a component of the solution, because if we didn't have the openings, the adversary could just give you something with too many errors. - later on you check that there were no errors among the n values that were opened - now we're in a good situation: if there are a non-trivial amount of bad positions, then the probability that the unopened - you get a highly unlikely case that there are many errors in the opened messages and not in the unopened ones - because all of the messages were determined previously - the probability that there is only errors among the opened values and not the unopened ones is small - if there are too many errors in the opened values, then we can just reject. And otherwise, we can just decrypt and check, using the reed solomon codes to construct the original message vector and check - if we have 3n ciphertexts, if you only open n of them, then this should give you no information on the whole vector, but if you can open 2n of them then you can uniquely reconstruct it. **Møte 1:** ![[IMG_6560.jpg]]