[[Quantum Random Oracle Model]]-teknikk fra [Tight adaptive reprogramming in the QROM](https://eprint.iacr.org/2020/1361.pdf) by Grillo, Hövelmanns, Hülsing, and Majenz (AC:GHHM21), se Proposition 1. Tillater adaptive reprogramming, gitt at de reprogrammerte punktene har høy nok entropi til å være statistisk vanskelig å finne (hence "resampling"). *Men* tillater *ikke* å adaptivt velge hva outputen skal være, som er det sentrale trikset i [[Bellare–Rogaway Encryption]], og navngivende for [[Non-Committing Encryption]]. Ahh, men det er her Christian var kløktig i valg av strategi: Reprogrammeringen som kan oppdages av motstanderen er at den resettes i challenge-orakelet; reprogrammeringen i det tilfeldige orakelet lar seg ikke oppdage, *unntatt* nøyaktig når qPCA-reduksjonen vinner, se [[Proof of NCE-CPA in the QROM]]. #### Statement, simplified version > **Proposition 1.** Let $X_1$, $X_2$ and $Y$ be finite sets, and let $A$ be any algorithm issuing $R$ many calls to REPROGRAM and $q$ many (quantum) queries to $O_b$ as defined in Fig. 1. Then the distinguishing advantage of $A$ is bounded by > $P(\text{REPRO}^A_1 \Rightarrow 1) - P(\text{REPRO}^A_0 \Rightarrow 1) \leq \frac{3R}{2} \sqrt{\frac{q}{|X_1|}}$ Her er spillet REPRO og metoden REPROGRAM definert som følger (NB: Motstander har kun classical access til REPROGRAM): ![[Pasted image 20240402090404.png|400]] > Note that apart from already knowing $x_2$, the adversary even learns the part $x_1$ of the position at which $O_1$ was reprogrammed. Hvordan unngår man trivial wins da? Svar: Den måtte ha gjettet $x_1$ *først*, slik at den kunne ha sjekket om verdien endret seg før og etter. #### Sammenligning med tidligere resultater > The above theorem constitutes a significant improvement over previous bounds. In [C:Unruh14](https://link.springer.com/chapter/10.1007/978-3-662-44381-1_1) and [TQC:EatSon15](https://eprint.iacr.org/2015/878), a bound proportional to $q|X_1|^{−1/2}$ for the distinguishing advantage in similar settings, but for R = 1, was given. #### Sharpness Skranken er *sharp* (up to a constant factor)! > What is more, we show in Section 6 that the above bound, and therefore also its generalizations, are tight (sic), by presenting a distinguisher that achieves an advantage equal to the right hand side of Eq. (1) for trivial $X_1$, up to a constant factor. #### Generalisering til andre distribusjoner > In fact, we prove something more general than Proposition 1: We prove that an adversary will not behave significantly different, even if > - the adversary does not only control a portion $x_2$, but instead it even controls the distributions according to which the whole positions $x \coloneqq (x_1, x_2)$ are sampled at which $O_1$ is reprogrammed, > - it can additionally pick different distributions, adaptively, and > - the distributions produce some additional side information $x^\prime$ which the adversary also obtains, > > as long as the reprogramming positions $x$ hold enough entropy. > > ![[Pasted image 20240402091703.png|400]]