\[\left\|\rho_{\cY\cR\cK} -  \rho_{\cY\cR} \otimes \frac{1}{2^\ell}\sum_{u}\ket{u}\bra{u}\right\|_1 \leq \frac{1}{2^{1+\frac{1}{2}(\mathbf{H}_\infty(\rho_{\cX\cY}|\cY)-\ell)}}.\]

Small superposition of terms. We will also make use of the following lemma from <cit.>.

Let $\cX,\cY$ be registers of arbitrary size, and let $\{\ket{i}\}_{i \in I}$ and $\{\ket{w}\}_{w \in W}$ be orthonormal bases of $\cX$. Let $\ket{\psi}_{\cX\cY}$ and $\rho_{\cX\cY}$ be of the form
\[\ket{\psi} = \sum_{i \in J}\alpha_i\ket{i}_\cX\ket{\psi_i}_\cY  \text{   and     } \rho = \sum_{i \in J}|\alpha_i|^2\ket{i}\bra{i}_\cX \otimes \ket{\psi_i}\bra{\psi_i}_\cY\]
for some subset $J \subseteq I$. Furthermore, let $\widehat{\rho}_{\cX\cY}$ and $\widehat{\rho}^{\mathsf{mix}}_{\cX\cY}$ be the classical-quantum states obtained by measuring register $\cX$ of $\ket{\psi}$ and $\rho$, respectively, in basis $\{\ket{w}\}_{w \in W}$ to observe outcome $w$. Then,
\[\mathbf{H}_\infty(\widehat{\rho}_{\cX,\cY} | \cY) \geq \mathbf{H}_\infty(\widehat{\rho}^{\mathsf{mix}}_{\cX,\cY} | \cY) - \log|J|.\]

§.§ Sampling in a quantum population

In this section, we describe a generic framework presented in <cit.> for analyzing cut-and-choose strategies applied to quantum states.

Classical sampling stratiegies. Let $A$ be a set, and let $\bq = (q_1,\dots,q_n) \in A^n$ be a string of length $n$. We consider the problem of estimating the relative Hamming weight of a substring $\omega(\bq_{\overline{t}})$ by only looking at the substring $\bq_t$ of $\bq$, for a subset $t \subset [n]$. We consider sampling strategies $\Psi = (P_T,P_S,f)$, where $P_T$ is an (independently sampled) distribution over subsets $t \subseteq [n]$, $P_S$ is a distribution over seeds $s \in S$, and $f: \{(t,\bv) : t \subset [n], \bv \in A^t\} \times S \to \bbR$ is a function that takes the subset $t$, the substring $\bv$, and a seed $s$, and outputs an estimate for the relative Hamming weight of the remaining string. For a fixed subset $t$, seed $s$, and a parameter $\delta$, define $B^\delta_{t,s}(\Psi) \subseteq A^n$ as
\[B^{\delta}_{t,s} \coloneqq \{\bb \in A^n : |\omega(\bb_{\overline{t}}) - f(t,\bb_t,s)| < \delta\}.\]
Then we define the classical error probability of strategy $\Psi$ as follows.

The classical error probability of a sampling strategy $\Psi = (P_T,P_S,f)$ is defined as the following value, paraterized by $0 < \delta < 1$:
\[\epsilon^\delta_{\mathsf{classical}}(\Psi) \coloneqq \max_{\bq \in A^n}\Pr_{t \gets P_T,s \gets P_S}\left[\bq \notin B_{t,s}^\delta(\Psi)\right].\]

Quantum sampling strategies. Now, let $A = A_1,\dots,A_n$ be an $n$-partite quantum system on registers $\cA = \cA_1 \otimes \dots \otimes \cA_n$, where each system has dimension $d$. Let $\{\ket{a}\}_{a}$ be a fixed orthonormal basis for each $\cA_i$. $\cA$ may be entangled with another system $\cE$, and we write the purified state on $\cA$ and $\cE$ as $\ket{\psi}_{\cA\cE}$. We consider the problem of testing whether the state on $\cA$ is close to the all-zero reference state $\ket{0}_{\cA_1}\dots\ket{0}_{\cA_n}$. There is a natural way to apply any sampling strategy $\Psi = (P_T,P_S,f)$ to this setting: sample $t,s$ according to $P_T,P_S$, measure subsystems $\cA_i$ for $i \in [t]$ in basis $\{\ket{a}\}_a$ to observe $\bq_{t} \in A^{|t|}$, and compute an estimate $f(t,\bq_t,s)$.

In order to analyze the effect of this strategy, we first consider the mixed state on registers $\cT$ (holding the subset $t$), $\cS$ (holding the seed $s$), and $\cA,\cE$ that results from sampling $t$ and $s$ according to $P_{TS} = P_TP_S$

\[\rho_{\cT\cS\cA\cE} = \sum_{t,s}P_{TS}(t,s)\ket{t,s}\bra{t,s} \otimes \ket{\psi}\bra{\psi}.\]
Next, we compare this state to an ideal state, parameterized by $0 < \delta < 1$, of the form

\[\widetilde{\rho}_{\cT\cS\cA\cE} = \sum_{t,s} P_{TS}(t,s)\ket{t,s}\bra{t,s} \otimes \ket{\widetilde{\psi}^{ts}}\bra{\widetilde{\psi}^{ts}} \text{   with    } \ket{\psi^{ts}} \in \mathsf{span}\left(B_{t,s}^\delta\right) \otimes \cE,\]
\[\mathsf{span}\left(B_{t,s}^\delta\right) \coloneqq \mathsf{span}\left(\{\ket{\bb} : \bb \in B_{t,s}^\delta\}\right) = \mathsf{span}\left(\{\ket{\bb}: |\omega(\bb_{\overline{t}}) - f(t,\bb_t,s)| < \delta\}\right).\]
That is, $\widetilde{\rho}_{\cT\cS\cA\cE}$ is a state such that it holds with certainty that the state on registers $\cA_{\overline{t}}\cE$, after having measured $\cA_{t}$ and oberserving $\bq_t$, is in a superposition of states with relative Hamming weight $\delta$-close to $f(t,\bq_t,s)$. This leads us to the definition of the quantum error probability of strategy $\Psi$.

The quantum error probability of a sampling strategy $\Psi = (P_T,P_S,f)$ is defined as the following value, parameterized by $0 < \delta < 1$:
\[\epsilon_{\mathsf{quantum}}^\delta(\Psi) \coloneqq \max_\cE\max_{\ket{\psi}_{\cA\cE}}\min_{\widetilde{\rho}_{\cT\cS\cA\cE}}\TD\left(\rho_{\cT\cS\cA\cE},\widetilde{\rho}_{\cT\cS\cA\cE}\right),\]
where the first max is over all finite-dimensional registers $\cE$, the second max is over all state $\ket{\psi}_{\cA\cE}$ and the min is over all ideal state $\widetilde{\rho}_{\cT\cS\cA\cE}$ of the form described above.

Finally, we relate the classical and quantum error probabilities.

For any sampling strategy $\Psi$ and $\delta > 0$,
\[\epsilon_{\mathsf{quantum}}^\delta(\Psi) \leq \sqrt{\epsilon_{\mathsf{classical}}^\delta(\Psi)}.\]

§ SEEDLESS EXTRACTION FROM QUANTUM SOURCES

In this section, we consider the problem of seedless randomness extraction from a quantum source of entropy. The source of entropy we are interested in comes from applying a Hadamard basis measurement to a state that is in a “small” superposition of computational basis vectors. More concretely, consider an arbitrarily entangled system on registers $\cA,\cX$, where $\cX$ is in a small superposition of computational basis vectors. Then, we want to specify an extractor $E$ such that, if $x$ is obtained by measuring register $\cX$ in the Hadamard basis, then $E(x)$ looks uniformly random, even given the “side information” on register $\cA$. Note that seeded randomness extraction in this setting has been well-studied (e.g. <cit.>).

Proofs of the following two theorems are given in <ref>.

§.§ The XOR extractor

First, we observe that if $E$ just XORs all the bits of $x$ together, then the resulting bit $E(x)$ is perfectly uniform, as long as the original state on $\cX$ is only supported on vectors with relative Hamming weight < 1/2.

Let $\cX$ be an $n$-qubit register, and consider any state $\ket{\gamma}_{\cA,\cX}$ that can be written as
\[\ket{\gamma} = \sum_{u: \cH\cW(u) < n/2} \ket{\psi_u}_{\cA} \otimes \ket{u}_\cX.\]
Let $\rho_{\cA,\cP}$ be the mixed state that results from measuring $\cX$ in the Hadamard basis to produce $x$, and writing $\bigoplus_{i \in [n]}x_i$ into the single qubit register $\cP$. Then it holds that
\[\rho_{\cA,\cP} = \Tr_\cX(\ket{\gamma}\bra{\gamma}) \otimes \left(\frac{1}{2}\ket{0}\bra{0} + \frac{1}{2}\ket{1}\bra{1}\right).\]

§.§ The RO extractor

Next, our goal is to extract multiple bits of randomness from $x$. To do this, we model $E$ as a random oracle. We derive a bound on the advantage any adversary has in distinguishing $E(x)$ from a uniformly random string, based on the number of qubits $k$ in the register $\cX$, the number of vectors $C$ in the superposition on register $\cX$, and the number of queries $q$ made to the random oracle. In fact, to be as general as possible, we consider a random oracle with input length $n$, and allow $n-k$ of the bits of the input to the random oracle to be (adaptively) determined by the adversary, while the remaining $k$ bits are sampled by measuring a $k$-qubit register $\cX$.

