A.k.a. "the one-way to hiding lemma", forkortet til O2H; introdusert av Dominique Unruh [EC:Unruh14 - Revocable quantum timed-release encryption](https://eprint.iacr.org/2013/606.pdf) (Lemma 5). En standardteknikk i [[Quantum Random Oracle Model]]. > In a classical setting, this (result) would be straightforward to prove (using lazy sampling of the random oracle). Se også [[Adaptive O2H]]. #### Litteratur - Quiques'21: Kathrin Hövelmanns, The one-way to hiding Lemma ([slides](https://huelsing.net/quiques/wordpress/wp-content/uploads/2021/10/Slides_Quiques_kathrin.pdf), [video](https://www.youtube.com/watch?v=KsEqyUmA46o)) - Open problem: [[Tight O2H]] #### Detaljer Her er lemmaet (lettere edited for readability): > **Lemma 5 (One-way to hiding)** Let $H: \{0,1\}^n \rightarrow \{0,1\}^m$ be a random oracle. Consider an oracle algorithm $A$ that makes at most $q$ queries to $H$. Let $B$ be an oracle algorithm that on input $x$ does the following: sample $i$ from $\{1, \dots, q\}$ and $y$ from $\{0,1\}^m$, run $A^H(x,y)$ until (just before) the $i$-th query, measure the argument of the query in the computational basis, output the measurement outcome. (When $A$ makes less than $i$ queries, $B$ outputs $\perp$.) > > Let $P_A^1$ be the probability that for $x$ uniformly sampled from $\{0,1\}^n$, $A^H(x, H(x))$ evaluates to $1$; let $P_A^2$ be the probability that for $x$ and $y$ uniformly sampled from $\{0,1\}^n$, $\{0,1\}^m$ respectively, $A^H(x, y)$ evaluates to $1$, and let $P_B$ be the probability that for $x$ uniformly sampled from $\{0,1\}^n$, $B^H(x)$ (with $B$ as specified above) outputs $x$. > > Then $|P_A^1 - P_A^2| \leq 2q \sqrt{P_B}$. Så, intuitivt, gitt at reduksjonen $B$ opererer som spesifisert, så kan man benytte lemmaet til å gå fra sannsynligheten for å finne $x$ til sannsynligheten for å skille et tilfeldig orakel fra sann tilfeldighet. Med andre ord: One-way to (indistinguishability, also known as) hiding. For å forklare det lettere forvirrende faktumet at $B$ blir bedt om å outputte sin egen input: > Note that this even holds when the adversary gets $x$ as an input. We may still get non-trivial bounds on the probability $P_B$ if we can show that $A$ does not query $x$ from $H$. This is useful, for example, when we try to show that $H(x)$ and $y$ are indistinguishable to an adversary $C$ that gets $f(x)$ where $f$ is a one-way function: We construct an adversary $A(x, y)$ that calls $C(f(x), y)$, and prove that $A(x, y)$ queries $x$ with negligible probability, which follows immediately from the one-wayness of $f$ and the construction of $A$. Men: > If we try to apply the same technique in the quantum setting, we run into a problem. We would like to say that the probability of distinguishing $H(x)$ and $y$ is bounded by the probability that $A$ queries $x$ from $H$. However, since $H$ can be queried in superposition, it is not even clear what that means. E.g., if $A$ queries $\sum_{x\in X}|x\rangle$ with $X$ being the domain of $H$, should we say that $A$ queried $x$ or not? Also, we cannot, after the execution, talk about the inputs of past queries (such as "all the queries made contain $x$ only with small amplitude"), because to speak about them afterwards would mean to measure or copy them during the execution. And that would disturb the execution of the adversary. The situation is further complicated by the possibility that the queries are entangled with the adversary's state. En annen måte å tenke på det på er at queries kan bli *uncomputed*, i hvilket tilfelle det ikke gir noe mening å snakke om hva querien er. Og her er det trikset kommer inn: > To circumvent these difficulties, we do not execute the adversary $A$ directly, but instead define a new adversary $B$ who runs $A$, but at some random query stops and measures the input to the query. The probability $P_B$ that this adversary $B$ measures $x$ is the quantum analogue to the probability that a classical $A$ queries $x$ in some query. Og slik bruker man det: > For example, if we wish to show that an adversary $C$ does not distinguish $H(x)$ and $y$ given $f(x)$, we do the following: $A(x,y)$ calls $C(f(x),y)$. To show indistinguishability, we then need to show that $P_B$ is negligible. $P_B$ is the probability that we measure $x$ if we run $C(f(x),y)$, stop at a randomly chosen $H$-query, and measure the query argument. From the one-wayness of $f$, we get that $P_B$ is negligible. Hence $H(x)$ and $y$ are indistinguishable given $f(x)$. Beviset er forholdsvist komplekst, men det fine med dette lemmaet er at det er mye enklere å *bruke* enn det er å bevise. ### Alternativ formulering Gitt at A og B skal brukes som subrutiner i lengre reduksjoner, tror jeg jeg foretrekker å si at lemmaet holder *for alle* (potensielt ikke-deterministiske) funksjoner $f$, når A og B blir gitt $f(x)$ som input. Er rimelig sikker på at dette er ekvivalent, gitt at B bare videresender $x$ til A i den opprinnelige versjonen. #### Bevis (Kommandoer er samlet i [[LaTeX-kommandoer]]) La motstanderen $\Eve$ bestå av tre sett av [[Kvantebit]]er, "A", "K", og "V".[^1] La $O_H$ være den unitære transformasjonen $\ket{a, k, v} \rightarrow \ket{a, k, v \oplus H(k)}$, hvor $\ket{a, k, v} = \ket{a} \ket{k} \ket{v}$ tilhører hvert av de tre respektive settene med qubits. La $U$ være den unitære transformasjonen som tar $\Eve$ til neste tilstand etter en forespørsel til $H$.[^2] La $\ket{\psi_i}$ være tilstanden etter til $\Eve$ etter $i$ forespørsler til $H$. Én forespørsel til $H$ leder da til følgende oppdatering av tilstanden: $\ket{\psi_i} = \ket{a, k, v} \longrightarrow U O_H \ket{\psi_i} = U \ket{a, k, v \oplus H(k)} = \ket{\psi_{i+1}}$. La $\ket{\psi_0} = \ket{\psi(x, y)}$ være en initiell tilstand som avhenger av inputen $x,y$ til $\Eve$.[^5] Vi har da at $\ket{\psi_i} = (U O_H)^i \ket{\psi(x,y)}$. Videre lar vi $\ket{\psi_i}$ for en gitt $H \in \ROspace$, $x \in \bin^n$ og $y \in \bin^m$ skrives $\ket{\psi^H_i(x,y)}$.[^4] Husk at det tilfeldige orakelet er en tilfeldig funksjon $H: \bin^n \rightarrow \bin^m$. Sannsynligheten for at et uniformt valgt tilfeldig orakelet er en gitt $H \in \ROspace$ er $2^{-m\cdot2^n}$, og sannsynligheten for at en uniformt valgt input leder til en konkret verdi $x \in \{ 0, 1 \}^n$ er $2^{-n}$, og tilsvarende er sannsynligheten for en gitt output $y$ lik $2^{-m}$. La $\alpha = 2^{-m\cdot2^n - m - n}$ være sannsynligheten for en gitt $H$, $x$, og $y$. La $M$ være den ikke-unitære operasjonen som brukes til å observere $\psi_i$ og gir en klassisk output. La summen $\Sigma_{H \in \ROspace} \Sigma_{x \in \bin^n} \Sigma_{y \in \bin^m}$ for enkelhetens skyld skrives $\Sigma_{H,x,y}$. Sannsynligheten for at $\Eve^H(x, y)$, for tilfeldig valgt $y$, outputter $1$ er da gitt ved: $P^2_\Eve = \Sigma_{H,x,y}\ \alpha \cdot \prob{1 \leftarrow M(\ket{\psi^H_q(x,y)})} \coloneqq \Sigma_{H,x,y}\ \alpha \cdot b^H_{x,y}$. For en gitt $x, y$, la $\ROprog \in \ROspace$ være funksjonen som er lik $H$ på alle punkter unntatt $x$, og $\ROprog(x) = y$.[^3] Da har vi at sannsynligheten for at $\Eve^{H}(x, H(x))$ outputter 1 nødvendigvis må være den samme som sannsynligheten for at $\Eve^{\ROprog}(x, y)$ outputter 1 (når sannsynligheten tas over alle $H$, $x$ og $y$), slik at vi har: $P^1_\Eve = \Sigma_{H,x,y}\ \alpha \cdot \prob{1 \leftarrow M(\ket{\psi^{\ROprog}_i(x,y)})} \coloneqq \Sigma_{H,x,y}\ \alpha \cdot b^{\ROprog}_{x,y}$. Reduksjonen $\Red$ opererer som følger: $\Red^H(x)$ trekker en tilfeldig $i$ fra $[q]$ og $y$ fra $\bin^m$, og måler "K"-registrene til tilstanden $\ket{\psi^H_{i-1}(x,y)}$, og outputter resultatet. La $Q_x$ være den ortogonale projektoren som projiserer registrene "K" på $\ket{x}$, altså at $\abs{Q_x \ket{\psi}}^2$ er sannsynligheten for at observasjon av "K"-registrene gir output $x$.[^6] Da har vi: $P_\Red = \Sigma_{H,x,y} \Sigma_{i \in [q]}\ \frac{\alpha}{q} \abs{Q_x \ket{\psi^{H}_{i-1}(x,y)}}^2$. La [[Trace-avstand]]en mellom to [[Tetthetsmatriser]] være $\tracedist(\rho_1,\rho_2)$; for rene tilstander $\rho_1 = \ket{\psi}\bra{\psi}$, $\rho_2 = \ket{\varphi}\bra{\varphi}$ skriver vi for enkelhetens skyld $\tracedist(\ket{\psi},\ket{\varphi})$. La den skildnbare distansen etter forespørsel $i$ være $D^i_{H, x, y} = \tracedist{\ket{\psi^H_i(x,y)},\ket{\psi^{\ROprog}_i(x,y)}}$. Siden trace-avstanden gir en øvre skranke for sannsynligheten for at en måling kan adskille to kvantetilstander, har vi da at for $i = q$, $D^q_{H,x,y} \geq \abs{b^H_{x,y} - b^{\ROprog}_{x,y}}$, mens for $i=0$ har vi så klart $D_0 = \tracedist{\ket{\psi_0(x,y)},\ket{\psi_0(x,y)}} = 0$. For generell $i$ har vi: $D^i_{H, x, y} = \tracedist{\ket{\psi^H_i(x,y)},\ket{\psi^{\ROprog}_i(x,y)}}$ $\quad = \tracedist{ U O_H \ket{\psi^H_{i-1}(x,y)}, U O_{\ROprog} \ket{\psi^{\ROprog}_{i-1}(x,y)}}$ $\quad \leq \tracedist{ U O_H \ket{\psi^H_{i-1}(x,y)}, U O_{\ROprog} \ket{\psi^H_{i-1}(x,y)}} + \tracedist{ U O_{\ROprog} \ket{\psi^H_{i-1}(x,y)}, U O_{\ROprog} \ket{\psi^{\ROprog}_{i-1}(x,y)}}$[^7] $\quad = \tracedist{ U O_H \ket{\psi^H_{i-1}(x,y)}, U O_{\ROprog} \ket{\psi^H_{i-1}(x,y)}} + D^{i-1}_{H, x, y}$, som gir oss: $\abs{b^H_{x,y} - b^{\ROprog}_{x,y}} \leq D^q_{H, x, y} \leq \Sigma_{i \in [q]} \tracedist{ U O_H \ket{\psi^H_{i-1}(x,y)}, U O_{\ROprog} \ket{\psi^H_{i-1}(x,y)}}$. La den unitære operatoren $V_y$ være gitt av $V_y\ket{a,k,v} = V_y\ket{a,k,v\oplus y}$. Da påstår Unruh at $O_{\ROprog} = O_H (1 - Q_x) + V_y Q_x$, og sier at dette kan verifiseres ved å sjekke likningen holder for alle basistilstander $\ket{a, k, v}$. **To-do: Gjør dette!** I det følgende bruker vi også at $O_H = O_H - O_H Q_x + O_H Q_x = O_H(1-Q_x) + O_H Q_x$. Da får vi: $\tracedist{ U O_H \ket{\psi^H_{i-1}(x,y)}, U O_{\ROprog} \ket{\psi^H_{i-1}(x,y)}}$ $\quad = \tracedist{ U O_H(1-Q_x) \ket{\psi^H_{i-1}(x,y)} + O_H Q_x \ket{\psi^H_{i-1}(x,y)}, U O_H (1 - Q_x) \ket{\psi^H_{i-1}(x,y)} + V_y Q_x \ket{\psi^H_{i-1}(x,y)}}$ $\quad \leq 2 \abs{O_H Q_x \ket{\psi^H_{i-1}(x,y)}} = 2 \abs{Q_x \ket{\psi^H_{i-1}(x,y)}}$. Merk hvordan operatorene bytter plass i den siste ulikheten, som gir den siste likheten fordi $O_H$ ikke påvirker "K"-registrene. Ifølge Unruh følger ulikheten fra [[Unruhs Lemma 11]] i det samme paperet, samt at "the left summands in the second trace distance (which are in the image of $(1-Q_x)$) are orthogonal to the right summands (which are in the image of $Q_x$)".[^8] **To-do: Verifiser!** Når vi setter brikkene sammen, får vi: $\abs{P^1_\Eve - P^2_\Eve} = \Sigma_{H,x,y}\ \alpha \cdot \abs{b^H_{x,y} - b^{\ROprog}_{x,y}}$ $\quad \leq \Sigma_{H,x,y}\ \alpha \cdot D^q_{H,x,y}$ $\quad \leq \Sigma_{H,x,y}\Sigma_{i \in [q]}\ \alpha \cdot \tracedist{ U O_H \ket{\psi^H_{i-1}(x,y)}, U O_{\ROprog} \ket{\psi^H_{i-1}(x,y)}}$ $\quad \leq \Sigma_{H,x,y}\Sigma_{i \in [q]}\ \alpha \cdot 2 \abs{Q_x \ket{\psi^H_{i-1}(x,y)}}$ Ved å anvende [[Jensens ulikhet]], får vi angivelig at dette er $\quad \leq 2 q \sqrt{\frac{\alpha}{q} \abs{Q_x \ket{\psi^{H}_{i-1}(x,y)}}^2} = 2 q \sqrt{P_\Red}$, hvilket skulle bevises. **To-do: Verifiser!** ### Varianter - [[Adaptive O2H]] - [[Semi-classical O2H]] - [[Measure-rewind-measure]] - Flere? (Se liste over teknikker i [[Quantum Random Oracle Model]].) [^1]: Uheldig dobbel-bruk av A her, men det ser ut til å være med vilje: "A" er $A$ sin "interne" tilstandsregister, "K" er $H$ sin input-register, og "V" er $H$ sin outputregister. (Men hvorfor "K" og "V" da?) [^2]: Denne svarer dermed til den klassiske tilstanden $s$ som typisk outputtes av f.eks. $A_i$ og blir input til $A_{i+1}$, eller som vi noen ganger har skrevet $A_{\langle s \rangle}$. Intuitivt, så lagrer den informasjonen den lærte fra forespørselen i "A", og klargjør neste forespørsel i "K" og "V". [^3]: Unruh kaller denne funksjonen $H_{xy}$. [^4]: Unruh skriver $\ket{\Psi^i_{Hxy}}$. [^5]: Unruh skriver $\ket{\Psi_{xy}}$. [^6]: Terminologien rundt målinger forvirrer meg enda. Hva, spesifikt, er effekten av $Q_x$ på $\ket{\psi}$? Hvordan ser den ut på matriseform? Er den en unitær operator eller ikke? Er den en POVM? [^7]: Aner ikke hvor denne ulikheten kommer fra. Generalisert trekantulikhet? [^8]: At $(1-Q_x)$ og $Q_x$ er motsetninger av hverandre gir jo intuitivt mening, men hva er "left/right summands" her?