### 1. Overblikk Prosjekt med Yevgeniy Dodis, hvor vi ser etter å generalisere resultatene hans til [[Quantum Random Oracle Model]]. Vi regner med at hovedverktøyet for å få dette til blir [[The Compressed-Oracle Technique]], da bevisene ikke krever reprogrammering, men belager seg tungt på lazy sampling. ### 2. Materiale til [[Forskningskø]] #### Leseliste 1. [C:CDKT19 - Seedless Fruit is the Sweetest: Random Number Generation, Revisited](https://eprint.iacr.org/2019/198) 2. [EC:SFHL20 - On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work](https://eprint.iacr.org/2020/1305) 3. [C:Zhandry19a - How to Record Quantum Queries, and Applications to Quantum Indifferentiability](https://eprint.iacr.org/2018/276) 4. [ITC:BouGrilVer23 - Quantum security of subset cover problems](https://eprint.iacr.org/2022/1474) 5. Stephanie Wehner et al.'s [Quantum to Classical Randomness Extractors](https://arxiv.org/pdf/1111.2026)? #### Neste steg - [x] Finn tid til å møte Yevgeniy neste uke (U24). - [ ] 🎓 Lag github-repo, og inviter Yevgeniy. - [ ] 📱 Hør med Yevgeniy om nytt møte (og beklag den lange ventetiden). Ditto Varun. #### Nylig 1. Leste slidesene Yevgeniy sendte, og oppdaterte leseliste. 2. Inviterte [Varun](https://varun-maram.github.io) til å bli med på møtet neste uke (U24), når enn det blir. ### 3. Møter **Møte 1:** [[12024-06-28]] - Quantum attacker produces classical source with quantum side information. - We have to define what it means that the source has entropy dependent to quantum RO queries. - 1st dimension: does the attacker have quantum side-information or not? Probably the answer is yes. - a) No: meaning A1 is classical. Because intuitively A1 models nature and A2 models the attacker. Then we know how to define min-entropy and stuff. - b) Yes*: A1 is quantum but makes only classical ROM queries. Imagine quantum source, but SHA is only called by classical algorithms. Could say A1 is quantum nature. - c) Yes: A1 is fully quantum. Could apply to quantum RNGs? (... Only if they are imperfect/noisy? Even more realistic ofc.) - d) Yes*: A1 is quantum and makes superposition queries, but state $\Sigma$ has to be passed to *classical* A2. - 2nd dimension: A1 makes classical or quantum queries to RO? - 3rd dimension: Is A2 classical or quantum? - a) Classical: Composes with classical $\Sigma$ (1a, 1d). 1a+3a = the previous work. - b) Quantum A2, definitely makes quantum RO queries. Possibly gets classical. Composes with 1a-1d. - 4th dimension: q2 polynomial or unbounded. (Computational vs I.T.) - a) If q2 is unbounded and A1 is classical, then it doesn't matter if A2 is classical or quantum, and this is already equivalent to previous result - b) If A1 is quantum, then it seems plausible that previous result still holds, but need to check. - There are some interesting existing counterexamples from a decade ago where security would be broken if attacker is quantum. Find? Or just folklore? - Find out what is the appropriate notion of min-entropy in the quantum world? Find out and (gently) present to Yevgeniy. - 2ndly he wants me to teach him [[The Compressed-Oracle Technique]]. - TO-DO: - 1: Write all meaningful combinations of the 4 dimensions ($\leq 16$ in total) and see what is already covered by previous work, and what settings remain to be explored. - 2: Solve all in to-do 1 with monolithic RO, see if there are any surprises. - 3: See if we can solve for non-monolithic, online extractors. - Q1: How to define $H^{\text{quantum}}_\infty\{X | \Sigma, L \}$ - Looking for an existing notion of min-entropy to generalize. Maybe this paper by Stephanie Wehner would be a good starting point. See equation 14, page 9: https://arxiv.org/pdf/1111.2026 - What about classical min-entropy conditioned on quantum queries? Does it make sense? - Interesting paragraph: - ![[Pasted image 20240628174419.png]] - these references will be good to look at. - "This paper might be a little bit of an overkill." (Not sure I agree—we might need the entire formalism.) - Look at [82]: Ta-Shma, "Short seed extractors against quantum storage". Se definition 3.1. "In my opinion this is a little bit restrictive." Is his min-entropy k - n? - 3.2 Random Access Codes - something to familiarize yourself with - and [30], Vidick et al.: "Trevisan’s extractor in the presence of quantum side information" - This actually looks easier to read - there is an update from 2018, and related work includes a later work from 2012 - Also we don't know if this is the state of the art or not. - Hold a seminar talk on how to apply the compressed oracle technique? - Eli - Has a related paper on quantum extractors actually! https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10353160 - *And* he is spending the summer working with Zhandry! - James, one of his post-doc, knows quantum stuff too