Let $H : \{0,1\}^n \to \{0,1\}^m$ be a uniformly random function, and let $q,C,k$ be integers. Consider a two-stage oracle algorithm $(A_1^H, A_2^H)$ that combined makes at most $q$ queries to $H$. Suppose that $A_1^H$ outputs classical strings $(T,\{x_i\}_{i \in T})$, and let $\ket{\gamma}_{\cA,\cX}$ be its left-over quantum state,[That is, consider sampling $H$, running a purified $A_1^H$, measuring at the end to obtain $(T,\{x_i\}_{i \in T})$, and then defining $\ket{\gamma}$ to be the left-over state on $\cA$'s remaining registers.] where $T \subset [n]$ is a set of size $n-k$, each $x_i \in \{0,1\}$, $\cA$ is a register of arbitary size, and $\cX$ is a register of $k$ qubits. Suppose further that with probability 1 over the sampling of $H$ and the execution of $A_1$, there exists a set $L \subset \{0,1\}^k$ of size at most $C$ such that $\ket{\gamma}$ may be written as follows:
\[\ket{\gamma} = \sum_{u \in L}\ket{\psi_u}_\cA \otimes \ket{u}_\cX.\]
Now consider the following two games.

* $\mathsf{REAL}$:

* $A_1^H$ outputs $T,\{x_i\}_{i \in T},\ket{\gamma}_{\cA,\cX}$.

* $\cX$ is measured in the Hadamard basis to produce a $k$-bit string which is parsed as $\{x_i\}_{i \in \overline{T}}$, and a left-over state $\ket{\gamma'}_{\cA}$ on register $\cA$. Define $x = (x_1,\dots,x_n)$.

* $A_2^H$ is given $T, \{x_i\}_{i \in T},\ket{\gamma'}_{\cA}, H(x)$, and outputs a bit.

* $\mathsf{IDEAL}$:

* $A_1^H$ outputs $T,\{x_i\}_{i \in T},\ket{\gamma}_{\cA,\cX}$.

* $r \gets \{0,1\}^m$.

* $A_2^H$ is given $T, \{x_i\}_{i \in T},\Tr_\cX(\ket{\gamma}\bra{\gamma}),r$, and outputs a bit.

\[\left|\Pr[\mathsf{REAL} = 1] - \Pr[\mathsf{IDEAL} = 1]\right| \leq \frac{2\sqrt{q}C + 2q\sqrt{C}}{2^{k/2}} < \frac{4qC}{2^{k/2}}.\]

§ NON-INTERACTIVE EXTRACTABLE AND EQUIVOCAL COMMITMENTS

A non-interactive commitment scheme with partial opening in the quantum random oracle model consists of classical oracle algorithms $(\Com,\Open,\Rec)$ with the following syntax.

* $\Com^H(1^\secp,\{m_i\}_{i \in [n]})$: On input the security parameter $\secp$ and $n$ messages $\{m_i \in \{0,1\}^k\}_{i \in [n]}$, output $n$ commitments $\{\com_i\}_{i \in [n]}$ and a state $\state$.

* $\Open^H(\state,T)$: On input a state $\state$ and a set $T \subseteq [n]$, output messages $\{m_i\}_{i \in T}$ and openings $\{u_i\}_{i \in T}$.

* $\Rec^H(\{\com_i\}_{i \in [n]},T,\{m_i,u_i\}_{i \in T})$: on input $n$ commitments $\{\com_i\}_{i \in [n]}$, a set $T$, and a set of message opening pairs $\{m_i,u_i\}_{i \in T}$, output either $\{m_i\}_{i \in T}$ or $\bot$.

The commitment scheme is parameterized by $n = n(\secp)$ which is the number of messages to be committed in parallel, and $k = k(\secp)$ which is the number of bits per message.

§.§ Construction

Extractable and equivocal commitment scheme

Parameters: security parameter $\secp$, number of commitments $n = n(\lambda)$

Random oracle: $H:\zo^{\secp+1} \rightarrow \zo^{\secp+1}$.

* $\Com^{H}(1^\secp,\{b_i\}_{i \in [n]})$: For all $i \in [n]$, sample $r_i \leftarrow \zo^\secp$ and set $\com_i = H(b_i||r_i)$. Set $\state = \{b_i,r_i\}_{i \in [n]}$ and output $(\state, \{\com_i\}_{i \in [n]})$.

* $\Open^{H}(\state, T)$: Parse $\state$ as $\{b_i,r_i\}_{i \in [n]}$ and output $\{b_i,r_i\}_{i \in T}$.

* $\Rec^{H}(\{\com_i\}_{i \in [n]},T,\{b_i,r_i\}_{i \in T})$: Output $\bot$ if there exists $i \in T$ s.t. $H(b_i||r_i) \neq \com_i$. Otherwise output $\{b_i\}_{i \in T}$.

We construct extractable and equivocal bit commitments in the QROM in <ref>. Without loss of generality, a committer can commit to strings of length $>1$ by committing to each bit in the string one by one, and sending all commitments in parallel.

We provide a natural construction, and proofs of extractability and equivocality for this construction in <ref>.

if we get time, we can try to see if we can generalize this

§ THE FIXED BASIS FRAMEWORK: OT FROM ENTANGLEMENT

We first obtain non-interactive OT in the shared EPR model, and then show that the protocol remains secure even when one player does the EPR pair setup.

In this section, we obtain three round OT realizing $\cF_{\SROT}$, and we provide a modification that yields four round chosen input $\cF_{\OT[\secp]}$. The constructions make use of standard BB84 states, therefore we refer to this as the random basis framework.

Instantiate fig:qot-4r-const with any non-interactive commitment scheme that is extractable (<ref>) and equivocal (<ref>). Then the following hold.

* When instantiated with the XOR extractor, there exist constants $A,B$ such that fig:qot-4r-const securely realizes (<ref>) $\cF_{\SROT[1]}$.

* When instantiated with the ROM extractor, there exist constants $A,B$ such that fig:qot-4r-const securely realizes (<ref>) $\cF_{\SROT[\secp]}$.

Furthermore, letting $\secp$ be the security parameter, $q$ be an upper bound on the total number of random oracle queries made by the adversary, and using the commitment scheme from <ref> with security parameter $\secp_\com = 2\secp$, the following hold.

* When instantiatied with the XOR extractor and constants $A = 1100$, $B= 500$, fig:qot-4r-const securely realizes $\cF_{\SROT[1]}$ with $\mu_{\sR^*}$-security against a malicious receiver and $\mu_{\sS^*}$-security against a malicious sender, where

\[
\mu_{\sR^*} = \frac{\sqrt{5}+1}{2^{\secp}}+\frac{148(q + 3200\secp + 1)^3 + 1}{2^{2\secp}} + \frac{25600q\secp}{2^{\secp}},\quad \mu_{\sS^*} = \frac{114q\sqrt{\secp}}{2^{ \secp}}.
\]

This requires a total of $(A+B)\secp = 1600\secp$ BB84 states.

* When instantiated with the ROM extractor and constants $A = 11\ 000, B = 12\ 000$, fig:qot-4r-const securely realizes $\cF_{\SROT[\secp]}$ with $\mu_{\sR^*}$-security against a malicious receiver and $\mu_{\sS^*}$-security against a malicious sender, where

\[
\mu_{\sR^*} = \frac{\sqrt{5}}{2^{\secp}}+ \frac{4q}{2^{18\secp}}+\frac{148(q + 46000\secp + 1)^3 + 1}{2^{2\secp}} + \frac{368000q\secp}{2^{\secp}}, \quad \mu_{\sS^*} =\frac{430q\sqrt{\secp}}{2^{\secp}}.
\]

This requires a total of $(A+B)\secp = 23\ 000\secp$ BB84 states.

Instantiate fig:qot-4r-actual with any non-interactive commitment scheme that is extractable (<ref>) and equivocal (<ref>). Then there exist constants $A,B$ such that fig:qot-4r-actual securely realizes (<ref>) $\cF_{\OT[\secp]}$.

Furthermore, letting $\secp$ be the security parameter, $q$ be an upper bound on the total number of random oracle queries made by the adversary, and using the commitment scheme from <ref> with security parameter $\secp_\com = 2\secp$, for constants $A = 5300, B = 5000$, fig:qot-4r-actual securely realizes $\cF_{\OT[\secp]}$ with $\mu_{\sR^*}$-security against a malicious receiver and $\mu_{\sS^*}$-security against a malicious sender, where

\[
\mu_{\sR^*} = \frac{\sqrt{5}}{2^\secp} + \frac{1}{2^{9\secp}} + \frac{148(q + 2n + 1)^3 + 1}{2^{2\secp}} + \frac{16qn}{2^{\secp}}, \quad \mu_{\sS^*} = \frac{288q\sqrt{\secp}}{2^{\secp}}.
\]

This requires a total of $(A+B)\secp = 10\ 300 \secp$ BB84 states.

Three-round OT protocol realizing $\cF_{\SROT[1]}$.

Ingredients, parameters and notation.

* Security parameter $\secp$ and constants $A,B$. Let $n = (A+B)\secp$ and $k = A\secp$.

* For classical bits $(x,\theta)$, let $\ket{x}_\theta$ denote $\ket{x}$ if $\theta = 0$, and $(\ket{0} + (-1)^x\ket{1})/\sqrt{2}$ if $\theta = 1$.

* A non-interactive extractable and equivocal commitment scheme $(\Com,\allowbreak\Open,\allowbreak\Rec)$, where commitments to 2 bits have size $\ell \coloneqq \ell(\secp)$.

* An extractor $E$ with domain $\{0,1\}^{n-k}$ which is either

* The XOR function, so $E(r_1,\dots,r_{n-k}) = \bigoplus_{i \in [n-k]} r_i$.

* A random oracle $\extro : \{0,1\}^{n-k} \to \{0,1\}^\secp$.

Receiver input: $b \in \{0,1\}, m \in \{0, 1\}^z$, where $z$ is the output length of the extractor.

* Receiver message. $\sR$ performs the following steps.

* Choose $x \leftarrow \{0, 1\}^n$, $\theta \leftarrow \{0, 1\}^n$ and prepare the states $\{\ket{x_i}_{\theta_i}\}_{i \in [n]}$.

* Compute $\left(\state,\{c_i\}_{i \in [n]}\right) \gets \Com\left(\{(x_i, \theta_i)\}_{i \in [n]}\right)$, and send $\{\ket{x_i}_{\theta_i},c_i\}_{i \in [n]}$ to $\sS$.

* Sender message.  $\sS$ performs the following steps.

* Choose $\widehat{\theta} \leftarrow \{0, 1\}^n$. For all $i \in [n]$, measure $\ket{x_i}_{\theta_i}$ in basis $\widehat{\theta_i}$ to get outcome $\widehat{x_i}$.

* Sample a random subset $T$ of $[n]$ of size $k$.
Send $T, \{\widehat{\theta}_i\}_{i \in \overline{T}}$ to $\sR$, where $\overline{T} \coloneqq [n]\setminus T$.

* Receiver message. $\sR$ performs the following steps.

* Divide $\overline{T}$ into 2 disjoint subsets $S_0, S_1$ as follows. Set $I_b = S_0$ and $I_{1-b} = S_1$, where ${S_0 = \{ i \ | \ i \in \overline{T} \wedge \theta_i = \widehat{\theta}_i \}}, {S_1 = \{ i \ | \ i \in \overline{T} \wedge \theta_i \ne \widehat{\theta}_i \}}$.

* Compute $\{(x_i, \theta_i), u_i\}_{i \in T} \gets \Open(\state, T)$.

* Compute $X$ as the concatenation of $\{x_i\}_{i \in I_b}$, set $r_b := E(X) \oplus m$, and sample $r_{1-b} \gets \zo^z$, where $z$ is the output length of extractor.

*  Send $I_0,I_1,\{(x_i, \theta_i), u_i\}_{i \in T}, (r_0, r_1)$ to $\sS$.

* Output computation $\sS$ does the following:

* Abort if $\Rec(\{c_i\}_{i \in T}, \{(x_i, \theta_i), u_i\}_{i \in T}) = \bot$ or if $\exists i \in T$ s.t. $\theta_i = \widehat{\theta}_i$ but $x_i \neq \widehat{x}_i$.

* Compute $\widehat{X}_0, \widehat{X}_1$ as the concatenation of $\{\widehat{x_i}\}_{i \in I_0},\{\widehat{x_i}\}_{i \in I_1}$ respectively. Output $m_0 := E(\widehat{X}_0) \oplus r_0$ and $m_1 := E(\widehat{X}_1) \oplus r_1$.

Four-round OT protocol realizing $\cF_{\OT[\secp]}$. Parts in blue are different than the 3-round OT protocol realizing $\cF_{\SROT[1]}$ in fig:qot-4r-const.

Ingredients, parameters and notation.

* Security parameter $\secp$ and constants $A,B$. Let $n = (A+B)\secp$ and $k = A\secp$.

* For classical bits $(x,\theta)$, let $\ket{x}_\theta$ denote $\ket{x}$ if $\theta = 0$, and $(\ket{0} + (-1)^x\ket{1})/\sqrt{2}$ if $\theta = 1$.

* A non-interactive extractable and equivocal commitment scheme $(\Com,\allowbreak\Open,\allowbreak\Rec)$, where commitments to 2 bits have size $\ell \coloneqq \ell(\secp)$.

* A universal hash function $h : \zo^{p(\secp)} \times \zo^{\leq B\secp} \rightarrow \zo^\secp$.

Sender input: $m_0,m_1 \in \zo^\secp$, Receiver input: $b \in \{0,1\}$.

* Receiver message. $\sR$ performs the following steps.

* Choose $x \leftarrow \{0, 1\}^n$, $\theta \leftarrow \{0, 1\}^n$ and prepare the states $\{\ket{x_i}_{\theta_i}\}_{i \in [n]}$.

* Compute $\left(\state,\{c_i\}_{i \in [n]}\right) \gets \Com\left(\{(x_i, \theta_i)\}_{i \in [n]}\right)$.

Send $\{\ket{x_i}_{\theta_i},c_i\}_{i \in [n]}$ to $\sS$.

* Sender message.  $\sS$ performs the following steps.

* Choose $\widehat{\theta} \leftarrow \{0, 1\}^n$. For all $i \in [n]$, measure $\ket{x_i}_{\theta_i}$ in basis $\widehat{\theta_i}$ to get outcome $\widehat{x_i}$.

* Sample a random subset $T$ of $[n]$ of size $k$. Send $T, \{\widehat{\theta}_i\}_{i \in \overline{T}}$ to $\sR$, where $\overline{T} \coloneqq [n]\setminus T$.

* Receiver message. $\sR$ performs the following steps.

* Divide $\overline{T}$ into 2 disjoint subsets $S_0, S_1$ as follows. Set $I_b = S_0$ and $I_{1-b} = S_1$, where ${S_0 = \{ i \ | \ i \in \overline{T} \wedge \theta_i = \widehat{\theta}_i \}}, {S_1 = \{ i \ | \ i \in \overline{T} \wedge \theta_i \ne \widehat{\theta}_i \}}$.

* Compute $\{(x_i, \theta_i), u_i\}_{i \in T} \gets \Open(\state, T)$.

* Compute $X$ as the concatenation of $\{x_i\}_{i \in I_b}$, set $r_b := E(X) \oplus m$, and sample $r_{1-b} \gets \zo^z$, where $z$ is the output length of extractor.

*  Send $I_0,I_1,\{(x_i, \theta_i), u_i\}_{i \in T}$, $(r_0, r_1)$ to $\sS$.

* Sender message. $\sS$ and $\sR$ do the following:

* $\sS$ does the following:

* Abort if $\Rec(\{c_i\}_{i \in T}, \{(x_i, \theta_i), u_i\}_{i \in T}) = \bot$ or if $\exists i \in T$ s.t. $\theta_i = \widehat{\theta}_i$ but $x_i \neq \widehat{x}_i$.

* Compute $\widehat{X}_0, \widehat{X}_1$ as the concatenation of $\{\widehat{x_i}\}_{i \in I_0},\{\widehat{x_i}\}_{i \in I_1}$ respectively.

* Sample $s \leftarrow \zo^{p(\secp)}$, send $(s,ct_0 = m_0 \oplus h(s,\widehat{X}_0),ct_1 = m_1 \oplus h(s,\widehat{X}_1))$ to $\sR$.

* $\sR$ computes $X$ as the concatenation of $\{x_i\}_{i \in I_b}$ and outputs $ct_b \oplus h(s,X)$.

§.§ Three-round random-input OT

In this section, we prove <ref>.

Sender Security

Receiver Security.
Let $\SimEqu = (\SimEqu.\RO,\SimEqu.\Com,\SimEqu.\Open)$ be the simulator for the equivocal commitment scheme $(\Com^{\comro},\Open^{\comro},\Rec^{\comro})$ (according to <ref>). We describe the simulator $\Sim[\sS^*]$ against a malicious receiver $\sS^*$. $\simu$ will answer random oracle queries to $\comro$ using $\SimEqu.\RO$.

Additionally, if randomness extractor $E$ in the protocol is $\extro$, then its simulation is accomplished via queries to an on-the-fly random oracle simulator $\simro.\RO$ as mentioned in Imported Theorem <ref>.

The Simulator.

* Prepare $n$ EPR pairs on registers $\{\cS_i, \cR_i\}_{i \in [n]}$

* Compute the commitments strings $\{ c_i \}_{i \in [n]}$ by calling $\SimEqu.\Com$ for the underlying commitment scheme.

* Send $\{\cS_i\}_{i \in [n]}$ and $\{ c_i \}_{i \in [n]}$ to $S^*$.

* Receive $T, \{ \widehat{\theta_i} \}_{i \in \overline{T}}$ from $S^*$.

* For all $i \in T$, sample $\theta_i \leftarrow \{+, \times \}$ and measure $\cR_i$ in the basis $\theta_i$ to obtain outcome $x_i$. For all $i \in \overline{T}$, measure $\cR_i$  in the basis $\widehat{\theta_i}$ to obtain outcome $\widetilde{x_i}$.

* Call $\SimEqu.\Open(\{ x_i, \theta_i \}_{i \in [T]})$ of the underlying commitment scheme to obtain openings $\{ (x_i, \theta_i), u_i \}_{i \in [T]}$.

* Generate a partition $I_0, I_1$ of $\overline{T}$ as follows: for every $i \in \overline{T}$, flip a random bit $b_i$ and place $i \in I_{b_i}$.

* Receives $m_0, m_1$ from $\cF_{\SROT}$ functionality.

* Set $r_0 = E(\{ \widetilde{x_i} \}_{i \in I_0}) \oplus m_0$,  $r_1 = E(\{ \widetilde{x_i} \}_{i \in I_1}) \oplus m_1$.

* Send $I_0, I_1, \{ (x_i, \theta_i), u_i \}_{i \in T}, (r_0, r_1)$ to $S^*$.

Fix any adversary $\{ \sS^*_\secp,\sD_\secp,(b_\secp, m_\secp)\}_{\secp \in \bbN}$, where $\sS^*_\secp$ is a QIOM that corrupts the sender, $\sD_\secp$ is a QOM, and $(b_\secp, m_\secp)$ is the input of the honest receiver.
For any receiver input $b_\secp \in \{0,1\}, m_\secp \in \zo^v$, where $v$ is the output lenght of extractor, consider the random variables $\Pi[ \sS^*_\secp,\sD_\secp,(b_\secp, m_\secp)]$ and
$\widetilde{\Pi}_{\cF^{\mathsf{OT}}}[ \Sim_\secp,\sD_\secp,(b_\secp, m_\secp)]$
according to Definition <ref> for the protocol in Figure <ref>.
Let $q(\cdot)$ denote an upper bound on the number of queries of $\sS^*_\secp$ and $\sD_\secp$.
We will show that :

\[\bigg|\Pr[\Pi[ \sS^*_\secp,\sD_\secp,(b_\secp, m_\secp)] = 1] - \Pr[\widetilde{\Pi}_\cF[ \Sim_\secp,\sD_\secp,(b_\secp, m_\secp)] = 1]\bigg| = \mu(\secp,q(\secp))\]

where the term on the right corresponds to the security error in the equivocal commitment.

This is done via a sequence of hybrids, as follows [If randomness extractor $E$ in the protocol is $\extro$, then there will be an additonal hybrid between $\Hyb_0$ and $\Hyb_1$ where we switch from using $\extro$ to simulating it using an efficient on-the-fly random oracle simulator $\simro.\RO$ as mentioned in Imported Theorem <ref>. This hybrid's (perfect) indistinguishability will follow directly from the indistinguishable simulation property as mentioned in Imported Theorem <ref>.]:

* $\Hyb_0:$ The output of this hybrid is the real distribution $\Pi[ \sS^*_\secp,\sD_\secp,(b_\secp, m_\secp)]$.

* $\Hyb_1:$

This is the same as the previous hybrid except that instead of running the $\Com$ and  $\Open$ algorithm, as in Figure <ref>, the challenger now answers random oracle queries to $\comro$ using $\SimEqu.\RO$, the random oracle simulator for the commitment scheme $(\Com^\comro,\allowbreak\Open^\comro,\allowbreak\Rec^\comro)$. Additionally, it performs the following modified steps on behalf of $\sR$:

* Prepare the commitments by calling $\SimEqu.\Com$ for the underlying commitment protocol.

* Prepare the opening by calling $\SimEqu.\Open(\{x_i, \theta_i\}_{i \in [n]})$, where $\{x_i, \theta_i\}_{i \in [n]}$ are as defined in the previous hybrid.

* $\Hyb_2:$

This is the same as the previous hybrid except the following change: in protocol round 1, the challenger calls

Algorithm EPR-to-BB84$(i)$ for every $i \in [n]$ to obtain $\ket{x_i}_{\theta_i}$.

Algorithm EPR-to-BB84 $(i)$:

* Sample EPR pair on registers $\cS_i, \cR_i$.

* Randomly sample a basis $\theta_i \leftarrow \{+, \times\}$

* Measure $\cR_i$ in the basis $\theta_i$ and let the outcome be $x_i$

* Use $\cS_i$ as a BB84 state $\ket{x_i}_{\theta_i}$

* $\Hyb_3$:

This is the same as the previous hybrid, except that in protocol round 1, the challenger sends halves of $n$ EPR pairs $\{\cS_i\}_{i \in [n]}$, prepared by executing Step 1 of the algorithm EPR-to-BB84, to $\sS^*$ while retaining $\{ \cR \}_{i \in [n]}$ with itself.
After round 2, the challenger runs Steps 2 and 3 of the Algorithm EPR-to-BB84 for every $i \in [n]$ to obtain $\{x_i, \theta_i \}_{i \in [n]}$. The resulting values $\{x_i, \theta_i \}_{i \in T}$ are used as inputs to $\SimEqu.\Open$ to prepare openings in round 3. Step 4 of the Algorithm EPR-to-BB84$(i)$ is not relevant in this hybrid.

That is, the challenger sends halves of EPR pairs to $\sS^*$ in round
e values $\{x_i, \theta_i \}_{i \in T}$ obtained as a result of performing Step 2 and Step 3 of Algorithm EPR-to-BB84 as inputs to $\cS_\Equ$ algorithm to prepare the openings in Step 3c.  The output of this hybrid consists of the final state of the malicious sender $S^*$ and the output of the honest receiver $R$.

* $\Hyb_4$:
This is the same as the previous hybrid, except the following changes. After round 2, the challenger samples $\{\theta_i\}_{i \in [16\secp]}$ uniformly in $\{+, \times\}$ and only runs the algorithm EPR-to-BB84$(i)$ for every $i \in [T]$, leaving the remaining halves of EPR pairs unmeasured.
It generates a partition $I_0, I_1$ of $\overline{T}$ as in the previous hybrid using the values $\{\theta_i\}_{i \in \overline{T}}$.

Next after round 4, for all $i \in I_b$, the challenger measures their halves of EPR pairs in the basis $\{ {{\theta}_i} \}_{i \in I_b}$. Denote measurement outcomes by $\{ \widetilde{x_i} \}_{i \in I_b}$.
Using the resulting outcomes, the challenger computes $\widetilde{m_b} := ct_b \oplus h(\widehat{s} || \{\widetilde{x}_i\}_{i \in I_b})$.

* $\Hyb_4$:

This is the same as the previous hybrid, except the following changes. After round 2, the challenger runs the Steps 2-3 of algorithm EPR-to-BB84 for every $i \in [T]$, leaving $\{\cR_i\}_{i \in \overline{T}}$ unmeasured.
It generates a partition $I_0, I_1$ of $\overline{T}$ as follows: for every $i \in \overline{T}$, flip a random bit $b_i$ and place $i \in I_{b_i}$.

For all $i \in \overline{T}$, the challenger measures $\{\cR_i\}_{i \in \overline{T}}$  in the basis $\{ \widehat{\theta_i} \}_{i \in \overline{T}}$ where $\{ \widehat{\theta_i} \}_{i \in \overline{T}}$ was obtained from $\sS^*$ in round $2$. Denote measurement outcomes by $\{ \widetilde{x_i} \}_{i \in \overline{T}}$.
Using the resulting outcomes, the challenger sets $r_b := E(\{\widetilde{x}_i\}_{i \in I_b}) \oplus m$.

* $\Hyb_5:$ This is the same as the previous hybrid, except that in Round 3, the challenger sets $r_0 = E(\{ \widetilde{x_i} \}_{i \in I_0}) \oplus m_0$,  $r_1 = E(\{ \widetilde{x_i} \}_{i \in I_1}) \oplus m_1$  where $m_0, m_1$ are received from $\cF_{\SROT}$

The output of this experiment is identical to the ideal distribution $\widetilde{\Pi}_{\cF_{\SROT}}[ \allowbreak \Sim_\secp,\sD_\secp,(b_\secp, m_\secp)]$.

* $\Hyb_6 [\textbf{Removing the receiver choice bit}]:$  $\simu$ behaves exactly as $\Hyb_5$ except that in Step 4, instead of using $b$ to define the sets $I_0$ and $I_1$, it instead sets $I_0 := S_0$ and $I_1 := S_1$. It then completes the remaining steps as mentioned in the previous hybrid.

The output of this hybrid consists of the final state of the malicious sender $S^*$ and the output of the ideal-world receiver.

We show

that $|\Pr[\Hyb_5=1]-\Pr[\Hyb_0=1]| \leq \mu(\secp,q(\secp))$, where $(\Com^\comro, \allowbreak \Open^\comro, \allowbreak \Rec^\comro)$ is a $\mu(\secp,q(\secp))$-equivocal bit commitment scheme, where $(\Com^\comro,\allowbreak\Open^\comro,\allowbreak\Rec^\comro)$ is a $\mu(\secp,q(\secp))$-equivocal bit commitment scheme, where $\mu(\secp,q, n_\com) = \frac{2qn_{\com}^{1/2}}{2^{\secp_\com/2}}$ for the specific commitment scheme that we construct in Section <ref>, where $n_{\com}$ is the number of bit commitments and $\secp_\com$ is the security parameter for the commitment scheme. Later, we will set $n_\com = c_1 \secp$ and $\secp_\com = c_2 \secp$ for some fixed constants $c_1, c_2$. Thus $\mu$ will indeed be a function of $\secp$ and $q$. We now procced with the proof by arguing the computational indistinguishability of each pair of consecutive hybrids in the above sequence.

$|\Pr[\Hyb_0=1]-\Pr[\Hyb_1=1]|\leq \mu(\lambda, q(\lambda))$.

Suppose there exists an adversary $\Adv_\secp$ corrupting $\sS$, a distinguisher $\sD_\secp$, quantuam states $\rho_\secp, \sigma_\secp$ and a bit $b$ such that,

\[
\bigg|\Pr[\Hyb_0=1]-\Pr[\Hyb_1=1]\bigg| > \mu(\lambda, q(\lambda))
\]

We will construct a reduction $\{\Adv^*_{\secp} = (\Adv_{\RCommit,\secp},\allowbreak\Adv_{\ROpen,\secp},\allowbreak\sD^*_{\secp})\}_{\secp \in \bbN}$ that makes at most $q(\secp)$ queries to the random oracle, and contradicts the $\mu$-equivocality of the underlying commitment scheme $(\Com^\comro,\allowbreak\Open^\comro,\allowbreak\Rec^\comro)$ as defined in Definition <ref>. In the following reduction, all random oracle queries to $\comro$ will be answered by the equivocal commitment challenger.

* Initalize the OT protocol with between honest receiver $\sR$ and $\Adv(\rho_\secp)$ corrupting $\sS$.

* After $\sR$ samples $\{(x_i,  \theta_i)\}_{i \in [n]}$, output the intermediate state $\rho^*_{\secp, 1}$ representing the joint state of $\sS$ and $\sR$ along with $\{(x_i,  \theta_i)\}_{i \in [n]}$.

The commitment challenger obtains $\{(x_i,  \theta_i)\}_{i \in [n]}$ and returns a set of commitments $\{ \com_i \}_{i \in [n]}$.

$\Adv_{\ROpen,\secp}(\rho^*_{\secp, 1}, \{ \com_i \}_{i \in [n]})$: Use $\rho^*_{\secp, 1}$ to initialize the joint state of $\sS$ and $\sR$, and $\{ \com_i \}_{i \in [n]}$ as commitments of $\sR$ in the protocol. Output the new joint state $\rho^*_{\secp, 2}$ after $\sR$ has computed $I_0$ and $I_1$.

The challenger returns $\{u_i\}_{i \in [n]}$ which is then fed to the following distinguisher (along with the information $\{ \com_i, (x_i, \theta_i) \}_{i \in [n]}$ from the aforementioned execution).

$\sD^*_\secp(\rho^*_{\secp, 2}, \{ \com_i, (x_i, \theta_i), u_i \}_{i \in [n]}):$

* Use $\rho^*_{\secp, 2}$ to initialize the joint state of $\sS$ and $\sR$. Run it until completion using $\{ (x_i, u_i) \}_{i \in T}$ as openings of $\sR$.

* Let $\tau_\secp^*$ be the final state of $\Adv$ and $y^*$ be the output of $\sR$. Run $\sD_\secp(\sigma_\secp, \tau^*_\secp, y^*)$ and output the bit $b$ returned by it.

By construction, when the challenger executes $(\Com^\comro,\allowbreak\Open^\comro)$, the reduction will generate a distribution identical to $\Hyb_0$. Similarly, when the challenger executes $(\SimEqu.\Com, \SimEqu.\Open)$ algorithms, the reduction will generate a distribution identical to $\Hyb_1$. Therefore, the reduction  directly contradicts the $\mu$-equivocality of the underlying commitment scheme $(\Com^\comro,\allowbreak\Open^\comro,\allowbreak\Rec^\comro)$ according to Definition <ref>, as desired.

$\Pr[\Hyb_1=1] = \Pr[\Hyb_2=1]$

The only difference between the two hybrids is a syntactic change in the way BB84 states are sampled in round $1$. The distribution $(x_i, \theta_i, \ket{x_i}_{\theta_i})_{i \in [16\secp]}$ resulting from these syntactically different sampling strategies is identical in both hybrids.

$\Pr[\Hyb_2=1] = \Pr[\Hyb_3=1]$

$\Hyb_3$ constitutes a purification of the receiver's strategy in round $1$ and since actions on disjoint subsystems commute, this does not affect the joint distribution of the sender's view and receiver output.

$\Pr[\Hyb_3=1] = \Pr[\Hyb_4=1]$

$\Hyb_4$ constitutes a purification of the receiver's strategy in round $3$ and since actions on disjoint subsystems commute, this does not affect the joint distribution of the sender's view and receiver output.

$\Pr[\Hyb_4=1] = \Pr[\Hyb_5=1]$

Assuming correctness of $\cF_{\SROT}$, the two hybrids are identical.Suppose ideal world receiver's input is $(b = 0, m)$. In this case, $\cF_{\SROT}$ sends $m_0 = m, m_1$ to the challenger where $m_1 \gets \zo^v$. In $\Hyb_5$, this would lead to $r_0 = E(\{ \widetilde{x_i} \}_{i \in I_0}) \oplus m$ (which is same as $\Hyb_4$) and $r_1 = E(\{ \widetilde{x_i} \}_{i \in I_1}) \oplus m_1$ (which is uniformly random as in $\Hyb_4$). Moreover, the output on sender side in $\Hyb_5$ is $(E(\{ \widetilde{x_i} \}_{i \in I_0}) \oplus r_0, E(\{ \widetilde{x_i} \}_{i \in I_1}) \oplus r_1)$ = $(m, m_1)$ as desired.
The case when ideal world receiver bit $b$ is $1$ can be proved in a similar way. Therefore for any fixing of the adversary's state and receiver's input, the two hybrids result in identical distributions.

Combining all the claims, we get that $|\Pr[\Hyb_0 = 1] - \Pr[\Hyb_5 = 1]| \le  \mu(\lambda, q(\lambda))$. In Theorem <ref>, we derived  $\mu(\secp,q, n_\com) = \frac{2qn_{\com}^{1/2}}{2^{\secp_\com/2}}$. We will now state the parameters for $n_\com$ and $\lambda_\com$.

* XOR extractor: Plugging $\lambda_\com = 2 \secp$, $n_\com = 2n$ (as we are committing to 2 bits at a time) where $n = 1600\secp$ (this setting of $n$ is the same as that needed in the sender security part of the proof), we get $\frac{114q\sqrt{\secp}}{2^{\secp}}$ security against a malicious sender.

* ROM extractor: Plugging $\lambda_\com = 2 \secp$, $n_\com = 2n$ (as we are committing to 2 bits at a time) where $n = 23\ 000\secp$ (this setting of $n$ is the same as that needed in the sender security part of the proof), we get $\frac{430q\sqrt{\secp}}{2^{\secp}}$ security against a malicious sender.

old text below
In $\Hyb_3$, the operation performed by the simulator for computing the sets $I_0, I_1$ is independent of the measurement outcomes $\{x_i\}_{i \in \overline{T}}$. Specifically, this is because the operation only takes as inputs $\overline{T}$, randomly sampled $\{ \theta_i \}_{i \in \overline{T}}$, and $\{ \widehat{\theta_i} \}_{i \in \overline{T}}$. Therefore, we can commute this operation with and outputs the set $I_0, I_1$. Hence we can prepone this operation before performing the measurements

Note that the transcript distribution is identical in both hybrids because the information about operations performed on second EPR halves for all $i \in \overline{T}$ is never used anywhere in the protocol except the last Step 7 (which is local to the receiver). Hence, all we need to show is that the output distribution of $R$ doesn't change. This follows from the fact that the way $\widetilde{m_b}$ is defined is identical in both hybrids. Specifically, in both the hybrids, it is defined as $ct_b \oplus h(\widehat{s} || \{\widetilde{x_i} \}_{i \in I_b})$ where $\{\widetilde{x_i} \}_{i \in I_b}$ are the receiver's measurement values at indices where $\widehat{\theta_i} = \theta_i$.

We first observe that the distributions $S_0$ and $S_1$ are identical over the randomness of sampling  $\{ \theta_i \}_{i \in \overline{T}}$.

This is because when $\{ \theta_i \}_{i \in \overline{T}}$ is sampled uniformly at random, the following holds true: For all $i \in \overline{T}$, $\Pr[\widehat{\theta_i} = \theta_i] = \frac{1}{2}$. Hence, $(S_0, S_1)$ form a uniformly random partition of the set $\overline{T}$ and the distribution of $(S_0, S_1)$ is identical to $(S_1, S_0)$.

Note that the protocol transcript contains $(I_0, I_1)$ which would be equal to $(S_b, S_{1-b})$ for an honest receiver strategy (and hence also for $\simu$ strategy until $\Hyb_5$). However, for the $\simu$ strategy in $\Hyb_6$, $(I_0, I_1)$ is always equal to $(S_0, S_1)$. Hence, if $b = 0$, the distribution of $(I_0, I_1)$ in $\Hyb_5$ would be identical to $\Hyb_6$. On the other hand, if $b = 1$, the distribution of $(I_0, I_1)$ in $\Hyb_5$ would be perfectly indistinguishable from $\Hyb_6$ (following from the fact that the distribution of $(S_0, S_1) = (S_1, S_0)$). Putting together these two observations, it easily follows that $\Hyb_5 = \Hyb_6$.

§.§ Four-round chosen-input OT

In this section, we prove <ref>.

Sender Security
The proof of this follows along a similar line as the proof of security against a malicious receiver for the 3-round protocol described before. We only describe the changes to the corresponding proof from before over here.

The only change to the simulator (compared to $\Sim[\rcv^*]$ for the 3-round protocol described earlier) is that after computing $b$ at the end of third round, it sends $b$ to $\cF_{\OT[\secp]}$ to receive back $m_b$, sets $m_{1-b} \coloneqq 0^\secp$, and thereafter completes the protocol as in the honest sender strategy. Once it outputs $\rcv^*$'s state, it continues answering distinguisher's queries using $\SimExt.\RO$.

The hybrids ($\Hyb_0,\Hyb_1,\Hyb_2$) also remain same as in the proof before, and the indistinguishability between $\Hyb_0,\Hyb_1$ proceeds as before. The indistiguishability between $\Hyb_1,\Hyb_2$ follows using a slightly modified analysis of <ref> and <ref>. Specifically, for the proof of <ref>, we use $\delta = 0.04, \beta = 0.023, \eta = 0.0236, A = 5300, B = 5000$, and obtain the same result of $\epsilon_{\mathsf{quantum}}^\delta \leq \frac{\sqrt{5}}{2^\secp}$.

For the proof of <ref>, we use a different analysis as follows: set $\epsilon = 0.017$. By assumption of the subclaim and using a similar analysis as the proof of <ref>, the state on $\cX$ is in a superposition of states $\ket{\bx_{\btheta^*}}$ s.t. $\Delta(\bx_{S},\bx^*_S)=0$ and  $\Delta(\bx_{\overline{T}},\bx^*_{\overline{T}}) < \delta$. Using Hoeffding's inequality, the number of positions $i \in \overline{T}$ s.t. $\widehat{\theta}_i \neq \theta_i^*$ is at least $\frac{(1-\epsilon)(n-k)}{2}$ except with probability $\exp\left(-\frac{\epsilon^2(n-k)}{2}\right)$. For $\epsilon=0.053, n-k=B\secp, B = 5000$, this probability is $<\frac{1}{2^\secp}$. Next, as before,  given any partition $(I_0,I_1)$ of $\overline{T}$ that $\rcv^*$ sends in the third round, it holds that there exists a bit $b$ and partition $I_{1-b}$ s.t. there are at least $\frac{(1-\epsilon)(n-k)}{4}$ positions $i$ with $\widehat{\theta}_i \neq \theta_i^*$.

Hence, $\cX_{I_{1-b}}$ is in a superposition of states $\ket{\bx_{\left(\btheta^*_{I_{1-b}}\right)}}$ s.t. $\Delta(\bx,\bx^*_{I_{1-b}}) < \delta$ and at least $\frac{(1-\epsilon)(n-k)}{4}$ positions of it are measured in basis $\widehat{\theta}_i \neq \theta_i^*$. Let $\widehat{X}_{1-b}$ be the string obtained by concatenating the measurement outcomes of $I_{1-b}$. Also, let $\cC$ denote the register for the complete system (including the private state of $\rcv^*$), but excluding register $\cX$. Using <ref>, we get,

\begin{align*}
\mathbf{H}_\infty(\widehat{X}_{1-b} \, | \, \cX_{I_b}, \cC) &\geq \frac{(1-\epsilon)(n-k)}{4} - h_b(\delta)|I_{1-b}|\\
&\geq \frac{(1-\epsilon)(n-k)}{4} - h_b(\delta)(n-k)
\end{align*}

For $\epsilon = 0.017, \delta = 0.04, n-k = B\secp, B = 5000$, we get, $\mathbf{H}_\infty(\widehat{X}_{1-b} \, | \, \cX_{I_b}, \cC)\geq 17\secp$, and also, that $\mathbf{H}_\infty(\widehat{X}_{1-b} \, | \, \widehat{X}_{I_b}, \cC)\geq 17\secp$. Using <ref>, we then get that $(s,h(s,\widehat{X}_{I_{1-b}}))$ is $\frac{1}{2^{9\secp}}$ statistically close to uniformly random string.
Hence, $|\Pr[\Hyb_1=1]-\Pr[\Hyb_2=1]|\leq \frac{\sqrt{5}}{2^{\secp}}+ \frac{1}{2^{9\secp}}$.

Receiver Security The proof of this is similar to the proof of receiver security for the 3 round random basis protocol described before. We only describe the changes here. The only change to the simulator is the following: Instead of executing Steps 8-10, it computes $\widetilde{X_0}, \widetilde{X_1}$ as the concatenation of $\{\widetilde{x_i}\}_{i \in I_0}, \{\widetilde{x_i}\}_{i \in I_1}$ respectively. It sends $I_0, I_1, \{(x_i, \theta_i), u_i\}_{i \in T}$ to $\sS$. On receiving $s, ct_0, ct_1$ from $\sS$ in Round 4, it extracts $m_0 := ct_0 \oplus h(s, \widetilde{X_0})$, $m_1 := ct_1 \oplus h(s, \widetilde{X_1})$, and sends $m_0, m_1$ to $\cF_\OT$.

The hybrids $\Hyb_0, \Hyb_1, \Hyb_2, \Hyb_3$ remain same as before. In $\Hyb_4$, instead of setting $r_b$, the challenger just outputs $m_b := ct_b \oplus h(s, \{\widetilde{x_i}\}_{i \in I_b})$ after Round 4. In $\Hyb_5$, instead of setting $r_0, r_1$, the challenger extracts $m_0 := ct_0 \oplus h(s, \{x_i\}_{i \in I_0})$, $m_1 := ct_1 \oplus h(s, \{x_i\}_{i \in I_1})$ after Round 4, and sends $m_0, m_1$ to $\cF_\OT$. The proof of indistinguishability between each pair of hybrids is similar to the prior proof.

The only security loss in the proof is between $\Hyb_0$ and $\Hyb_1$ (when we invoke the equivocality of the underlying commitment scheme).  Using Theorem <ref> where we derived  $\mu(\secp,q, n_\com) = \frac{2qn_{\com}^{1/2}}{2^{\secp_\com/2}}$ and plugging $\lambda_\com = 2 \secp$, $n_\com = 2n$ (as we are committing to 2 bits at a time) where $n = 10\ 300\secp$ (this setting of $n$ is the same as that needed in the sender security part of the proof), we get $\frac{288q\sqrt{\secp}}{2^{\secp}}$ security against a malicious sender.

§ PRELIMINARIES

We use $[n]$ to denote the set $\{1,2, \ldots n\}$ and $[a,b]$ (where $a<b$) to denote the set $\{a, a+1, \ldots b\}$. We use $\cH\cW(x)$ to denote the Hamming weight of a binary string $x \in \{0,1\}^*$, and $\omega(x)$ to denote its relative Hamming weight $\cH\cW(x) / |x|$. For two strings $x,y \in \zo^*$, we use $\Delta(x,y)=\omega(x \oplus y)$ to denote the relative Hamming distance of $x,y$. For finite sets $X,Y$, let $F_{X \to Y}$ be the set of functions with domain $X$ and codomain $Y$. For a set $T \subseteq [n]$, $\{i\}_{i \in T}$ is used to represent a set indexed by $T$.

Let $h_b(x)$ denote the binary entropy function, $h_b(x) = -x\log_2(x)-(1-x)\log_2(1-x)$. We make use of the well-known fact that the number of strings of length $n$ with relative Hamming weight at most $\delta$ is $\leq 2^{h_b(\delta)n}$.

§.§ Oblivious Transfer with Quantum Communication

The definition below is copy pasted from the OWF=> QOT paper

An oblivious transfer with quantum communication is a protocol between a quantum interactive sender $\cS$ and a quantum interactive receiver $\cR$, where the sender $\cS$ has input $m_0,m_1 \in \{0,1\}^\secp$ and the receiver $\cR$ has input $b \in \{0,1\}$. After interaction the sender outputs $(m_0,m_1)$ and the receiver outputs $(b,m_b)$.

Let $\cF(\cdot,\cdot)$ be the following functionality. $\cF(b,\cdot)$ takes as input either $(m_0,m_1)$ or $\abort$ from the sender, returns $\mathsf{end}$ to the sender, and outputs $m_b$ to the receiver in the non-$\abort$ case and $\bot$ in the $\abort$ case. $\cF(\cdot,(m_0,m_1))$ takes as input either $b$ or $\abort$ from the receiver,
returns $m_b$ to the receiver, and
returns $\mathsf{end}$ to the sender
in the non-$\abort$ case, and returns $\bot$ to the sender  in the $\abort$ case.

We let $\langle S(m_0, m_1), R(b) \rangle$ denote an execution of the OT protocol with sender input $(m_0, m_1)$ and receiver input bit $b$.
We denote by $\brho_{\out,S^*}\langle S^*(\brho), R (b) \rangle$ and $\mathsf{OUT}_{R}\langle S^*(\brho), R(b) \rangle$ the final state of a non-uniform malicious sender $S^*(\brho)$ and the output of the receiver $R(b)$ at the end of an interaction (leaving the indexing by $\secp$ implicit). We denote by $\brho_{\out,R^*}\langle S(m_0, m_1), R^*(\brho) \rangle$ and $\mathsf{OUT}_{S}\langle  S(m_0, m_1), R^*(\brho) \rangle$ the final state of a non-uniform malicious receiver $R^*(\brho)$ and the output of the sender $S(m_0,m_1)$ at the end of an interaction.
We require OT to satisfy the following security properties:

* Receiver Security.
For every receiver bit $b \in \zo$, every QPT non-uniform malicious sender $S^*(\brho)$, and QPT non-uniform distinguisher $D^*(\bsigma,\cdot)$, where $\brho$ and $\bsigma$ may be entangled, there exists a simulator $\simu_{S^*}$ such that the following holds.
$\simu_{S^*}(\brho)$ sends inputs $(m_0, m_1)$ or $\mathsf{abort}$ to the ideal functionality ${\fot(b,\cdot)}$, whose output to the receiver is denoted by $\mathsf{OUT}_R$. $\simu_{S^*}(\brho)$ also outputs a final state $\brho_{\mathsf{Sim},\out,S^*}$ such that

\begin{align*}
\bigg|&\Pr\left[D^*\left(\bsigma,\left(\brho_{\mathsf{Sim},\out,S^*}, \mathsf{OUT}_{R} \right)\right) = 1\right]\\
&-\Pr\left[D^*\left(\bsigma,\left(\brho_{\out,S^*}\langle S^*(\brho), R(b) \rangle, \mathsf{OUT}_{R}\langle S^*(\brho), R(b) \rangle\right) \right) = 1\right]\bigg| = \negl(\secp).
\end{align*}

* Sender Security. For every pair of sender inputs $(m_0, m_1)$, every QPT non-uniform malicious receiver $R^*(\brho)$, and QPT non-uniform distinguisher $D^*(\bsigma,\cdot)$, where $\brho$ and $\bsigma$ may be entangled, there exists a  simulator $\simu_{R^*}$ such that the following holds. $\simu_{R^*}(\brho)$ sends bit $b$ or $\mathsf{abort}$ to the ideal functionality ${\fot(m_0,m_1,\cdot)}$, whose output to the sender is denoted by $\mathsf{OUT}_S$. $\simu_{R^*}(\brho)$ also outputs a final state $\brho_{\mathsf{Sim},\out,R^*}$ such that

\begin{align*}
\bigg|&\Pr\left[D^*\left(\bsigma,\left(\brho_{\mathsf{Sim},\out,R^*}, \mathsf{OUT}_S \right)\right) = 1\right]\\
&-\Pr\left[D^*\left(\bsigma,\left(\brho_{\out,R^*}\langle S(m_0,m_1), R^*(\brho) \rangle, \mathsf{OUT}_S\langle S(m_0,m_1), R^*(\brho) \rangle\right) \right) = 1\right]\bigg| = \negl(\secp).
\end{align*}

§.§ Quantum preliminaries

A register $\cX$ is a named Hilbert space $\bbC^{2^n}$. A pure quantum state on register $\cX$ is a unit vector $\ket{\psi}_\cX \in \bbC^{2^n}$, and we say that $\ket{\psi}_\cX$ consists of $n$ qubits. A mixed state on register $\cX$ is described by a density matrix $\rho_\cX \in \bbC^{2^n \times 2^n}$, which is a positive semi-definite Hermitian operator with trace 1.

A quantum operation $F$ is a completely-positive trace-preserving (CPTP) map from a register $\cX$ to a register $\cY$, which in general may have different dimensions. That is, on input a density matrix $\rho_\cX$, the operation $F$ produces $F(\rho_\cX) = \tau_\cY$ a mixed state on register $\cY$. A unitary $U: \cX \to \cX$ is a special case of a quantum operation that satisfies $U^\dagger U = U U^\dagger = \bbI_\cX$, where $\bbI_\cX$ is the identity matrix on register $\cX$. A projector $\Pi$ is a Hermitian operator such that $\Pi^2 = \Pi$, and a projective measurement is a collection of projectors $\{\Pi_i\}_i$ such that $\sum_i \Pi_i = \bbI$.

Let $\ptrace$ denote the trace operator. For registers $\cX,\cY$, the partial trace $\ptrace_\cY$ is the unique operation from $\cX,\cY$ to $\cX$ such that for all $\rho_\cX,\tau_\cY$, $\ptrace_{\cY}(\rho,\tau) = \ptrace(\tau)\rho$. The trace distance between states $\rho,\tau$, denoted $\TD(\rho,\tau)$ is defined as
\[\TD(\rho,\tau) \coloneqq \frac{1}{2}\|\rho-\tau\|_1 \coloneqq \frac{1}{2}\ptrace\left(\sqrt{(\rho-\tau)^\dagger(\rho-\tau)}\right).\]
We will often use the fact that the trace distance between two states $\rho$ and $\tau$ is an upper bound on the probability that any algorithm can distinguish $\rho$ and $\tau$.

Let $\rho_\cX$ be a quantum state and let $(\Pi,\bbI-\Pi)$ be a projective measurement on $\cX$ such that $\Tr(\Pi\rho) \geq 1-\delta$. Let
\[\rho' = \frac{\Pi\rho\Pi}{\Tr(\Pi\rho)}\]
be the state after applying $(\Pi,\bbI-\Pi)$ to $\rho$ and post-selecting on obtaining the first outcome. Then, $\TD(\rho,\rho') \leq 2\sqrt{\delta}$.

Finally, we will make use of the convention that $+$ denotes the computational basis $\{\ket{0},\ket{1}\}$ and $\times$ denotes the Hadamard basis $\left\{\frac{\ket{0} + \ket{1}}{\sqrt{2}}, \frac{\ket{0} - \ket{1}}{\sqrt{2}}\right\}$. For a bit $r \in \{0,1\}$, we write $\ket{r}_+$ to denote $r$ encoded in the computational basis, and $\ket{r}_\times$ to denote $r$ encoded in the Hadamard basis.

§.§ Quantum machines and protocols

todo: add support for parallel queries

Quantum interactive machines. A quantum interactive machine (QIM) is a family of machines $\{M_\secp\}_{\secp \in \bbN}$, where each $M_{\secp}$ consists of a sequence of quantum operations $M_{\secp,1},\dots,M_{\secp,\ell(\secp)}$, where $\ell(\secp)$ is the number of rounds in which $M_\secp$ operates. Usually, we drop the indexing by $\secp$ and refer to the machine $M = M_1,\dots,M_\ell$. Each machine $M_i$ may have a designated input and output register used to communicate with its environment.

Quantum oracle machines. Let $X,Y$ be finite sets and let $O : X \to Y$ be an arbitrary function. We say that $A^{O}$ is a $q$-query quantum oracle machine (QOM) if it can be written as $A_{q+1}U_OA_{q}U_O\dots U_OA_2U_OA_1$, where $A_1,\dots,A_{q+1}$ are arbitrary quantum operations, and $U[O]$ is the unitary defined by
\[U[O]: \ket{x}_\cX\ket{y}_\cY \to \ket{x}_\cX\ket{y \oplus O(x)}_\cY,\]
operating on a designated oracle input register $\cX$ and oracle output register $\cY$. We say that $A$ is a quantum interactive oracle machine (QIOM) if $A = A_1^O,\dots,A_\ell^O$ is such that each $A_i^O$ is a quantum oracle machine.

Sometimes, it will be convenient to consider controlled queries to an oracle $O$, which would be implemented by a unitary
\[U_c[O] : \ket{b}_\cB\ket{x}_\cX\ket{y}_\cY \to \ket{b}_\cB\ket{x}_\cX\ket{y \oplus b \cdot O(x)}_\cY.\]

However, it is easy to see that such a controlled query can be implemented with two standard queries, by introducing an extra register $\cZ$, as follows:

\begin{align*}
\ket{b}_\cB\ket{x}_{\cX}\ket{y}_\cY\ket{0}_\cZ
&\xrightarrow{U[O_0]_{\cX,\cZ}} \ket{b}_\cB\ket{x}_{\cX}\ket{y}_\cY\ket{O(x)}_\cZ \to \ket{b}_\cB\ket{x}_{\cX}\ket{y \oplus b \cdot O(x)}_\cY\ket{O(x)}_\cZ\\  &\xrightarrow{U[O_0]_{\cX,\cZ}} \ket{b}_\cB\ket{x}_{\cX}\ket{y \oplus b \cdot O(x)}_\cY\ket{0}_\cZ.
\end{align*}

It will also be convenient to consider algorithms $A^{O_0,O_1}$ with access to multiple oracles $O_0: X_0 \to Y_0, O_1: X_1 \to Y_1$, written as $A_{q+1}U_{O_1}A_{q}U_{O_0}\dots U_{O_1}A_2U_{O_0}A_1$. Defining $O(b,x) = O_b(x)$ for $(b,x) \in (0,X_0) \union (1,X_1)$, it is easy to see that any $A^{O_0,O_1}$ can be written as an oracle algorithm $B^O$. On the other hand, given a $q$-query oracle algorithm $A^O$ where $O: X \to Y$, and a partition of $X$ into $(0,X') \cup (1,X')$, we can write $A$ as a $4q$-query algorithm $B^{O_0,O_1}$, where $O_b : X' \to Y$ is such that $O_b(x') = O(b,x')$. This follows by answering each query to $O$ using one controlled query to $O_0$ and one controlled query to $O_1$. This can be extended to splitting up an oracle $O$ into $k$ oracles, with a multiplicative factor of $2k$ in the number of queries made by the adversary. Thus, throughout this work, we often consider machines that have access to multiple (potentially independently sampled) oracles, while noting that this model is equivalent to considering machines with access to a single oracle, up to a difference in the number of oracle queries. In particular, any adversarial algorithm that has superposition access to a single oracle $O$ with an input space that can be partitioned into $k$ parts may be written as an adversarial algorithm wth access to $k$ appropriately defined separate oracles $O_1,\dots,O_k$.

Functionalities and protocols in the quantum random oracle model.
Let $\cF$ denote a functionality, which is a classical interactive machine specifying the instructions to realize a cryptographic task. A two-party protocol[One can also consider multi-party protocols, but we restrict to the two-party setting in this work.] $\Pi$ for $\cF$ consists of two QIMs $(A,B)$.[Technically, $A$ and $B$ are infinite families of interactive machines, parameterized by the security parameter $\secp$.] A protocol $\Pi$ in the quantum random oracle model (QROM) consists of two QIOMs $(A^H,B^H)$ that have quantum oracle access to a uniformly random function $H$ sampled from $F_{X \to Y}$ for some finite sets $X$ and $Y$.

An adversary intending to attack the protocol along with a distinguisher can be described by a family $\{\Adv_\secp,\sD_\secp,x_\secp\}_{\secp \in \bbN}$, where $\Adv_\secp$ is a QIOM that corrupts party $M \in \{A,B\}$, $\sD_\secp$ is a QOM, and $x_\secp$ is the input of the honest party $P \in \{A,B\}$. Define the one-bit random variable $\Pi[\Adv_\secp,\sD_\secp,x_\secp]$ as follows.

* $H$ is sampled uniformly at random.

* $\Adv_\secp^H$ interacts with $P^H(x_\secp)$ during the execution of $\Pi$, and $\Adv_\secp$ outputs a quantum state $\rho$, while $P^H$ outputs a classical string $y$.

* $\sD_\secp^H(\rho, y)$ outputs a bit $b$.

An ideal-world protocol $\widetilde{\Pi}_\cF$ for functionality $\cF$ consists of two “dummy” parties $\widetilde{A},\widetilde{B}$ that have access to an additional “trusted” party that implements $\cF$. That is, $\widetilde{A},\widetilde{B}$ each interact directly with $\cF$, which eventually returns outputs to $\widetilde{A},\widetilde{B}$. We consider the execution of ideal-world protocols in the presence of a simulator followed by a distinguisher, described by a family $\{\Sim_\secp,\sD_\secp,x_\secp\}_{\secp \in \bbN}$. Define the random variable $\widetilde{\Pi}_\cF[\Sim_\secp,\sD_\secp,x_\secp]$ over one bit output a follows.

* $\Sim_\secp$ interacts with $\widetilde{P}(x_\secp)$ during the execution of $\widetilde{\Pi}_\cF$, and $\Sim_\secp$ outputs a quantum state $\rho$, while $\widetilde{P}$ outputs a classical string $y$.

* $\sD_\secp^{\Sim_\secp}(\rho, y)$ outputs a bit $b$.

In the above, $\Sim_\secp$ may be stateful, meaning that the part of $\Sim_\secp$ that interacts with $\widetilde{P}(x)$ may pass an arbitrary state to the part of $\Sim_\secp$ that answers $\sD_\secp's$ oracle queries.

Furthermore, we will only consider the notion of security with abort where every ideal functionality is slightly modified to (1) know the identities of corrupted parties and (2) be slightly reactive: after all parties have provided input, the functionality computes outputs and delivers the outputs to the corrupt parties only. Then the functionality awaits either a “deliver” or “abort” command from the corrupted parties. Upon receiving “deliver”, the functionality delivers the outputs to all the honest parties. Upon receiving “abort”, the functionality delivers an abort output ($\bot$) to all the honest parties.

removed the $(\cdot,\cdot)$ notation from below. Also, i think we can strengthen this definition by saying that there exists a simulator, polynomial s which works for all adv making q queries. Esp since now we don't have the query bound needed for simulation on adversaries? And making the defn similar to what is there for commitments currently

A protocol $\Pi$ $\mu$-securely realizes a functionality $\cF$ with abort in the quantum random oracle model if there exists a polynomial $s$ such that for any function $q$ and any $\{\Adv_\secp\}_{\secp \in \bbN}$, there exists a simulator $\{\Sim_\secp\}_{\secp \in \bbN}$ such that the run-time of $\Sim_\secp$ is at most the run-time of $\Adv_\secp$ plus $s(\secp,q(\secp))$, and for all $\{\sD_\secp,x_\secp\}_{\secp \in \bbN}$ with the property that the combined number of oracle queries made by $\Adv_\secp$ and $\sD_\secp$ is at most $q(\secp)$, it holds that
\[\bigg|\Pr[\Pi[\Adv_\secp,\sD_\secp,x_\secp] = 1] - \Pr[\widetilde{\Pi}_\cF[\Sim_\secp,\sD_\secp,x_\secp] = 1]\bigg| = \mu(\secp,q(\secp)).\]

Furthermore, we say that a protocol $\Pi$ securely realizes a functionality $\cF$ if it $\mu$-securely realizes $\cF$ where $\mu$ is such that for any $q(\secp) = \poly(\secp)$, $\mu(\secp,q(\secp)) = \negl(\secp)$.

§.§ Oblivious transfer functionalities
We will consider various oblivious transfer functionalities in this work. Some of these will be used as stepping stones towards other constructions.

* $\cF_{\OT[k]}$: the chosen-input string OT functionality takes as input a bit $b$ from the receiver and two strings $m_0,m_1 \in \{0,1\}^k$ from the sender. It delivers $m_b$ to the receiver.

* $\cF_{\RROT[1]}$: the random-receiver-input bit OT functionality takes as input $\top$ from the receiver and two bits $m_0,m_1 \in \{0,1\}$ from the sender. It samples $b \gets \{0,1\}$ and delivers $(b,m_b)$ to the receiver.

* $\cF_{\SROT[k]}$: the random-sender-input (string) OT functionality takes as input $\top$ from the sender and $(b,m)$ from the receiver for $b \in \{0,1\}, m \in \{0,1\}^k$. It set $m_b = m$, samples $m_{1-b} \gets \{0,1\}^k$ and delivers  $(m_0,m_1)$ to the sender.

* $\cF_{\EndRROT}$: the random-receiver-input bit OT with endemic security <cit.> OT functionality takes as input $\top$ or $b$ from the receiver and two bits $m_0,m_1 \in \{0,1\}$ from the sender.

* Correctness. Obtain $\top$ from an honest receiver and $(m_0,m_1)$ from the sender, sample $b \gets \{0,1\}$ and deliver $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* Endemic Security against a Malicious Receiver. Obtain $b$ from a malicious receiver and $(m_0,m_1)$ from the sender, deliver $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* $\cF_{\OT[k]}(\cdot,\cdot)$: the chosen-input OT functionality takes as input a bit $b$ from the receiver and two strings $m_0,m_1 \in \{0,1\}^k$ from the sender.

* In the case of $b$ from the receiver and $(m_0,m_1)$ from the sender, it delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* $\cF_{\SROT[k]}(\cdot,\cdot)$: the random-sender-input OT functionality takes as input $(b,\top)$ or $(b,m_b)$ from the receiver and $\top$ from the sender.

* In the case of $(b,\top)$ from the receiver and $\top$ from the sender, it samples $m_0,m_1 \gets \{0,1\}^k$ and delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* In the case of $(b,m_b)$ from the receiver and $\top$ from the sender, it samples $m_{1-b} \gets \{0,1\}^k$ and delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* $\cF_{\EndSROT[k]}(\cdot,\cdot)$: the random-sender-input with endemic security OT functionality takes as input $(b,\top)$ or $(b,m_b)$ from the receiver and $\top$ or $(m_0,m_1 \in \{0,1\}^k)$ from the sender.

* In the case of $(b,\top)$ from the receiver and $\top$ from the sender, it samples $m_0,m_1 \gets \{0,1\}^k$ and delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* In the case of $(b,m_b)$ from the receiver and $\top$ from the sender, it samples $m_{1-b} \gets \{0,1\}^k$ and delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* In the case of $(b,\top)$ from the receiver and $(m_0,m_1)$ from the sender, it delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* $\cF_{\RROT[k]}(\cdot,\cdot)$: the random-receiver-input OT functionality takes as input $\top$ from the receiver and two strings $m_0,m_1 \in \{0,1\}^k$ from the sender.

* In the case of $\top$ from the receiver and $(m_0,m_1)$ from the sender, it samples $b \gets \{0,1\}$ and delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* $\cF_{\EndRROT[k]}(\cdot,\cdot)$: the random-receiver-input with endemic security OT functionality takes as input $\top$ or $b$ from the receiver and two strings $m_0,m_1 \in \{0,1\}^k$ from the sender.

* In the case of $\top$ from the receiver and $(m_0,m_1)$ from the sender, it samples $b \gets \{0,1\}$ and delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

* In the case of $b$ from the receiver and $(m_0,m_1)$ from the sender, it delivers $(b,m_b)$ to the receiver and $(m_0,m_1)$ to the sender.

We will often refer to the following bit OT reversal theorem.

Any protocol that securely realizes the functionality $\cF_{\SROT[1]}$ can be converted into a protocol that securely realizes the functionality $\cF_{\RROT[1]}$, without adding any messages.

For concreteness, we specify how the OT reversal works. Suppose that Alice and Bob have access to an ideal OT functionality $\cF_{\SROT[1]}$ where Alice is the receiver and Bob is the sender. Their goal is to realize $\cF_{\RROT[1]}$ with roles reversed, i.e. with Alice as sender and Bob as receiver. This is achieved as follows.

* Alice has input $m_0,m_1 \in \{0,1\}$, and samples  $c \gets \{0,1\}, r \gets \{0,1\}$.

* Alice and Bob run the protocol for $\cF_{\SROT[1]}$ where Alice inputs $(c,r)$ as receiver to $\cF_{\SROT[1]}$, and Alice sends
\[\ell_0 \coloneqq m_0 \oplus r, \ell_1 \coloneqq m_1 \oplus r \oplus c\]
along with her OT message to Bob.

* Bob obtains output $(r_0,r_1)$ from the protocol for $\cF_{\SROT[1]}$. Then, he sets
\[b \coloneqq r_0 \oplus r_1, m_b \coloneqq \ell_b \oplus r_0,\]
and outputs $(b,m_b)$.

Bit Oblivious Transfer Reversal.
should probably go elsewhere
We will often reference the following standard non-interactive OT reversal technique from <cit.>. Here, two players Alice and Bob have access to an ideal OT functionality $\cF_{\SROT[1]}(\cdot,\cdot)$ where Alice is the receiver and Bob is the sender. Their goal is to realize $\cF_{\SROT[1]}(\cdot,\cdot)$ Ideally we want chosen, this may need to change with roles reversed, i.e. with Alice as sender and Bob as receiver. This is achieved as follows.

* Alice obtains $(b,m)$ and Bob obtains $(m_0, m_1)$ from $\cF_{\SROT[1]}(\cdot,\cdot)$.

* Alice computes and outputs $\ell_0 = m, \ell_1 = b \oplus m$.

* Bob computes and outputs $c = m_0 \oplus m_1, \ell = m_0$.

Correctness. It is easy to see that when $m = m_b$ (which would follow by correctness of the ideal OT functionality $\cF_{\SROT[1]}(\cdot,\cdot)$ where Alice is the receiver and Bob is the sender), $\ell = \ell_b$

Sender Security. should probably fill this out depending on what type of security our underlying OT has.

todo Given $(b,m_b)$, define $\ell_0 = m_b, \ell_1 = m_b \oplus b$, and given $(m_0,m_1)$, define $c = m_0 \oplus m_1, \ell_c = m_0$.

Privacy against specious adversaries.

We will also consider a weaker notion of security, called privacy against specious adversaries. Specious adversaries can be seen as a quantum analogue of classical semi-honest adversaries. In this section, we leave the indexing by $\secp$ implicit when discussing QIOMs, protocols, etc.

In order to define specious adversaries, we introduce more notation to describe the evolving state of a protocol $\Pi$ between two QIOMs $A^H$ and $B^H$. For the purpose of this work, we restrict attention to protocols $\Pi$ that compute a functionality $\cF$ with classical inputs and outputs. We define $\brho(\Pi,i,x,y)$ to be the joint state of the protocol $\Pi$ executed between $A^H(x)$ and $B^H(y)$ after $i$ rounds. That is,

\[\brho(\Pi,i,x,y) \coloneqq (A_{(i+1)/2}^H \otimes \bbI^{\gray{B}_{(i-1)/2}}) \dots (B_1^H \otimes \bbI^{\gray{A_1}})(A_1^H \otimes \bbI^{\gray{B_0}})(\ket{x}\bra{x}^{\gray{A_0}} \otimes \ket{y}\bra{y}^{\gray{B_0}})\]

for odd $i$, and

\[\brho(\Pi,i,x,y) \coloneqq (B_{i/2}^H \otimes \bbI^{\gray{A_{i/2}}}) \dots (B_1^H \otimes \bbI^{\gray{A_1}})(A_1^H \otimes \bbI^{\gray{B_0}})(\ket{x}\bra{x}^{\gray{A_0}} \otimes \ket{y}\bra{y}^{\gray{B_0}})\]

for even $i$.

An adversary $\widetilde{A}$ corrupting party $A$ consists of memory registers  $\gray{\widetilde{A}_1},\dots,\gray{\widetilde{A}_\ell}$, an $\ell$-tuple of quantum oracle machines $(\widetilde{A}_1^H,\dots,\widetilde{A}_\ell^H)$ where $\widetilde{A}_1^H: \gray{A_0} \to \gray{\widetilde{A}_1} \otimes \gray{X_1}$ and $\widetilde{A}_i^H: \gray{\widetilde{A}_{i-1}} \otimes \gray{Y_{i-1}} \to \gray{\widetilde{A}_i} \otimes \gray{X_i}$ for $2 \leq i \leq \ell$, and an initial state $\brho$ on register $\gray{\widetilde{A}_0}$. The global state after the $i$th step of the protocol is denoted $\brho_{\widetilde{A}}(\Pi,i,x,y)$.

Let $\Pi$ be a $(2\ell-1)$-round protocol in the QROM consisting of QIOMs $A^H$ and $B^H$. An adversary $\widetilde{A}$ corrupting $A$ is called specious if there exists a sequence of recovery operations $F_1^H,\dots,F_\ell^H$ such that

* $F_i^H: \gray{\widetilde{A}_i} \to \gray{A_i}$ for $i \in [\ell]$, and

* for all inputs $(x,y)$ and all $i \in [\ell]$,

\[\TD\left((F_i^H \otimes \bbI^{\gray{X_i},\gray{B_{i-1}}})\left(\brho_{\widetilde{A}}(\Pi,2i-1,x,y)\right),\brho(\Pi,2i-1,x,y)\right) = \negl(\secp).\]

Privacy against specious adversaries is defined to mean that there exists a simulator that, having access only to the adversary's input and the ideal functionality $\cF$, can (approximately) produce the state of the adversary at any step of the protocol. Such a simulator is represented by quantum oracle machines $\cS_1^H,\dots,\cS_\ell^H$, where each may query the ideal functionality $\cF$ at most once.

A protocol $\Pi$ is private against specious adversaries corrupting party $A$ with query-bounded simulation if for any specious $\widetilde{A}$ and $q \in \bbN$, there exists a simulator $S_2^H,\dots,S_\ell^H$, such that for all inputs $(x,y)$, $i \in [2,\dots,\ell]$,[Note that such a simulator exists for $i = 1$ by definition.] and QOM $\cD$ that makes as most $q$ oracle queries,

\[\bigg|\Pr\left[\cD^H\left(\ptrace_{\gray{X_i},\gray{B_{i-1}}}\brho_{\widetilde{A}}(\Pi,2i-1,x,y)\right) = 1\right] - \Pr\left[\cD^{S_i^H}\left(\cS_i(x)^{H,\cF[y]}\right)\right]\bigg| = \negl(\secp),\]
where $\cF[y]$ indicates (one-time) oracle access to the ideal functionality $\cF$ with party $B$'s input $y$ hard-coded.

§.§ Quantum oracle results

We state here some results on quantum oracle machine from prior literature, which we use in our proofs.

[One-way to hiding <cit.>]

Let $X,Y$ be finite non-empty sets and let $(S,O_1,O_2,\ket{\psi})$ be sampled from an arbitrary distribution such that $S \subseteq X$, $O_1,O_2: X \rightarrow Y$ are such that $\forall x \not \in S, O_1(x) = O_2(x)$, and $\ket{\psi}$ is a quantum state on an arbitrary number of qubits. Let $A^{O}(\ket{\psi})$ be a quantum oracle algorithm that makes at most $q$ queries. Let $B^{O}(\ket{\psi})$ be an oracle algorithm that does the following: pick $i \leftarrow [q]$, run $A^{O}(\ket{\psi})$ until (just before) the $i^{th}$ query, measure the query input register in the computational basis, and output the measurement outcome $x$. Let

* $P_{\text{left}} = \Pr[A^{O_1}(\ket{\psi})=1]$,

* $P_{\text{right}} = \Pr[A^{O_2}(\ket{\psi})=1]$,

* and $P_{\text{guess}} = \Pr[x \in S : x \leftarrow B^{O_1}(\ket{\psi})]$.

Then it holds that
\[|P_{\text{left}} - P_{\text{right}}| \leq 2q \sqrt{P_{\text{guess}}}.\]

The above theorem is actually a generalization of the theorem stated in <cit.>, in which the input $\ket{\psi}$ is assumed to be a classical bit string $z$. However, the proof given in <cit.> readily extends to considering quantum input. The proof is split up into <cit.> and <cit.>. In Lemma 8, $(S,O_1,O_2,z)$ are fixed, and $z$ is used to define $A$'s initial state $\ket{\Psi_0}$. Here, we can just define $A$'s initial state as $\ket{\psi}$.

In Lemma 9, an expectation is taken over $(S,O_1,O_2,z)$, and the same expectation can be taken over $(S,O_1,O_2,\ket{\psi})$.

[Random vs. injective functions <cit.>]

Let $X$ and $Y$ be finite non-empty sets, and let $H: X \to Y$ be a uniformly random function. Then for any quantum oracle algorithm $A$ making at most $q$ oracle queries,

\[\Pr[H(x_1) = H(x_2) : (x_1,x_2) \gets A^H] = O(q^3/|Y|).\]

Moreover, if $|X| \leq |Y|$, then for any quantum oracle algorithm $\cA$ making at most $q$ oracle queries,

\[|\Pr[A^H = 1] - \Pr[A^G = 1]| = O(q^3/|Y|),\]

where $G: X \to Y$ is a uniformly random injective function.

[Efficient simulation of random oracle <cit.>]

Let $X$ and $Y$ be finite non-empty sets, and let $H: X \to Y$ be a uniformly random function. Then for any quantum oracle algorithm $A$ making at most $q$ oracle queries,

$$\Pr\left[A^H = 1\right] = \Pr\left[A^F = 1\right],$$

where $F$ is sampled from a family of $2q$-wise independent functions from $X \to Y$.

[Measure-and-reprogram <cit.>][This theorem was stated more generally in <cit.> to consider the drop in expectation for each specific $x^* \in X$. ]
Let $X,Y$ be finite non-empty sets, and let $q \in \bbN$. Let $\Adv$ be a quantum oracle machine with initial state $\rho$ that makes at most $q$ queries to a uniformly random function $H: X \to Y$ and that outputs an $x \in X$ along with an arbitrary quantum state $\sigma$ on register $\cA$. There exists a quantum interactive machine $\Sim[\Adv]$ such that for any projection
\[\Pi[y] \coloneqq \sum_x \ket{x}\bra{x} \otimes \Pi^{x,y}_\cA,\]
where each $\Pi^{x,y}$ is an arbitrary projection on register $\cA$ that is parameterized by strings $x \in X$ and $y \in Y$, it holds that

\begin{align*}&\E_H\left[\Tr\left(\Pi[H(x)] \left(\ket{x}\bra{x} \otimes \sigma\right)\right) : (x,\sigma) \gets \Adv^H(\rho)\right]\\ &\leq (2q+1)^2\E\left[\Tr\left(\Pi[y]\left(\ket{x}\bra{x} \otimes \sigma\right)\right) : \begin{array}{r} (x,\state) \gets \Sim[\Adv](\rho) \\ y \gets Y \\ \sigma \gets \Sim[\Adv](y,\state) \end{array}\right].\end{align*}

Moreover, $\Sim[\Adv]$ runs $\Adv$ except for the following differences: i) it introduces an intermediate measurement of one of the registers maintained by $\Adv$ to obtain $x$, and ii) it simulates responses to $\Adv$'s oracle queries to $H$.

Finally, we will often make use of an “on-the-fly” method for simulating a quantum random oracle, due to <cit.>. This method of simulation is efficient and does not depend on an a priori upper bound on the number of queries $q$ to be made by the adversary. In fact, as shown by <cit.>, this simulation method may be augmented with an extraction interface that essentially allows to recovers a pre-image $x$ given an image $y = H(x)$.

Below, we define independent queries to an interface to be two consecutive queries that can in principle be performed in either order. More formally, two consecutive queries are independent if they can applied to disjoint registers, meaning that one query may be applied to input and output registers $\cX$ and $\cY$, while the other may be applied to disjoint input and output registers $\cX'$ and $\cY'$.

Furthermore, we say that two quantum operations $E$ and $F$ $\alpha$-almost-commute if for any input state $\rho$, $\TD(E(F(\rho)),F(E(\rho)) \leq \alpha$.
We say that two quantum operations $E$ and $F$ commute if for any input state $\rho$, $\TD(E(F(\rho)),F(E(\rho)) = 0$.

[On-the-fly simulation with extraction <cit.>]

Let $X$ be a finite non-empty set and $Y = \zo^n$. There exists a simulator $\simro$ that consists of an initialization step and an interface $\simro.\RO$ that maintains an internal state. $\simro.\RO$, given registers $\cX$ and $\cY$, applies a quantum operation to these registers and its internal state.[We can also consider applying $\simro.\RO$ to a classical input $x$ and producing classical output $y$, which corresponds to applying the quantum operation on $\ket{x}_\cX\ket{0}_\cY$ and measuring the register $\cY$ to produce the output.] The following properties hold for any oracle algorithm $A$.

* Indistinguishable simulation.
\[ \Pr_{H}[1 \leftarrow A^H] = \Pr[1 \leftarrow A^{\simro.\RO}]. \]

* Efficiency. Suppose that $A$ makes $q$ queries to $\simro.\RO$. Then the total runtime of $\simro$ is $O(q^2)$.

There also exists an interface $\simro.\sE$ that upon input a classical value $y \in \zo^n$, outputs a classical value $\hat{x} \in X \cup \{\emptyset\}$. The following properties hold for any oracle algorithm $A$.

* Correctness of extraction.
Suppose that $A$ makes $q$ queries to $\simro.\RO$ and no queries to $\simro.\sE$, and outputs $\mathbf{x} \in X^\ell$ and $\mathbf{y} \in Y^\ell$. Then,

\[
\Pr\left[ \exists \, i \, : \, (\mathbf{y}_i = \mathbf{\hat{y}}_i) \wedge (\mathbf{x}_i \neq \mathbf{\hat{x}}_i) \Bigg| \begin{array}{r} \mathbf{x},\mathbf{y} \leftarrow A^{\simro.\RO} \\ \mathbf{\hat{y}} \gets \simro.\RO(\mathbf{x}) \\ \mathbf{\hat{x}} \leftarrow \simro.\sE(\mathbf{y})  \end{array}\right] \leq \frac{296(q+\ell+1)^3+2}{2^n}.
\]

* Almost commutativity of $\simro.\RO$ and $\simro.\sE$.  Any two independent queries to $\simro.\sE$ and $\simro.\RO$ $\frac{8\sqrt{2}}{2^{n/2}}$-almost-commute.

* Efficiency.
Suppose that $A$ makes $q_\RO$ queries to $\simro.\RO$ and $q_\sE$ queries to $\simro.\sE$. Then the total runtime of $\simro$ is $O(q_\RO q_\sE + q_\RO^2)$.

§.§ Quantum entropy and leftover hashing

Quantum conditional min-entropy.

Let $\rho_{\cX\cY}$ denote a bipartite quantum state over registers $\cX,\cY$. Following <cit.>, the conditional min-entropy of $\rho_{\cX\cY}$ given $\cY$ is then defined to be

\[\mathbf{H}_\infty(\rho_{\cX\cY} \mid \cY) \coloneqq \sup_\tau \max \{h \in \mathbb{R} : 2^{-h} \cdot \bbI_\cX \otimes \tau_\cY - \rho_{\cX\cY} \geq 0\}.\]

In this work, we will exclusively consider the case where the $\rho_{\cX\cY}$ is a joint distribution of the form $(R,\tau)$ where $R$ is a classical random variable. In other words, $\rho_{\cX\cY}$  can be written as

\[ \sum_x \Pr[X = x] \ket{x}\bra{x} \otimes \tau_x. \]

We refer to such $\rho_{\cX\cY}$ as a classical-quantum state. In this case, quantum conditional min-entropy exactly corresponds to the maximum probability of guessing $x$ given the state on register $\cY$.

Let $\rho_{\cX,\cY}$ be a classical-quantum state, and let $p_{\mathsf{guess}}(\rho_{\cX,\cY} | \cY)$ be the maximum probability that any quantum operation can output the $x$ on register $\cX$, given the state on register $\cY$. Then
\[p_{\mathsf{guess}}(\rho_{\cX,\cY} | \cY) = 2^{-\mathbf{H}_\infty(\rho_{\cX,\cY} | \cY)}.\]

Leftover hash lemma with quantum side information. We now state a generalization of the leftover hash lemma to the setting of quantum side information.
Let $\mathcal{H}$ be a family of universal hash functions from $X$ to $\{0,1\}^\ell$, i.e. for any $x \neq x'$, $\Pr_{h \leftarrow \mathcal{H}}[h(x) = h(x')] = 2^{-\ell}$. Let $\rho_{\cX\cY}$ be any classical-quantum state. Let $\cR$ be a register that holds $h \gets \cH$, let $\cK$ be a register that holds $h(x)$, where $x$ is on register $\cX$, and define $\rho_{\cX\cY\cR\cK}$ to be the entire system. Then, it holds that

\[\left\|\rho_{\cY\cR\cK} -  \rho_{\cY\cR} \otimes \frac{1}{2^\ell}\sum_{u}\ket{u}\bra{u}\right\|_1 \leq \frac{1}{2^{1+\frac{1}{2}(\mathbf{H}_\infty(\rho_{\cX\cY}|\cY)-\ell)}}.\]

Small superposition of terms. We will also make use of the following lemma from <cit.>.

Let $\cX,\cY$ be registers of arbitrary size, and let $\{\ket{i}\}_{i \in I}$ and $\{\ket{w}\}_{w \in W}$ be orthonormal bases of $\cX$. Let $\ket{\psi}_{\cX\cY}$ and $\rho_{\cX\cY}$ be of the form
\[\ket{\psi} = \sum_{i \in J}\alpha_i\ket{i}_\cX\ket{\psi_i}_\cY  \text{   and     } \rho = \sum_{i \in J}|\alpha_i|^2\ket{i}\bra{i}_\cX \otimes \ket{\psi_i}\bra{\psi_i}_\cY\]
for some subset $J \subseteq I$. Furthermore, let $\widehat{\rho}_{\cX\cY}$ and $\widehat{\rho}^{\mathsf{mix}}_{\cX\cY}$ be the classical-quantum states obtained by measuring register $\cX$ of $\ket{\psi}$ and $\rho$, respectively, in basis $\{\ket{w}\}_{w \in W}$ to observe outcome $w$. Then,
\[\mathbf{H}_\infty(\widehat{\rho}_{\cX,\cY} | \cY) \geq \mathbf{H}_\infty(\widehat{\rho}^{\mathsf{mix}}_{\cX,\cY} | \cY) - \log|J|.\]

§.§ Sampling in a quantum population

In this section, we describe a generic framework presented in <cit.> for analyzing cut-and-choose strategies applied to quantum states.

Classical sampling stratiegies. Let $A$ be a set, and let $\bq = (q_1,\dots,q_n) \in A^n$ be a string of length $n$. We consider the problem of estimating the relative Hamming weight of a substring $\omega(\bq_{\overline{t}})$ by only looking at the substring $\bq_t$ of $\bq$, for a subset $t \subset [n]$. We consider sampling strategies $\Psi = (P_T,P_S,f)$, where $P_T$ is an (independently sampled) distribution over subsets $t \subseteq [n]$, $P_S$ is a distribution over seeds $s \in S$, and $f: \{(t,\bv) : t \subset [n], \bv \in A^t\} \times S \to \bbR$ is a function that takes the subset $t$, the substring $\bv$, and a seed $s$, and outputs an estimate for the relative Hamming weight of the remaining string. For a fixed subset $t$, seed $s$, and a parameter $\delta$, define $B^\delta_{t,s}(\Psi) \subseteq A^n$ as
\[B^{\delta}_{t,s} \coloneqq \{\bb \in A^n : |\omega(\bb_{\overline{t}}) - f(t,\bb_t,s)| < \delta\}.\]
Then we define the classical error probability of strategy $\Psi$ as follows.

The classical error probability of a sampling strategy $\Psi = (P_T,P_S,f)$ is defined as the following value, paraterized by $0 < \delta < 1$:
\[\epsilon^\delta_{\mathsf{classical}}(\Psi) \coloneqq \max_{\bq \in A^n}\Pr_{t \gets P_T,s \gets P_S}\left[\bq \notin B_{t,s}^\delta(\Psi)\right].\]

Quantum sampling strategies. Now, let $A = A_1,\dots,A_n$ be an $n$-partite quantum system on registers $\cA = \cA_1 \otimes \dots \otimes \cA_n$, where each system has dimension $d$. Let $\{\ket{a}\}_{a}$ be a fixed orthonormal basis for each $\cA_i$. $\cA$ may be entangled with another system $\cE$, and we write the purified state on $\cA$ and $\cE$ as $\ket{\psi}_{\cA\cE}$. We consider the problem of testing whether the state on $\cA$ is close to the all-zero reference state $\ket{0}_{\cA_1}\dots\ket{0}_{\cA_n}$. There is a natural way to apply any sampling strategy $\Psi = (P_T,P_S,f)$ to this setting: sample $t,s$ according to $P_T,P_S$, measure subsystems $\cA_i$ for $i \in [t]$ in basis $\{\ket{a}\}_a$ to observe $\bq_{t} \in A^{|t|}$, and compute an estimate $f(t,\bq_t,s)$.

In order to analyze the effect of this strategy, we first consider the mixed state on registers $\cT$ (holding the subset $t$), $\cS$ (holding the seed $s$), and $\cA,\cE$ that results from sampling $t$ and $s$ according to $P_{TS} = P_TP_S$

\[\rho_{\cT\cS\cA\cE} = \sum_{t,s}P_{TS}(t,s)\ket{t,s}\bra{t,s} \otimes \ket{\psi}\bra{\psi}.\]
Next, we compare this state to an ideal state, parameterized by $0 < \delta < 1$, of the form

\[\widetilde{\rho}_{\cT\cS\cA\cE} = \sum_{t,s} P_{TS}(t,s)\ket{t,s}\bra{t,s} \otimes \ket{\widetilde{\psi}^{ts}}\bra{\widetilde{\psi}^{ts}} \text{   with    } \ket{\psi^{ts}} \in \mathsf{span}\left(B_{t,s}^\delta\right) \otimes \cE,\]
\[\mathsf{span}\left(B_{t,s}^\delta\right) \coloneqq \mathsf{span}\left(\{\ket{\bb} : \bb \in B_{t,s}^\delta\}\right) = \mathsf{span}\left(\{\ket{\bb}: |\omega(\bb_{\overline{t}}) - f(t,\bb_t,s)| < \delta\}\right).\]
That is, $\widetilde{\rho}_{\cT\cS\cA\cE}$ is a state such that it holds with certainty that the state on registers $\cA_{\overline{t}}\cE$, after having measured $\cA_{t}$ and oberserving $\bq_t$, is in a superposition of states with relative Hamming weight $\delta$-close to $f(t,\bq_t,s)$. This leads us to the definition of the quantum error probability of strategy $\Psi$.

The quantum error probability of a sampling strategy $\Psi = (P_T,P_S,f)$ is defined as the following value, parameterized by $0 < \delta < 1$:
\[\epsilon_{\mathsf{quantum}}^\delta(\Psi) \coloneqq \max_\cE\max_{\ket{\psi}_{\cA\cE}}\min_{\widetilde{\rho}_{\cT\cS\cA\cE}}\TD\left(\rho_{\cT\cS\cA\cE},\widetilde{\rho}_{\cT\cS\cA\cE}\right),\]
where the first max is over all finite-dimensional registers $\cE$, the second max is over all state $\ket{\psi}_{\cA\cE}$ and the min is over all ideal state $\widetilde{\rho}_{\cT\cS\cA\cE}$ of the form described above.

Finally, we relate the classical and quantum error probabilities.

For any sampling strategy $\Psi$ and $\delta > 0$,
\[\epsilon_{\mathsf{quantum}}^\delta(\Psi) \leq \sqrt{\epsilon_{\mathsf{classical}}^\delta(\Psi)}.\]

§ SECURITY OF THE SEEDLESS EXTRACTORS

In this section, we show the security of the XOR and ROM extractors.

§.§ XOR extractor

Let $\cX$ be an $n$-qubit register, and consider any state $\ket{\gamma}_{\cA,\cX}$ that can be written as
\[\ket{\gamma} = \sum_{u: \cH\cW(u) < n/2} \ket{\psi_u}_{\cA} \otimes \ket{u}_\cX.\]
Let $\rho_{\cA,\cP}$ be the mixed state that results from measuring $\cX$ in the Hadamard basis to produce $x$, and writing $\bigoplus_{i \in [n]}x_i$ into the single qubit register $\cP$. Then it holds that
\[\rho_{\cA,\cP} = \Tr_\cX(\ket{\gamma}\bra{\gamma}) \otimes \left(\frac{1}{2}\ket{0}\bra{0} + \frac{1}{2}\ket{1}\bra{1}\right).\]

First, write the state on $(\cA,\cX,\cP)$ that results from applying Hadamard to $\cX$ and writing the parity, denoted by $p(x) \coloneqq \bigoplus_{i \in [n]}x_i$, to $\cP$:

\[\frac{1}{2^{n/2}}\sum_{x \in \{0,1\}^n}\left(\sum_{u:\cH\cW(u) < n/2}(-1)^{u \cdot x}\ket{\psi_u}\right)\ket{x}\ket{p(x)}.\]

Then we have that

\begin{align*}
\rho_{\cA,\cP} &= \frac{1}{2^n}\sum_{x: p(x) = 0} \left(\sum_{u_1,u_2}(-1)^{(u_1 \oplus u_2)\cdot x}\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right) \otimes \ket{0}\bra{0}\\ &\ \ \ + \frac{1}{2^n}\sum_{x: p(x) = 1} \left(\sum_{u_1,u_2}(-1)^{(u_1 \oplus u_2)\cdot x}\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right) \otimes \ket{1}\bra{1} \\
&= \frac{1}{2^n}\sum_{u_1,u_2}\ket{\psi_{u_1}}\bra{\psi_{u_2}} \otimes \left(\sum_{x:p(x)=0}(-1)^{(u_1 \oplus u_2)\cdot x}\ket{0}\bra{0} + \sum_{x:p(x)=1}(-1)^{(u_1 \oplus u_2)\cdot x}\ket{1}\bra{1}\right) \\ &= \frac{1}{2^n}\sum_{u_1,u_2}2^{n/2}\delta_{u_1 = u_2} \ket{\psi_{u_1}}\bra{\psi_{u_2}} \otimes \left(\ket{0}\bra{0} + \ket{1}\bra{1}\right) \\
&= \frac{1}{2}\sum_{u:\cH\cW < n/2}\ket{\psi_u}\bra{\psi_u} \otimes \left(\ket{0}\bra{0} + \ket{1}\bra{1}\right) \\ &= \Tr_\cX(\ket{\gamma}\bra{\gamma}) \otimes \left(\frac{1}{2}\ket{0}\bra{0} + \frac{1}{2}\ket{1}\bra{1}\right),
\end{align*}

where the 3rd equality is due to the following claim, plus the observation that $u_1 \oplus u_2 \neq 1^n$ for any $u_1,u_2$ such that $\cH\cW(u_1),\cH\cW(u_2) < n/2$.

For any $u \in \{0,1\}^n$ such that $u \notin \{0^n,1^n\}$, it holds that
\[\sum_{x:p(x)=0}(-1)^{u\cdot x} = \sum_{x:p(x)=1}(-1)^{u\cdot x} = 0.\]

For any such $u \notin \{0^n,1^n\}$, define $S_0 = \{i : u_i = 0\}$ and $S_1 = \{i : u_i = 1\}$. Then, for any $y_0 \in \{0,1\}^{|S_0|}$ and $y_1 \in \{0,1\}^{|S_1|}$, define $x_{y_0,y_1} \in \{0,1\}^n$ to be the $n$-bit string that is equal to $y_0$ when restricted to indices in $S_0$ and equal to $y_1$ when restricted to indices in $S_1$. Then,

\begin{align*}
&\sum_{x:p(x)=0}(-1)^{u \cdot x} = \sum_{y_1 \in \{0,1\}^{|S_1|}}\sum_{y_0 \in \{0,1\}^{|S_0|}: p(x_{y_0,y_1})=0} (-1)^{u \cdot x_{y_0,y_1}}\\ &= \sum_{y_1 \in \{0,1\}^{|S_1|}}2^{|S_0|-1}(-1)^{1^{|S_1|} \cdot y_1} = 2^{|S_0|-1}\sum_{y_1 \in \{0,1\}^{|S_1|}}(-1)^{p(y_1)} = 0,
\end{align*}

and the same sequence of equalities can be seen to hold for $x : p(x) = 1$.

§.§ RO extractor

Let $H : \{0,1\}^n \to \{0,1\}^m$ be a uniformly random function, and let $q,C,k$ be integers. Consider a two-stage oracle algorithm $(A_1^H, A_2^H)$ that combined makes at most $q$ queries to $H$. Suppose that $A_1^H$ outputs classical strings $(T,\{x_i\}_{i \in T})$, and let $\ket{\gamma}_{\cA,\cX}$ be its left-over quantum state,[That is, consider sampling $H$, running a purified $A_1^H$, measuring at the end to obtain $(T,\{x_i\}_{i \in T})$, and then defining $\ket{\gamma}$ to be the left-over state on $\cA$'s remaining registers.] where $T \subset [n]$ is a set of size $n-k$, each $x_i \in \{0,1\}$, $\cA$ is a register of arbitary size, and $\cX$ is a register of $k$ qubits. Suppose further that with probability 1 over the sampling of $H$ and the execution of $A_1$, there exists a set $L \subset \{0,1\}^k$ of size at most $C$ such that $\ket{\gamma}$ may be written as follows:
\[\ket{\gamma} = \sum_{u \in L}\ket{\psi_u}_\cA \otimes \ket{u}_\cX.\]
Now consider the following two games.

* $\mathsf{REAL}$:

* $A_1^H$ outputs $T,\{x_i\}_{i \in T},\ket{\gamma}_{\cA,\cX}$.

* $\cX$ is measured in the Hadamard basis to produce a $k$-bit string which is parsed as $\{x_i\}_{i \in \overline{T}}$, and a left-over state $\ket{\gamma'}_{\cA}$ on register $\cA$. Define $x = (x_1,\dots,x_n)$.

* $A_2^H$ is given $T, \{x_i\}_{i \in T},\ket{\gamma'}_{\cA}, H(x)$, and outputs a bit.

* $\mathsf{IDEAL}$:

* $A_1^H$ outputs $T,\{x_i\}_{i \in T},\ket{\gamma}_{\cA,\cX}$.

* $r \gets \{0,1\}^m$.

* $A_2^H$ is given $T, \{x_i\}_{i \in T},\Tr_\cX(\ket{\gamma}\bra{\gamma}),r$, and outputs a bit.

\[\left|\Pr[\mathsf{REAL} = 1] - \Pr[\mathsf{IDEAL} = 1]\right| \leq \frac{2\sqrt{q}C + 2q\sqrt{C}}{2^{k/2}} < \frac{4qC}{2^{k/2}}.\]

The proof follows via two steps. First, we define a HYBRID distribution where we re-program the random oracle at input $x$ to a uniformly random string $r$, and argue that the adversary cannot notice, even given $x$. Intuitively, this is establishing that $H(x)$ must have been quite close to uniformly random from the adversary's perspective at the point that $x$ is measured (on average over $x$). This requires a new “adaptive re-programming” lemma for the QROM, where the point $x$ that is adaptively re-programmed may be sampled from a quantum source of entropy. As mentioned in the introduction, all previous adaptive re-programming lemmas have only handled classical entropy sources. Second, we “undo” the re-programming of $H(x)$, but still output (uniformly random) $r$ as the extracted string. Indistinguishability of these two games, on the other hand, can be established via a one-way-to-hiding lemma, since in the final game, the adversary is given no information at all about the measured string $x$. In particular, it suffices to use the fact that $x$ has high quantum min-entropy conditioned on the adversary's state to argue that the adversary cannot guess $x$ and thus cannot notice whether or not $H(x)$ was re-programmed.

Now we formalize this strategy. Consider the following hybrid game.

* $\mathsf{HYBRID}$:

* $A_1^H$ outputs $T,\{x_i\}_{i \in T},\ket{\gamma}_{\cA,\cX}$.

* $\cX$ is measured in the Hadamard basis to produce a $k$-bit string which is parsed as $\{x_i\}_{i \in \overline{T}}$, and a left-over state $\ket{\gamma'}_{\cA}$ on register $\cA$. Define $x = (x_1,\dots,x_n)$. Sample $r \gets \{0,1\}^m$, and re-program $H(x)$ to $r$.

* $A_2^H$ is given $T, \{x_i\}_{i \in T},\ket{\gamma'}_{\cA}, r$, and outputs a bit.

The theorem follows by combining the two following claims.

\[|\Pr[\mathsf{REAL} = 1] - \Pr[\mathsf{HYBRID} = 1]| \leq \frac{2\sqrt{q}C}{2^{k/2}}.\]

Consider purifying the random oracle $H$ on register $\cR$, and let $\ket{\widehat{\gamma}}_{\cR,\cA,\cX}$ be the left-over state of $A_1$ and the random oracle in $\mathsf{REAL}$ or $\mathsf{HYBRID}$ after $A_1$ outputs $(T,\{x_i\}_{i \in T})$. By <ref>, the state $\ket{\widehat{\gamma}}_{\cR,\cA,\cX}$ satisfies the premise of <ref> below, where $\cF$ is the set of $2^k$ sub-registers of $\cR$ corresponding to each $x' \in \{0,1\}^n$ such that $x'_i = x_i$ for all $i \in T$.

Now, consider a reduction that receives the state $\rho^{\mathsf{REAL}}$ or $\rho^{\mathsf{REPROG}}$ from <ref>, measures $\cF_{x}$ in the computational basis to obtain $H(x)$, and then continues to run $A_2$ on input $H(x)$ (along with $A_1$'s state on $\cA$ and $T$, $\{x_i\}_{i \in T}$). In the case of $\rho^{\mathsf{REAL}}$, this exactly matches the $\mathsf{REAL}$ game and in the case of $\rho^{\mathsf{REPROG}}$, this exactly matches the $\mathsf{HYBRID}$ game, using the fact that $\ket{\phi_0}$ (as defined in <ref>) is the uniform superposition state.

\[|\Pr[\mathsf{HYBRID} = 1] - \Pr[\mathsf{IDEAL} = 1]| \leq \frac{2q\sqrt{C}}{2^{k/2}}.\]

This follows from an invocation of <ref>. Consider the distribution over $(S,O_1,O_2,\ket{\psi})$ that results from the following.

* Sample $O_1$ as a random oracle $H$,

* run $A_1^H$ to obtain $T,\{x_i\}_{i \in T},\ket{\gamma}_{\cA,\cX}$,

* measure to obtain $\{ x_i \}_{ i\in \overline{T}}$ as in the $\mathsf{HYBRID}$ game, define $x = (x_1,\dots,x_n)$, and define $S = \{x\}$,

* sample $r \gets \{0,1\}^m$, and let $O_2$ be the same as $O_1$, except that $O_2(x) = r$,

* let $\ket{\psi}$ be the resulting state on register $\cA$ along with the classical information $(T,\{x_i\}_{i \in T},r)$.

Then, $\Pr[\mathsf{IDEAL} = 1] = P_{\text{left}}$ and $\Pr[\mathsf{HYBRID} = 1] = P_{\text{right}}$, so it suffices to bound $P_{\text{guess}}$. By <ref>, $P_{\text{guess}}$ is upper bounded by $1/2^{\ell}$, where $\ell$ is the quantum conditional min-entropy of $\{x_i\}_{i \in \overline{T}}$ given register $\cA$. By <ref>, and the fact that measuring an unentangled $k$-bit standard basis vector in the Hadamard basis gives $k$ bits of quantum conditional min-entropy, $P_\text{guess}$ is upper bounded by $\frac{C}{2^{k}}$. Thus, <ref> gives the final bound of $\frac{2q\sqrt{C}}{2^{k/2}}$.

Setup. Consider a state $\ket{\gamma}_{\cA,\cF,\cX}$ initially on three registers, $\cA$ for the adversary, $\cF$ for the random oracle (written in purified form), and $\cX$. The parts of the state on $\cF$ and $\cX$ satisfy some special properties: $\cF$ is the result of interacting with the QROM with at most $q$ queries, and $\cX$ is in a superposition of a small number of terms in the computational basis. Say that $\cX$ is measured in the Hadamard basis to produce $x$, and then $x$ is queried to the random oracle to obtain $y$, which is placed in register $\cY$. This produces a mixed state $\rho_{\cA,\cF,\cX,\cY}$. Ultimately, we want to prove the following claim:

\[\TD\left(\Tr_\cX(\rho),\Tr_{\cX,\cY}(\rho) \otimes \frac{1}{2^n}\sum_{y}\ket{y}\bra{y}^{\nishant{\cY}}\right) = \negl(n).\]

$n$ not defined yet? + small question to ask yeah $n$ is just defined to be the size of the output of the random oracle, actually this should be $m$ to be consistent with what is below Below, we show a different claim, which establishes at least that $y=H(x)$ is close to uniformly random from the adversary's perspective. In particular, we show that

\[\TD\left(\rho,\rho^{\cF:x \to r}\right) = \negl(n),\]

where $\rho^{\cF:x \to r}$ indicates that $\cF$ has been re-rogrammed to uniformly random at index $x$, right after $\cX$ was measured to obtain $x$, but right before $y = H(x)$ was written to $\cY$.

§.§ The superposition oracle

Following <cit.>, we will use the fact that a quantum accesible random oracle $H: \{0,1\}^n \to \{0,1\}^m$ can be implemented as follows.

* Let $\cF$ be a $(m \cdot 2^n)$-qubit register split into $2^n$ subregisters $\{\cF_x\}_{x \in \{0,1\}^n}$ of size $m$. Let $\ket{\phi_0}$ be the uniform superposition state. Prepare an initial state
\[\ket{\Psi}_\cF = \bigotimes_{x \in \{0,1\}^n} \ket{\phi_0}_{{\cF_x}}.\]

* A query on registers $\cX,\cY$ is answered with a unitary $O_{\cX,\cY,\cF}$ such that
\[O_{\cX,\cY,\cF}\ket{x}\bra{x}_\cX = \ket{x}\bra{x}_\cX \otimes (\mathsf{CNOT}^{\otimes m})_{\cF_x : \cY}.\]

* Register $\cF$ is measured to obtain a random function $H$.

Let $\ket{\psi_q}_{\cA,\cF}$ be the joint adversary-oracle state state after an adversary has made $q$ queries to the superposition oracle on register $\cF$. Then this state can be written as
\[\ket{\psi_q}_{\cA,\cF} = \sum_{S \subset \{0,1\}^n, |S| \leq q} \ket{\psi_{q,S}}_{\cA,\cF_S} \otimes \left(\ket{\phi_0}^{\otimes (2^n - |S|)}\right)_{\cF_{\overline{S}}},\]
where $\ket{\psi_{q,S}}$ are such that $\bra{\phi_0}_{\cF_x}\ket{\psi_{q,S}}_{\cA,\cF_S} = 0$ for all $x \in S$.

§.§ Re-programming
In this section, we prove the following lemma.

Let $\ket{\phi_0}$ be an $m$-qubit unit vector, and let $\cF$ be a $(m \cdot 2^k)$-qubit register split into $2^k$ sub-registers $\{\cF_x\}_{x \in \{0,1\}^k}$ of $m$ qubits. Let $\cA$ be an arbitrary register and $\cX$ be an $k$-qubit register. Consider any state $\ket{\gamma}_{\cF,\cA,\cX}$, set $L \subseteq \{0,1\}^k$, and integer $q \in \bbN$, such that $\ket{\gamma}$ can be written as

\[\ket{\gamma} = \sum_{u \in L} \ket{\widehat{\psi}_u}_{\cF,\cA} \otimes \ket{u}_\cX,\]

where each

\[\frac{\ket{\widehat{\psi}_u}}{\|\ket{\widehat{\psi}_u}\|} = \sum_{S \subset \{0,1\}^n : |S| \leq q} \ket{\psi_{u,S}}_{\cA,\cF_S} \otimes \left(\ket{\phi_0}^{(2^k-|S|)}\right)_{\cF_{\overline{S}}},\]
and each $\ket{\psi_{u,S}}$ is orthogonal to $\ket{\phi_0}_{\cF_x}$ for all $x \in S$. Let

* $\rho^{\mathsf{REAL}}_{\cF,\cA,\cX}$ be the mixed state that results from measuring $\cX$ in the Hadamard basis to produce $x \in \{0,1\}^k$ and a left-over state $\ket{\gamma_x}_{\cF,\cA}$, and outputting $\ket{\gamma_x}\bra{\gamma_x} \otimes \ket{x}\bra{x}$, and

* $\rho^{\mathsf{REPROG}}_{\cF,\cA,\cX}$ be the mixed state that results from measuring $\cX$ in the Hadamard basis to produce $x \in \{0,1\}^k$ and a left-over state $\ket{\gamma_x}_{\cF,\cA}$, and outputting $\Tr_{\cF_x}\left(\ket{\gamma_x}\bra{\gamma_x}\right) \otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x} \otimes \ket{x}\bra{x}$.

\[\TD\left(\rho^{\mathsf{REAL}},\rho^{\mathsf{REPROG}}\right) \leq \frac{2\sqrt{q}|L|}{2^{k/2}}.\]

For each $u \in L$, let $a_u \coloneqq \|\ket{\widehat{\psi}_u}\|$, and $\ket{\psi_u} \coloneqq \ket{\widehat{\psi}_u}/a_u$. Consider applying the Hadamard transform to register $\cX$ of $\ket{\gamma}$, producing

\[\sum_{x \in \{0,1\}^k,u \in L}\frac{(-1)^{u \cdot x}a_u}{2^{k/2}}\ket{\psi_u}_{\cF,\cA} \otimes \ket{x}_{\cX} \coloneqq \sum_{x \in \{0,1\}^k}\ket{\gamma_x}_{\cF,\cA} \otimes \ket{x}_{\cX}\]
and then measuring in the computational basis to produce $x$ and left-over state $\ket{\gamma_x}\bra{\gamma_x}_{\cF,\cA}.$

The lemma asks to bound the following quantity.

\begin{align*}
\frac{1}{2}&\Bigg\|\sum_{x \in \{0,1\}^k}\ket{\gamma_x}\bra{\gamma_x}_{\cF,\cA} \otimes \ket{x}\bra{x} - \sum_{x \in \{0,1\}^k}\Tr_{\cF_{x}}\left(\ket{\gamma_x}\bra{\gamma_x}_{\cF,\cA}\right) \otimes \ket{\phi_0}\bra{\phi_0}_{\cF_{x}} \otimes \ket{x}\bra{x} \Bigg\|_1 \\
&= \frac{1}{2}\Bigg\|\frac{1}{2^k}\sum_{x \in \{0,1\}^k}\sum_{u_1,u_2 \in L}(-1)^{(u_1 \oplus u_2) \cdot x}a_{u_1}a_{u_2}\ket{\psi_{u_1}}\bra{\psi_{u_2}} \otimes \ket{x}\bra{x} \\
&\ \ \ - \frac{1}{2^k}\sum_{x \in \{0,1\}^k}\Tr_{\cF_x}\left(\sum_{u_1,u_2 \in L}(-1)^{(u_1 \oplus u_2) \cdot x}a_{u_1}a_{u_2}\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right) \otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x} \otimes \ket{x}\bra{x}\Bigg\|_1 \\
&\leq \frac{1}{2^{k+1}}\sum_{u_1,u_2 \in L}a_{u_1}a_{u_2}\left\|\sum_{x \in \{0,1\}^k}\left(\ket{\psi_{u_1}}\bra{\psi_{u_2}} \otimes \ket{x}\bra{x}\right) - \left(\Tr_{\cF_x}\left(\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right)\otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x} \otimes \ket{x}\bra{x}\right)\right\|_1 \\
&\leq \frac{1}{2^{k+1}}\sum_{u_1,u_2 \in L}a_{u_1}a_{u_2}\sum_{x \in \{0,1\}^n}\left\|\ket{\psi_{u_1}}\bra{\psi_{u_2}} - \Tr_{\cF_x}\left(\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right)\otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x}\right\|_1,\end{align*}

where the inequalities follow from the triangle inequality. Now, following the proof of <cit.>, for any $u_1,u_2,$ and $x$, we can write
\begin{align*}\ket{\psi_{u_1}}\bra{\psi_{u_2}} = &\bra{\phi_0}_{\cF_x}\ket{\psi_{u_1}}\bra{\psi_{u_2}}\ket{\phi_0}_{\cF_x} \otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x} + \ket{\psi_{u_1}}\bra{\psi_{u_2}}(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\\ &+ (\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\ket{\phi_0}\bra{\phi_0}_{\cF_x}\end{align*}

\begin{align*}
\Tr_{\cF_x}\left(\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right)\otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x} = &\bra{\phi_0}_{\cF_x}\ket{\psi_{u_1}}\bra{\psi_{u_2}}\ket{\phi_0}_{\cF_x} \otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x}\\ &+ \Tr_{\cF_x}\left((\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right) \otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x}
\end{align*}

\begin{align*}
&\left\|\ket{\psi_{u_1}}\bra{\psi_{u_2}} - \Tr_{\cF_x}\left(\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right)\otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x}\right\|_1 \leq \|\ket{\psi_{u_1}}\bra{\psi_{u_2}}(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\|_1 \\ &+ \|(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\ket{\phi_0}\bra{\phi_0}_{\cF_x}\|_1 + \|\Tr_{\cF_x}\left((\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right) \otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x}\|_1.
\end{align*}

Now, for each $x,u$, define $\alpha_{x,u} = \|\bra{\phi_0}_{\cF_x}\ket{\psi_{u}}\|$. The first term above simplifies as

\begin{align*}
\|\ket{\psi_{u_1}}\bra{\psi_{u_2}}(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\|_1 = \|\bra{\psi_{u_2}}(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\| = \sqrt{1-\bra{\psi_{u_2}}\ket{\phi_0}\bra{\phi_0}\ket{\psi_{u_2}}} = \sqrt{1-\alpha_{x,u_2,}^2}.
\end{align*}

The second term above simplifies as

\begin{align*}
&\|(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\ket{\phi_0}\bra{\phi_0}_{\cF_x}\|_1 \leq \|(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\|_1 \\ &= \|(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\| = \sqrt{1-\bra{\psi_{u_1}}\ket{\phi_0}\bra{\phi_0}\ket{\psi_{u_1}}} = \sqrt{1-\alpha_{x,u_1}^2},
\end{align*}

where the inequality is Holder's inequality. The third term simplifies as

\begin{align*}
&\left\|\Tr_{\cF_x}\left((\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right) \otimes \ket{\phi_0}\bra{\phi_0}_{\cF_x}\right\|_1 =  \left\|\Tr_{\cF_x}\left((\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right)\right\|_1 \\ &\leq \left\|(\bbI - \ket{\phi_0}\bra{\phi_0}_{\cF_x})\ket{\psi_{u_1}}\bra{\psi_{u_2}}\right\|_1 = \sqrt{1-\alpha^2_{x,u_1}},
\end{align*}

where the inequality is the following fact from <cit.>: for any bounded operator $T$ on $\cA \otimes \cB$, $\|\Tr_\cB(T)\|_1 \leq \|T\|_1$.

Thus, the distinguishing advantage can be bounded by

\begin{align*}
&\frac{1}{2^{k+1}}\sum_{u_1,u_2 \in L}a_{u_1}a_{u_2}\sum_{x \in \{0,1\}^k}2\sqrt{1-\alpha^2_{x,u_1}} + \sqrt{1-\alpha^2_{x,u_2}}  \\ &\leq \frac{1}{2^{k}}\sum_{u_1,u_2 \in L}a_{u_1}a_{u_2}\left(\sum_{x \in \{0,1\}^k}\sqrt{1-\alpha^2_{x,u_1}} + \sum_{x \in \{0,1\}^k}\sqrt{1-\alpha^2_{x,u_2}}\right)
\\ &\leq \frac{1}{2^{k}}\sum_{u_1,u_2 \in L}a_{u_1}a_{u_2}\left(\sqrt{2^k\left(2^k - \sum_{x \in \{0,1\}^k}\alpha^2_{x,u_1}\right)}+\sqrt{2^k\left(2^k - \sum_{x \in \{0,1\}^k}\alpha^2_{x,u_2}\right)}\right),
\end{align*}

where the second inequality follows from Cauchy-Schwartz.

Now, for any $u$,

\begin{align*}
&\sum_{x \in \{0,1\}^k}\alpha^2_{x,u} = \sum_{x \in \{0,1\}^k} \| \bra{\phi_0}_{\cF_x}\ket{\psi_{u}}\|^2 \|\\ &= \sum_{x \in \{0,1\}^k}\bigg\|\sum_{S \subset \{0,1\}^k : |S| \leq q} \bra{\phi_0}_{\cF_x}\ket{\psi_{u,S}}_{\cA,\cF_S} \otimes \left(\ket{\phi_0}^{(2^k-|S|)}\right)_{\cF_{\overline{S}}}\bigg\|^2 \\ &= \sum_{x \in \{0,1\}^k}\bigg\|\sum_{S \not\owns x} \ket{\psi_{u,S}}_{\cA,\cF_S} \otimes \left(\ket{\phi_0}^{(2^k-|S|)}\right)_{\cF_{\overline{S}}}\bigg\|^2,
\end{align*}

where the last equality follows since $\ket{\phi_0}_{\cF_x}$ is orthogonal to $\ket{\psi_{u,S}}$ for all $x \in S$, and $\ket{\phi_0}$ is normalized. Now, since each of the summands in the inner summation are pairwise orthogonal (so that we can move the summation outside of the norm), we can write

\begin{align*}
&\sum_{x \in \{0,1\}^k}\bigg\|\sum_{S \not\owns x} \ket{\psi_{u,S}}_{\cA,\cF_S} \otimes \left(\ket{\phi_0}^{(2^k-|S|)}\right)_{\cF_{\overline{S}}}\bigg\|^2 = \sum_{S}\sum_{x \notin S}\bigg\|\ket{\psi_{u,S}}_{\cA,\cF_{S}} \otimes \left(\ket{\phi_0}^{(2^k-|S|)}\right)_{\cF_{\overline{S}}}\bigg\|^2 \\ &\geq (2^k-q)\sum_{S}\bigg\|\ket{\psi_{u,S}}_{\cA,\cF_{S}} \otimes \left(\ket{\phi_0}^{(2^k-|S|)}\right)_{\cF_{\overline{S}}}\bigg\|^2 = (2^k-q)\bigg\|\sum_S \ket{\psi_{u,S}}_{\cA,\cF_{S}} \otimes \left(\ket{\phi_0}^{(2^k-|S|)}\right)_{\cF_{\overline{S}}}\bigg\|^2 \\ &= (2^k - q)\|\ket{\psi_{u}}\|^2 = 2^k - q.
\end{align*}

Thus, the distinguishing advantage can be bounded by

\begin{align*}
\frac{2}{2^{k}}\sqrt{2^k \cdot q}\sum_{u_1,u_2 \in L}a_{u_1}a_{u_2} \leq \frac{2\sqrt{q}|L|}{2^{k/2}},
\end{align*}

since, by Cauchy-Schwartz and the fact that $\sum_{u \in L} a_u^2 = 1$, we can bound $\sum_{u \in L}a_u \leq \sqrt{|L|}$.

§ COMMITMENTS

§.§ Construction

Extractable and equivocal commitment scheme

Parameters: security parameter $\secp$, number of commitments $n = n(\lambda)$

Random oracle: $H:\zo^{\secp+1} \rightarrow \zo^{\secp+1}$.

* $\Com^{H}(1^\secp,\{b_i\}_{i \in [n]})$: For all $i \in [n]$, sample $r_i \leftarrow \zo^\secp$ and set $\com_i = H(b_i||r_i)$. Set $\state = \{b_i,r_i\}_{i \in [n]}$ and output $(\state, \{\com_i\}_{i \in [n]})$.

* $\Open^{H}(\state, T)$: Parse $\state$ as $\{b_i,r_i\}_{i \in [n]}$ and output $\{b_i,r_i\}_{i \in T}$.

* $\Rec^{H}(\{\com_i\}_{i \in [n]},T,\{b_i,r_i\}_{i \in T})$: Output $\bot$ if there exists $i \in T$ s.t. $H(b_i||r_i) \neq \com_i$. Otherwise output $\{b_i\}_{i \in T}$.

We construct extractable and equivocal bit commitments in the QROM in <ref>. Without loss of generality, a committer can commit to strings of length $>1$ by committing to each bit in the string one by one, and sending all commitments in parallel.

§.§ Extractability

In this section, we prove the following theorem by relying on

We remark that our proof of extraction uses ideas already present in <cit.> to establish that our construction satisfies <ref>.

fig:uccomm-protocol is a $\mu$-extractable non-interactive commitment scheme with partial opening in the QROM, with message length $1$ (i.e. $k=1$), satisfying <ref>, where $\mu(\secp,q, n) =\frac{8qn}{2^{\secp/2}} + \frac{148(q+n+1)^3+1}{2^{\secp}}$[When $n = c \lambda$ for some arbitrary fixed constant $c$, then we can define $\mu_c(\secp, q) = \frac{2q(c \secp)^{1/2}}{2^{\secp/2}}$. In all our OT protocols, we will set $n$ in this manner and will assume that $\mu$ is a function of $\lambda, q$.], and where the runtime of the simulator is bounded by $s(\secp,q) = O(q^2 + q\cdot n(\secp))$. In addition, the protocol satisfies extraction with $\nu$-commuting simulator, where $\nu(\secp) = \frac{8}{2^{\secp/2}}$.

Let $(\simro.\RO,\simro.\sE)$ be the on-the-fly random oracle simulator with extraction from <ref>. The extractable commitment simulator $\SimExt = (\SimExt.\RO,\SimExt.\Ext)$ is defined as follows.

* $\SimExt.\RO = \simro.\RO$

* $\SimExt.\Ext$ runs $\simro.\sE$ to obtain either a $\secp+1$ bit string $x^*$, or $\emptyset$. In the case of $x^*$, output the first bit of $x^*$. In the case of $\emptyset$, output 0.

We now prove that for any family of quantum oracle algorithms $\{\Adv_\secp = (\Adv_{\Commit,\secp},\Adv_{\Open,\secp},\sD_{\secp})\}_{\secp \in \bbN}$, the two experiments in <ref> are $\mu(\secp,q)$ close, where $\mu(\secp,q) = \frac{148(q+n+1)^3+1}{2^{\secp}} + \frac{8qn}{2^{\secp/2}}$. We consider the following sequence of hybrids (where parts in blue indicate difference from the previous hybrid):

* $\Hyb_0$: This corresponds to the “real” experiment in <ref>.

* Sample oracle $H \leftarrow F_{\zo^{\secp+1} \rightarrow \zo^{\secp+1}}$.

* $(\brho_{1},\{\com_i\}_{i \in [n]}) \gets \Adv_{\Commit,\secp}^H$

* $(\brho_{2},\{b_i,r_i\}_{i \in T}) \gets \Adv_{\Open,\secp}^H(\brho_{1})$

* $\out \gets \Rec^H(\{\com_i\}_{i \in [n]},\{b_i,r_i\}_{i \in T})$

* Output $b \gets \sD_{\secp}^H(\brho_{2},\out)$

* $\Hyb_1$: This is the same as previous hybrid, except that all oracle calls to $H$ are answered by $\simro.\RO$.

* Initialize the extractable random oracle simulator, $\simro$.

* $(\brho_{1},\{\com_i\}_{i \in [n]}) \gets \Adv_{\Commit,\secp}^{\nblue{\simro.\RO}}$

* $(\brho_{2},\{b_i,r_i\}_{i \in T}) \gets \Adv_{\Open,\secp}^{\nblue{\simro.\RO}}(\brho_{1})$

* $\out \gets \Rec^{\nblue{\simro.\RO}}(\{\com_i\}_{i \in [n]},\{b_i,r_i\}_{i \in T})$

* Output $b \leftarrow \sD_{\secp}^{\nblue{\simro.\RO}}(\brho_{2},\out)$

* $\Hyb_2$: This is the same as the previous hybrid except for an additional query to $\simro.\RO$ that is performed at the end of the experiment, along with an event $\mathsf{BAD}$ that we define. Notice also that we have opened up the description of the algorithm $\Rec$ below. The hybrid outputs the following distribution.

* Initialize the extractable random oracle simulator, $\simro$.

*  $(\brho_{1},\{\com_i\}_{i \in [n]}) \gets \Adv_{\Commit,\secp}^{\simro.\RO}$

*  $(\brho_{2},\{b_i,r_i\}_{i \in T}) \gets \Adv_{\Open,\secp}^{\simro.\RO}(\brho_{1})$

* $\out \gets \Rec^{\simro.\RO}(\{\com_i\}_{i \in [n]},\{b_i,r_i\}_{i \in T})$

* If there exists $i \in T$ s.t. $\simro.\RO(b_i||r_i) \neq \com_i$, set $\out \coloneqq \bot$, otherwise set $\out \coloneqq \{b_i\}_{i \in T}$.

Obtain bit $b \leftarrow \sD_{\secp}^{\simro.\RO}(\brho_{2},\out)$.

* For all $i \in [n]$, set $y_i \leftarrow \simro.\RO(b_i||r_i)$.

* If $\out \neq \bot$ and there exists $i \in T$ such that $y_i \neq \com_i$, output $\mathsf{BAD}$, otherwise output $b$.

* $\Hyb_3:$ This is the same as the previous hybrid except that there is a query to $\simro.\sE$, and an extra condition in the $\mathsf{BAD}$ event. The hybrid outputs the following distribution:

* Initialize the extractable random oracle simulator, $\simro$.

* $(\brho_{1},\{\com_i\}_{i \in [n]}) \gets \Adv_{\Commit,\secp}^{\simro.\RO}$

* $(\brho_{2},\{b_i,r_i\}_{i \in T}) \gets \Adv_{\Open,\secp}^{\simro.\RO}(\brho_{1})$

* $\out \gets \Rec^{\simro.\RO}(\{\com_i\}_{i \in [n]},\{b_i,r_i\}_{i \in T})$

* If there exists $i \in T$ s.t. $\simro.\RO(b_i||r_i) \neq \com_i$, set $\out \coloneqq \bot$, otherwise set $\out \coloneqq \{b_i\}_{i \in T}$.

* Obtain bit $b \leftarrow \sD_{\secp}^{\simro.\RO}(\brho_{2},\out)$

* For all $i \in [n]$, set $y_i \leftarrow \simro.\RO(b_i||r_i)$.

* For all $i \in [n]$, set $x^*_i \leftarrow \simro.\sE(\com_i)$.

* If there exists $i \in T$ such that
$(x_i^* \neq (b_i||r_i)) \wedge (y_i=\com_i)$, output $\mathsf{BAD}$, or if $\out \neq \bot$ and there exists $i \in T$ such that $y_i \neq \com_i$, output $\mathsf{BAD}$, otherwise output

* $\Hyb_4$: This hybrid is identical to the previous one except that $\simro.\sE$ is called earlier on in the hybrid. The hybrid outputs the following distribution:

* Initialize the extractable random oracle simulator, $\simro$.

* $(\brho_{1},\{\com_i\}_{i \in [n]}) \gets \Adv_{\Commit,\secp}^{\simro.\RO}$

* For all $i \in [n]$, set $x^*_i \leftarrow \simro.\sE(\com_i)$.

* $(\brho_{2},\{b_i,r_i\}_{i \in T}) \gets \Adv_{\Open,\secp}^{\simro.\RO}(\brho_{1})$

* $\out \gets \Rec^{\simro.\RO}(\{\com_i\}_{i \in [n]},\{b_i,r_i\}_{i \in T})$

* If there exists $i \in T$ s.t. $\simro.\RO(b_i||r_i) \neq \com_i$, set $\out \coloneqq \bot$, otherwise set $\out \coloneqq \{b_i\}_{i \in T}$.

* $b \leftarrow \sD_{\secp}^{\simro.\RO}(\brho_{2},\out)$

* For all $i \in [n]$, set $y_i \leftarrow \simro.\RO(b_i||r_i)$.

* If there exists $i \in T$ such that
$(x_i^* \neq (b_i||r_i)) \wedge (y_i=\com_i)$, output $\mathsf{BAD}$, or if $\out \neq \bot$ and there exists $i \in T$ such that $y_i \neq \com_i$, output $\mathsf{BAD}$, otherwise output

* $\Hyb_5$: This hybrid is identical to the previous hybrid except for altering the variable $\mathsf{out}$ to sometimes take the value $\mathsf{FAIL}$. The hybrid outputs the following distribution:

* Initialize the extractable random oracle simulator, $\simro$.

* $(\brho_{1},\{\com_i\}_{i \in [n]}) \gets \Adv_{\Commit,\secp}^{\simro.\RO}$

* For all $i \in [n]$, set $x^*_i \leftarrow \simro.\sE(\com_i)$.
For all $i \in [n]$, if $x_i^* = \emptyset$, set $b^*_i \coloneqq 0$, and otherwise set $b^*_i$ equal to the first bit of $x_i^*$.

* $(\brho_{2},\{b_i,r_i\}_{i \in T}) \gets \Adv_{\Open,\secp}^{\simro.\RO}(\brho_{1})$

*  Obtain $\out \leftarrow \Rec^{\simro.\RO}(\{\com_i\}_{i \in [n]},\{b_i,r_i\}_{i \in T})$ as follows:

* If there exists $i \in T$ s.t. $\simro.\RO(b_i||r_i) \neq \com_i$, set $\out \coloneqq \bot$, otherwise set $\out \coloneqq \{b_i\}_{i \in T}$.

*  If $\out \notin \{\{b_i^*\}_{i \in T},\bot\}$, set $\out = \mathsf{FAIL}$.

* $b \leftarrow \sD_{\secp}^{\simro.\RO}(\brho_{2},\out)$

* For all $i \in [n]$, set $y_i \leftarrow \simro.\RO(b_i||r_i)$.

* If there exists $i \in T$ such that
$(x_i^* \neq (b_i||r_i)) \wedge (y_i=\com_i)$, output $\mathsf{BAD}$, or if $\out \neq \bot$ and there exists $i \in T$ such that $y_i \neq \com_i$, output $\mathsf{BAD}$, otherwise output $b$.

* $\Hyb_6$: This hybrid is identical to the previous hybrid except for removing the final query to $\simro.\RO$ and the event $\mathsf{BAD}$.

* Initialize the extractable random oracle simulator, $\simro$.

* $(\brho_{1},\{\com_i\}_{i \in [n]}) \gets \Adv_{\Commit,\secp}^{\simro.\RO}$

* For all $i \in [n]$, set $x^*_i \leftarrow \simro.\sE(\com_i)$.
For all $i \in [n]$, if $x_i^* = \emptyset$, set $b^*_i \coloneqq 0$, and otherwise set $b^*_i$ equal to the first bit of $x_i^*$.

* $(\brho_{2},\{b_i,r_i\}_{i \in T}) \gets \Adv_{\Open,\secp}^{\simro.\RO}(\brho_{1})$

*  Obtain $\out \leftarrow \Rec^{\simro.\RO}(\{\com_i\}_{i \in [n]},\{b_i,r_i\}_{i \in T})$ as follows:

* If there exists $i \in T$ s.t. $\simro.\RO(b_i||r_i) \neq \com_i$, set $\out \coloneqq \bot$, otherwise set $\out \coloneqq \{b_i\}_{i \in T}$.

* If $\out \notin \{\{b_i^*\}_{i \in T},\bot\}$, set $\out = \mathsf{FAIL}$.

* $b \leftarrow \sD_{\secp}^{\simro.\RO}(\brho_{2},\out)$

* For all $i \in [n]$, set $y_i \leftarrow \simro.\RO(b_i||r_i)$.

* If there exists $i \in T$ such that
$(x_i^* \neq (b_i||r_i)) \wedge (y_i=\com_i)$, output $\mathsf{BAD}$, or if $\out \neq \bot$ and there exists $i \in T$ such that $y_i \neq \com_i$, output $\mathsf{BAD}$, otherwise output $b$.

We note that $\Hyb_6$ is the simulated distribution. We prove indistinguishability between the hybrids below.

$\Pr[\Hyb_0=1] = \Pr[\Hyb_1=1]$

This follows from the indistinguishable simulation property of Imported Theorem <ref>.

$\Pr[\Hyb_1=1] = \Pr[\Hyb_2=1]$

First, adding the extra query to $\simro.\RO$ does not affect the output of the experiment since it is performed after $b$ is computed. Next, the event $\mathsf{BAD}$ only occurs if some classical query $(b_i||r_i)$ to $\simro.\RO$ returns different classical values at different points in the experiment. However, this can never occur due to the indistinguishable simulation property of Imported Theorem <ref>, and because two classical queries to an oracle $H$ always return the same value.

$|\Pr[\Hyb_2=1] - \Pr[\Hyb_3=1]| \leq  \frac{148(q+n+1)^3+1}{2^{\secp}}$

First, adding the query to $\simro.\sE$ does not affect the output of the experiment since it is performed after the information needed to determine the output is already computed.

Thus, to prove this claim, it suffices to show that

\[
\Pr_{\substack{\Hyb_2}}\left[\exists \, i \in T \, : \, (x_i^* \neq (b_i||r_i)) \wedge (y_i=\com_i)\right] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}}.
\]

Consider adversary $\sB$ that runs steps <ref> through <ref> in $\Hyb_2$, and outputs $\{\com_i\}_{i \in T}, \allowbreak\{b_i||r_i\}_{i \in T}$. Note that $\sB$ does not make any queries to $\simro.\sE$. Now consider the experiment where $\sB$ is run as above, followed by running $y_i \gets \simro.\RO(b_i||r_i)$ for all $i \in T$ and then  $x_i^* \gets \simro.\sE(\com_i)$ for all $i \in T$, and outputting $1$ if $\exists \, i \in T \, : \, (x_i^* \neq (b_i||r_i)) \wedge (\simro.\RO(b_i||r_i)=\com_i)$. Applying the correctness of extraction property of <ref>, and bounding $|T|$ by $n$, we get the required claim.

$|\Pr[\Hyb_3=1] - \Pr[\Hyb_4=1]| \leq  \frac{8qn}{2^{\secp/2}}$

This follows from the almost commutativity of $\simro.\sE$ and $\simro.\RO$ property of <ref>. Indeed, since $\{\com_i\}_{i \in [n]}$ are classical strings output by the experiment after step 2, all subsequent queries to $\simro.\RO$ are independent of $\simro.\sE(\com_i)$ for any $i$, in the sense that they may operate on disjoint input and output registers. Thus, the statistical distance between the two experiments is at most $\frac{8qn}{2^{\secp/2}}$, since there are most $q$ queries to $\simro.\RO$, and $n$ queries to $\simro.\sE$.

$\Pr[\Hyb_4=1] = \Pr[\Hyb_5=1]$

The only change in $\Hyb_5$ is that the variable $\mathsf{out}$ is modified and set to $\mathsf{FAIL}$ when $\mathsf{out} \not\in \{\{b^*_i\}_{i \in T}, \bot\}$. We show that whenever $\out$ is set of $\mathsf{FAIL}$, the event $\mathsf{BAD}$ occurs, which means that the output of the experiment is anyway $\mathsf{BAD}$.

Indeed, in the case of $\mathsf{FAIL}$, we know that $\out$ is not equal to $\bot$ or $\{b_i^*\}_{i \in T}$. Since $\out \neq \bot$, this means that either $\mathsf{BAD}$ occurs, or $y_i = \com_i$ for all $i \in T$. Since $\out \neq \{b_i^*\}_{i \in T}$, there must there exist $i \in T$ such that $x_i^* \neq (b_i||r_i)$. But then if $y_i = \com_i$ for all $i \in T$, the event $\mathsf{BAD}$ also occurs.

We prove this using the following subclaims:

\[
\Pr_{\substack{\Hyb_2}}\left[\exists \, i \in T \, : \, (x_i^* \neq b_i||r_i) \wedge (y_i=\com_i)\right] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}}.
\]

Consider adversary $\sB$ that runs steps <ref> through <ref> in $\Hyb_2$, and outputs $\{\com_i\}_{i \in T}, \{b_i||r_i\}_{i \in T}$. Note that $\sB$ does not make any queries to $\simro.\sE$. Now consider the experiment where $\sB$ is run as above, followed by running $\simro.\sE(\com_i)$ for $i \in T$ to get $\{x_i^*\}_{i \in T}$, and outputting $1$ if $\exists \, i \in T \, : \, (x_i^* \neq b_i||r_i) \wedge (\simro.\RO(b_i||r_i)=\com_i)$. Applying the correctness of extraction property of $\simro$ (property <ref>, <ref>), and bounding $|T|$ by $n$, we get the required claim.

\[
\Pr_{\substack{\Hyb_3}}\left[\exists \, i \in T \, : \, (x_i^* \neq b_i||r_i) \wedge (\simro.\RO(b_i||r_i)=\com_i)\right] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}}
\]

This follows by the almost-commutativity property of $\simro.\RO$ and $\simro.\sE$. In particular, let $\sB^{\simro.\RO}$ be an adversary in $\Hyb_2$ that does the following:

* Run experiment in $\Hyb_2$.

* Output 1 if $\exists \, i \in T \, : \, (x_i^* \neq b_i||r_i) \wedge (\simro.\RO(b_i||r_i) = \com_i)$ and $0$ otherwise.

The statistical distance between the output of $\sB$ when it runs as above in $\Hyb_2$ and when the calls to $\simro.\sE$ are commuted to between steps <ref> and <ref> (exactly as in $\Hyb_3$) is at most $\frac{8qn}{2^{\secp/2}}$, using the almost commuting property of $\simro.\RO$ and $\simro.\sE$ (property <ref>, <ref>). Combining this with <ref>, we get that the probability that $\sB$ outputs $1$ in $\Hyb_3$ is at most $\frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}}$.

In $\Hyb_4$, on step <ref>, $\Pr[\out = \mathsf{FAIL}] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}}$.

We have,

\begin{align}
\Pr[\out = \mathsf{FAIL}] &= \Pr[\out \not \in \{b_i^*\}_{i \in T} \wedge \out \neq \bot] \nonumber\\
&= \Pr\left[\left(\exists i \in T : \, b_i^* \neq b_i \right) \wedge \left( \forall i \in T, \, y_i^{\Rec} = \com_i \right)\right]\nonumber\\
&\leq \Pr\left[\exists i \in T : \, \left(x_i^* \neq b_i||r_i\right) \wedge  \left(y_i^{\Rec} = \com_i\right)\right]\nonumber\\
&= \Pr\left[\exists i \in T : \, \left(x_i^* \neq b_i||r_i\right) \wedge  \left(\simro.\RO(b_i||r_i) = \com_i\right)\right]\label{eq:subcloutfail}\\
&\leq \frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}} \quad (\text{using \cref{subclaim:extComProofCorr1}}) \nonumber
\end{align}

Using $\Hyb_4$, step <ref>, $\Pr[\out = \mathsf{FAIL}] = \Pr[\out \notin \{\{b_i^*\}_{i \in T}, \bot\}] = \Pr[(\out \neq \{b_i^*\}_{i \in T}) \wedge (\out \neq \bot)] \leq \Pr[\out \neq \{b_i^*\}_{i \in T} \, | \, \out \neq \bot] = \Pr[\out \neq \{b_i^*\}_{i \in T} \, | \, \out = \{b_i\}_{i \in T}] = \Pr[\exists \, i \in T \, : \, b_i \neq b_i^*]$.

If $\out \neq \bot$ in step <ref> of $\Hyb_4$, this means (by the checks performed inside $\Rec$), that, $\forall i \in T$, $\simro.\RO(b_i||r_i) = \com_i$. Therefore, by using <ref>, we get,

\begin{align*}
&\Pr[\exists \, i \in T \, : \, (x_i^* \neq b_i||r_i) \wedge (\simro.\RO(b_i||r_i)=\com_i)] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}}\\
\implies& \Pr[\exists \, i \in T \, : \, (x_i^* \neq b_i||r_i) \, | \, (\simro.\RO(b_i||r_i)=\com_i)] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}}\\
\implies& \Pr[\exists \, i \in T \, : \, (x_i^* \neq b_i||r_i) \, | \, \out \neq \bot] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}}\\
\implies& \Pr[\exists \, i \in T \, : \, (b_i \neq b_i^*) \, | \, \out \neq \bot] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}}\\
\implies& \Pr[\out = \mathsf{FAIL} \text{ in step~\ref{step:extComSimHyb4S6} of $\Hyb_4$ }] \leq \frac{296(q+n+1)^3+2}{2^{\secp+1}} + \frac{8qn}{2^{\secp/2}}
\end{align*}

