Want counterexample showing separation: a scheme employing multiple Quantum [[Random Oracle Model]] that is secure when they are modelled as independent and insecure when modelled as singular and domain-separated.  First discussed this idea with Jiaxin and Runzhi, and later with Hannah Davis at [[PKC'23]] (Mihir's PhD student and one of the main authors of the original paper). She's been sort-of thinking about something like this as a possible future project – if we do end up working on it, then shoot her an email. ## Neste steg - [ ] 🎓 Diskuter med Joseph og Christian i kontekst [[PQ-NCE and SIMstar]]? Var noe med introduksjonen til [[SIMstar]]-paperet som fikk meg til å tenke at dette kunne blitt brukt som motivasjon. (Fortsatt kanskje nok mat her til å være et eget paper da.) - [ ] 🎓 Skriv ned poly-separation (basert på [[Kvante-kollisjonsøk]]) - [ ] 🎓 Se om det lar seg gjøre å konstruere en eksponentiell separasjon basert på [[Yamakawa-Zhandry]] #### Idea 1: Multiple matching entries Imagine having $n$ QROs that all take the same seed to produce $n$ (ephemeral) keys. The task is to recover the seed.  (Alternatively view $s$ as a long-term secret, and $H(ctr, s)$ as ephemeral secrets as the scheme is being used for counter $ctr$.) If the random oracles are modelled as independent, the optimal strategy is to use grover search against any one of them.  If, however, they are modelled as a single domain-separated QRO, then the door is opened for multiple-matching-entries Grover search (in conjunction with quantum partial search), see: https://en.m.wikipedia.org/wiki/Grover%27s_algorithm #### Idea 2: Collisions across oracles Another idea: a scheme that is broken iff a collision is found between H1 and H2 (e.g. their output is used to one-time pad the message twice); having them modelled as H(1,x), H(2,x) then allows one to use quantum collision finding.  This latter idea might actually become relevant if we imagine a PQ-DL hybrid KEM that hashes it's output before xor-ing the keys (for instance to make a XEM, or to act as a KDF to ensure the outputs are equal-length bit strings).  #### Idea 3: Superpolynomial separation These would only be polynomial separations however. Could we get an exponential one by considering proofs that program trapdoors into the QROs? Maybe leveraging threshold security, using programming to output shares of the secret? Alternatively, could we leverage Zhandry's QRO search task? See: [[Yamakawa-Zhandry]].