$\Pr[\Hyb_6 = 1] \geq \Pr[\Hyb_5 = 1]$

This follows by observing that the distribution $\Hyb_6$ is identical to $\Hyb_5$ except that it never outputs $\mathsf{BAD}$, and therefore the probability that it outputs $1$ cannot possibly reduce.

Combining all claims, we have that

\begin{equation}
\label{eq:newa}
\Pr[\Hyb_0 = 1] \leq \Pr[\Hyb_6 = 1] + \Bigg(\frac{148(q+n+1)^3+1}{2^{\secp}} + \frac{8qn}{2^{\secp/2}}\Bigg),
\end{equation}

and by a similar argument

\begin{equation*}
\Pr[\Hyb_0 = 0] \leq \Pr[\Hyb_6 = 0] + \Bigg(\frac{148(q+n+1)^3+1}{2^{\secp}} + \frac{8qn}{2^{\secp/2}}\Bigg).
\end{equation*}

Because the output of $\Hyb_0$ and $\Hyb_6$ is a single bit, the equation above implies that

\begin{equation}
\label{eq:newb}
%(1 - \Pr[\Hyb_6 = 1]) \geq (1 - \Pr[\Hyb_0 = 1]) - \Bigg(\frac{148(q+n+1)^3+1}{2^{\secp}} + \frac{8qn}{2^{\secp/2}}\Bigg)$$
\Pr[\Hyb_6 = 1] \leq \Pr[\Hyb_0 = 1] + \Bigg(\frac{148(q+n+1)^3+1}{2^{\secp}} + \frac{8qn}{2^{\secp/2}}\Bigg)
\end{equation}

Combining equations (<ref>) and (<ref>), we have

\begin{equation}
\Big| \Pr[\Hyb_6 = 1] - \Pr[\Hyb_0 = 1] \Big| \leq \Bigg(\frac{148(q+n+1)^3+1}{2^{\secp}} + \frac{8qn}{2^{\secp/2}}\Bigg),
\end{equation}

In addition, by Property <ref> in <ref>, the runtime of $\Sim$ is bounded by a polynomial $s(\secp,q) = O(q^2 + q\cdot n)$. Finally, by the almost commutativity of $\simro.\RO$ and $\simro.\sE$ property of <ref>, it follows that the simulator $\Sim$ is $\nu$-commuting, with $\nu(\secp) = \frac{8}{2^{
\secp/2}}$.

§.§ Equivocality

fig:uccomm-protocol is a $\mu$-equivocal bit commitment scheme with partial opening in the QROM
satisfying Definition <ref>, where $\mu(\secp,q, n) = \frac{2qn^{1/2}}{2^{\secp/2}}$ [When $n = c \lambda$ for some arbitrary fixed constant $c$, then we can define $\mu_c(\secp, q) = \frac{2q(c \secp)^{1/2}}{2^{\secp/2}}$. In all our OT protocols, we will set $n$ in this manner and will assume that $\mu$ is a function of $\lambda, q$.] and where the runtime of the simulator is bounded by $s(\secp,q) = O(q^2 + \poly(\secp))$.

We construct a simulator $\SimEqu = (\SimEqu.\RO,\SimEqu.\Com,\SimEqu.\Open)$ as follows:

* For all $i \in [n]$, sample $c_i \leftarrow \zo^{\secp+1}$.

* $\Sim.\RO$ then works as follows:

* Initialize the compressed oracle based random oracle simulator, $\simroco$, from <ref>. For all $i \in [n]$, sample $r_i \leftarrow \zo^\secp, R^{i}_0, R^{i}_1 \gets \zo^{\secp+1}$. Answer oracle queries of $\Adv_{\RCommit,\secp}$ and $\Adv_{\ROpen,\secp}$ using oracle $\puncrom{H}$ which is defined as follows:

\[
\puncrom{H}(x) =
\begin{cases}
R^{i}_0 & \, \text{if }x = 0||r_i \text{ for some }i \in [n]\\
R^{i}_1 & \, \text{if }x = 1||r_i \text{ for some }i \in [n]\\
\simroco(x) & \, \text{otherwise} \\
\end{cases}
\]

* Answer oracle queries of $\sD_{\secp}$ using $\puncrom{H}_R(x)$, which it defines as follows: $\puncrom{H}_R(x) = {H}(x)$, except for all $ i \in [n],\puncrom{H}_R(b_i||r_i) = c_i$

* Answer all oracle queries of $\Adv.\RCommit$ using oracle

* Initialize the efficient on-the-fly random oracle simulator, $\simro.\RO$, from <ref>. For all $i \in [n]$, sample $r_i \leftarrow \zo^\secp, R^{i}_0, R^{i}_1 \gets \zo^{\secp+1}$.

* Let $\SimEqu.\RO$ answer oracle queries of $\Adv_{\RCommit,\secp}$ and $\Adv_{\ROpen,\secp}$ using the oracle $\puncrom{H}$ which is defined as follows:

\[
\puncrom{H}(x) =
\begin{cases}
R^{i}_0 & \, \text{if }x = 0||r_i \text{ for some }i \in [n]\\
R^{i}_1 & \, \text{if }x = 1||r_i \text{ for some }i \in [n]\\
\simro.\RO(x) & \, \text{otherwise} \\
\end{cases}
\]

In an abuse of notation, we have defined $H^\bot$ using the quantum operation $\simro.\RO$. $H^\bot$ will actually be implemented by issuing a controlled query to $\simro.\RO$ (see discussion on controlled queries in <ref>), controlled on the $x$ in input register $\cX$ not being in the set $\{b||r_i\}_{b \in \{0,1\},i \in [n]}$, and then, for each $i \in [n]$ and $b \in \{0,1\}$, implementing a controlled query to a unitary that maps $\ket{x,y} \to \ket{x,y \oplus R_{b}^i}$, controlled on the input $\cX$ register being $(b||r_i)$.

$\SimEqu.\Com$: To output commitments, for all $i \in [n]$, sample $c_i \leftarrow \zo^{\secp+1}$, set $\com_i = c_i$ and output $\{\com_i\}_{i \in [n]}$.

* $\SimEqu.\Open$: When given input $\{b_i\}_{i \in [n]}$, output $\{b_i,r_i\}_{i \in [n]}$.

* Let $\SimEqu.\RO$ answer oracle queries of $\sD_\secp$ using the oracle $\puncrom{H}_R$ which is defined as follows:

\[
\puncrom{H}_R(x) =
\begin{cases}
c_i & \, \text{if }x = b_i||r_i \text{ for some }i \in [n]\\

\simro.\RO(x) & \, \text{otherwise} \\
\end{cases}
\]

Note that $\puncrom{H}_R$ can be implemented in a similar way as described above.

Consider then the following sequence of hybrids to prove that fig:uccomm-protocol is an equivocal bit commitment scheme in QROM satisfying Definition <ref> (parts in blue are different from previous hybrid):

* $\Hyb_0$: This hybrid outputs the following distribution, which matches the real output distribution in Definition <ref>.

* Sample oracle $H \leftarrow F_{\zo^{\secp+1} \rightarrow \zo^{\secp+1}}$.

* $(\brho_{1}, \{b_i\}_{i \in [n]}) \gets \Adv_{\RCommit,\secp}^{ \  H}$

* $(\state, \{\com_i\}_{i \in [n]}) \gets \Com^{H}(1^\secp, \{b_i\}_{i \in [n]})$

* $\brho_{2} \gets \Adv_{\ROpen,\secp}^{ \  H}(\brho_{1}, \{\com_i\}_{i \in [n]})$

* $\{b_i,r_i\}_{i \in [n]} \gets \Open^{H}(\state,[n])$

* Output $\sD_{\secp}^{  H}(\brho_{2},\{\com_i\}_{i \in [n]}, \{b_i,r_i\}_{i \in [n]})$.

* $\Hyb_1$: This is the same as the previous hybrid except that the randomness used in $\Com$ is sampled at the beginning of the experiments and is used to define a different oracle $\puncrom{H}$. $\puncrom{H}$ is then used to answer queries of $\Adv_{\RCommit,\secp},\allowbreak\Adv_{\ROpen,\secp}$. Concretely, this hybrid outputs the following distribution.

* Sample oracle $H \leftarrow F_{\zo^{\secp+1} \rightarrow \zo^{\secp+1}}$.

* For all $i \in [n]$, sample $r_i \leftarrow \zo^\secp, R^{i}_0,R^{i}_1 \gets \zo^{\secp+1}$ and define oracle $\puncrom{H}$ as:

\[
\puncrom{H}(x) =
\begin{cases}
R^{i}_0 & \, \text{if }x = 0||r_i \text{ for some }i \in [n]\\
R^{i}_1 & \, \text{if }x = 1||r_i \text{ for some }i \in [n]\\
H(x) & \, \text{otherwise}
\end{cases}
\]

* $(\brho_{1},\{b_i\}_{i \in [n]}) \gets \Adv_{\RCommit,\secp}^{ \  \nblue{\puncrom{H}}}$

* $(\state, \{\com_i\}_{i \in [n]}) \gets \Com^{H}(1^\secp, \{b_i\}_{i \in [n]})$

* $\brho_{2} \gets \Adv_{\ROpen,\secp}^{ \  \nblue{\puncrom{H}}}(\brho_{1}, \{\com_i\}_{i \in [n]})$

* Output $\sD_{\secp}^{  H}(\brho_{2},\{\com_i\}_{i \in [n]}, \{b_i,r_i\}_{i \in [n]})$.

* $\Hyb_2$: This is the same as previous hybrid, except that the commitments are sampled as fresh uniformly random string, and another oracle $\puncrom{H}_R$ is defined that is used to answer oracle queries of $\sD_{\secp}$. Concretely, this hybrid outputs the following distribution.

* Sample oracle $H \leftarrow F_{\zo^{\secp+1} \rightarrow \zo^{\secp+1}}$.

* For all $i \in [n]$, sample $r_i \leftarrow \zo^\secp, R^{i}_0,R^{i}_1 \gets \zo^{\secp+1}$ and define oracle $\puncrom{H}$ as:

\[
\puncrom{H}(x) =
\begin{cases}
R^{i}_0 & \, \text{if }x = 0||r_i \text{ for some }i \in [n]\\
R^{i}_1 & \, \text{if }x = 1||r_i \text{ for some }i \in [n]\\
H(x) & \, \text{otherwise}
\end{cases}
\]

* $(\brho_{1},\{b_i\}_{i \in [n]}) \gets \Adv_{\RCommit,\secp}^{ {\puncrom{H}}}$

* For all $i \in [n]$, sample $c_i \gets \zo^{\secp+1}$ and set $\com_i = c_i$.

* $\brho_{2} \gets \Adv_{\ROpen,\secp}^{ {\puncrom{H}}}(\brho_{1}, \{\com_i\}_{i \in [n]})$

* Define oracle $\puncrom{H}_R$ as follows:
\[
\puncrom{H}_R(x) =
\begin{cases}
c_i & \, \text{if }x = b_i||r_i \text{ for some }i \in [n]\\
H(x) & \, \text{otherwise} \\
\end{cases}
\]

* Output $\sD_{\secp}^{  \nblue{\puncrom{H}_R}}(\brho_{2},\{\com_i\}_{i \in [n]}, \{b_i,r_i\}_{i \in [n]})$.

* $\Hyb_3$:

This is the same as previous hybrid, except that the oracle $H$ is replaced by the efficient on-the-fly simulator $\simro.\RO$.

This hybrid distribution is also the simulated output distribution in Definition <ref>.
Concretely, this hybrid outputs the following distribution.

* Initialize on-the-fly simulator $\simro.\RO$.

* For all $i \in [n]$, sample $r_i \leftarrow \zo^\secp, R^{i}_0,R^{i}_1 \gets \zo^{\secp+1}$ and define oracle $\puncrom{H}$ as:

\[
\puncrom{H}(x) =
\begin{cases}
R^{i}_0 & \, \text{if }x = 0||r_i \text{ for some }i \in [n]\\
R^{i}_1 & \, \text{if }x = 1||r_i \text{ for some }i \in [n]\\
\nblue{\simro.\RO(x)} & \, \text{otherwise}
\end{cases}
\]

* $(\brho_{1},\{b_i\}_{i \in [n]}) \gets \Adv_{\RCommit,\secp}^{{\puncrom{H}}}$

* For all $i \in [n]$, sample $c_i \gets \zo^{\secp+1}$, and set $\com_i = c_i$.

* $\brho_{2} \gets \Adv_{\ROpen,\secp}^{ {\puncrom{H}}}(\brho_{1}, \{\com_i\}_{i \in [n]})$

* Define oracle $\puncrom{H}_R$ as follows:
\[
\puncrom{H}_R(x) =
\begin{cases}
c_i & \, \text{if }x = b_i||r_i \text{ for some }i \in [n]\\
\nblue{\simro.\RO}(x) & \, \text{otherwise} \\
\end{cases}
\]

* Output $\sD_{\secp}^{\puncrom{H}_R}(\brho_{2},\{\com_i\}_{i \in [n]}, \{b_i,r_i\}_{i \in [n]})$.

Consider the following indistinguishability claims between the hybrids:

$|\Pr[\Hyb_0=1]-\Pr[\Hyb_1=1]|\leq \frac{2q n^{1/2}}{2^{\secp/2}}$

The two hybrids differ in the way oracle queries of $\Adv_\secp$ are answered. In $\Hyb_1$, queries of $\Adv_{\RCommit,\secp}$ and $\Adv_{\ROpen,\secp}$ are answered using oracle $\puncrom{H}$ instead of $H$ as in $\Hyb_0$.
Assume then for sake of contradiction that there exists some $\Adv = \{\brho_\secp,\Adv_\secp\}_{\secp \in \bbN}$ for which $|\Pr[\Hyb_1=1]-\Pr[\Hyb_0=1]| > \frac{2q^{3/2} n^{1/2}}{2^{\secp/2}}$.
Fix such $\Adv$.

We derive a contradiction by relying on the One-Way to Hiding lemma (Imported Theorem <ref>).
We first define oracle algorithms $\sA,\sB,\sC$.

Our goal after defining these algorithms will be to show $\sC$ succeeds in a particular event with more probability than is allowed by the statement of the lemma, which gives us a contradiction.

$\sA^{O}(H,\{r_i\}_{i \in [n]})$

* $(\brho_{1},\{b_i\}_{i \in [n]}) \gets \Adv_{\RCommit,\secp}^{O}$

* $(\state, \{\com_i\}_{i \in [n]}) \gets \Com^{H}(1^\secp, \{b_i\}_{i \in [n]} ; \{r_i\}_{i \in [n]})$

* $\brho_{2} \gets \Adv_{\ROpen,\secp}^{O}(\brho_{1}, \{\com_i\}_{i \in [n]})$

* $\{b_i,r_i\}_{i \in [n]} \gets \Open^{H}(\state,[n])$

* Output $\sD_{\secp}^{  H}(\brho_{2},\{\com_i\}_{i \in [n]}, \{b_i,r_i\}_{i \in [n]})$.

$\sB^{O}(H,\{r_i\}_{i \in [n]})$ Fix $q \coloneqq q(\lambda)$ non-uniformly as (an upper bound on) the number of oracle queries of $\Adv_\secp$, and thus also $\sA^O$.

Pick $i \leftarrow [q]$, run $\sA^{O}$ until just before the $i^{th}$ query, measure the query register and output the measurement outcome $x$.

read more on expected time simulation; what if we had expected q here?

$\sC^{O}(H,\{r_i\}_{i \in [n]})$ Run $x \gets \sB^{O}(H,\{r_i\}_{i \in [n]})$, parse $x$ as $b||r$, where $|b|=1,|r|=\secp$, and output $r$.

We begin by proving the following claim about $\sB$.