parties run $2+L$ blocks of ${\mathsf{NTCF}}$ evaluations in parallel. In the
end the server gets $2+L$ key-pair-superpositions, and the client gets the
corresponding key pairs. The client names these key pairs as follows:  • The
first key pair is denoted as
$K^{({\text{helper}})}=(x^{({\text{helper}})}_{0},x^{({\text{helper}})}_{1})$,
$x^{({\text{helper}})}_{0}\neq x^{({\text{helper}})}_{1}$. • The remaining
$(1+L)$ key pairs are denoted as $K=(K^{(i)})_{i\in[0,L]}$; for each
$i\in[0,L]$, $K^{(i)}=(x_{0}^{(i)},x_{1}^{(i)})$, $x_{0}^{(i)}\neq
x_{1}^{(i)}$. The honest server holds
${\mathsf{gadget}}(K^{({\text{helper}})})\otimes{\mathsf{gadget}}(K^{(0)})\otimes{\mathsf{gadget}}(K^{(1)})\otimes{\mathsf{gadget}}(K^{(2)})\otimes\cdots{\mathsf{gadget}}(K^{(L)})$
(71) 2. The client randomly chooses to run one of the following two with the
server: • (Standard basis test) The client asks the server to measure all the
gadgets on the standard basis. The server returns the measurement result and
the client checks whether the server’s response has the following form:
$x_{b^{({\text{helper}})}}^{({\text{helper}})}||x_{b^{(0)}}^{(0)}||x_{b^{(1)}}^{(1)}||x_{b^{(2)}}^{(2)}||\cdots||x_{b^{(L)}}^{(L)}$
for some $b^{({\text{helper}})}\in\\{0,1\\}$ and $b^{(i)}\in\\{0,1\\}$ for
each $i\in[0,L]$. If not, the client writes ${\mathsf{fail}}$ in the flag
register. • (Verifiable state preparation) (a) (State transformation with the
helper gadget) For each $i\in[0,L]$, the client samples
$\Theta^{(i)}=(\theta^{(i)}_{0},\theta_{1}^{(i)})\leftarrow_{r}\\{0,1\cdots
7\\}^{2}$. Denote $\Theta=(\Theta^{(i)})_{i\in[0,L]}$. Both parties execute
${\mathsf{AddPhaseWithHelper}}((K^{({\text{helper}})},K),\Theta;1^{\kappa})$,
which consumes the helper gadget. After this step the honest server’s state
is:
${\mathsf{gadget}}(K^{(0)},\Theta^{(0)})\otimes{\mathsf{gadget}}(K^{(1)},\Theta^{(1)})\otimes{\mathsf{gadget}}(K^{(2)},\Theta^{(2)})\otimes\cdots\otimes{\mathsf{gadget}}(K^{(L)},\Theta^{(L)})$
(72) (b) The client randomly chooses to run one of the following five
subprotocols with the server: – (Standard basis test) The client asks the
server to measure all the gadgets on the standard basis. The server returns
the measurement result and the client checks whether the server’s response has
the following form:
$x_{b^{(1)}}^{(0)}||x_{b^{(1)}}^{(1)}||x_{b^{(2)}}^{(2)}||\cdots||x_{b^{(L)}}^{(L)}$
for some $b^{(i)}\in\\{0,1\\}$, for each $i\in[0,L]$. – (Collective phase
test) Both parties execute ${\mathsf{CoPhTest}}(K,\Theta;1^{\kappa})$. –
(Individual phase test) Both parties execute
${\mathsf{InPhTest}}(K,\Theta;1^{\kappa})$. This is considered as the
${\mathsf{quiz}}$ round and the client will possibly write ${\mathsf{win}}$ or
${\mathsf{lose}}$ in the score register. – (Basis norm test) Both parties
execute
${\mathsf{BNTest}}((K^{(i)})_{i\in[L]},(\Theta^{(i)})_{i\in[L]};1^{\kappa})$
on these states. – (Output states) The client reveals $(K^{(i)})_{i\in[L]}$
and the honest server could decode the gadgets and get the following state up
to a global phase:
$\ket{+_{\theta^{(1)}}}\otimes\ket{+_{\theta^{(2)}}}\otimes\cdots\otimes\ket{+_{\theta^{(L)}}}$
where $\theta^{(i)}=\theta^{(i)}_{1}-\theta^{(i)}_{0}$ for each $i\in[L]$. And
the client could also calculate these phases from $\Theta$. All the other
client-side registers are disgarded. This is considered as the
${\mathsf{comp}}$ round. The subprotocols used in this protocol are formalized
below.

##### Add phases under the helper gadget method

Below we formalize the state transformation subprotocol, which guarantees the
honest server could add phases to (71). And this step will use the helper
gadget method.

######  Protocol 3 (${\mathsf{AddPhaseWithHelper}}$).

Suppose the security parameter is $\kappa$. Gadget number is controlled by
$L$. The client holds key tuples
$K^{({\text{helper}})}=(x^{({\text{helper}})}_{0},x_{1}^{({\text{helper}})})$,
$K=(K^{(i)})_{i\in[0,L]}$, $K^{(i)}=(x_{0}^{(i)},x_{1}^{(i)})$ and phase tuple
$\Theta=(\Theta^{(i)})_{i\in[0,L]}$,
$\Theta^{(i)}=(\theta_{0}^{(i)},\theta_{1}^{(i)})$. Honest server holds:
${\mathsf{gadget}}(K^{({\text{helper}})})\otimes{\mathsf{gadget}}(K^{(0)})\otimes{\mathsf{gadget}}(K^{(1)})\otimes{\mathsf{gadget}}(K^{(2)})\otimes\cdots{\mathsf{gadget}}(K^{(L)})$
1. (Add phases) For each $i\in[0,L]$, the client prepares the following table
and sends it to the server:
${\mathsf{LT}}(x_{0}^{({\text{helper}})}x^{(i)}_{0}\rightarrow\theta^{(i)}_{0},x_{1}^{({\text{helper}})}x^{(i)}_{0}\rightarrow\theta^{(i)}_{0},x_{0}^{({\text{helper}})}x^{(i)}_{1}\rightarrow\theta^{(i)}_{1},x_{1}^{({\text{helper}})}x^{(i)}_{1}\rightarrow\theta^{(i)}_{1};1^{\kappa})$
The honest server should do the following mapping for each $i\in[0,L]$ to add
the phases:
$\displaystyle(\ket{x_{0}^{({\text{helper}})}}+\ket{x_{1}^{({\text{helper}})}})\otimes(\ket{x_{0}^{(i)}}+\ket{x_{1}^{(i)}})$
(73) $\displaystyle\rightarrow$
$\displaystyle(\ket{x_{0}^{({\text{helper}})}}+\ket{x_{1}^{({\text{helper}})}})\otimes(\ket{x_{0}^{(i)}}\ket{\theta_{0}^{(i)}}+\ket{x_{1}^{(i)}}\ket{\theta_{1}^{(i)}})$
(74) $\displaystyle\rightarrow$
$\displaystyle(\ket{x_{0}^{({\text{helper}})}}+\ket{x_{1}^{({\text{helper}})}})\otimes(e^{\theta_{0}^{(i)}{\mathrm{i}}\pi/4}\ket{x_{0}^{(i)}}\ket{\theta_{0}^{(i)}}+e^{\theta^{(i)}_{1}{\mathrm{i}}\pi/4}\ket{x_{1}^{(i)}}\ket{\theta_{1}^{(i)}})$
(75) $\displaystyle\rightarrow$
$\displaystyle(\ket{x_{0}^{({\text{helper}})}}+\ket{x_{1}^{({\text{helper}})}})\otimes(e^{\theta_{0}^{(i)}{\mathrm{i}}\pi/4}\ket{x_{0}^{(i)}}+e^{\theta^{(i)}_{1}{\mathrm{i}}\pi/4}\ket{x_{1}^{(i)}})$
(76) 2. Both parties execute
${\mathsf{HadamardTest}}(K^{({\text{helper}})};1^{\kappa})$ (formalized below)
on the helper gadget. An honest server holds the following state in the end:
${\mathsf{gadget}}(K^{(0)},\Theta^{(0)})\otimes{\mathsf{gadget}}(K^{(1)},\Theta^{(1)})\otimes{\mathsf{gadget}}(K^{(2)},\Theta^{(2)})\otimes\cdots\otimes{\mathsf{gadget}}(K^{(L)},\Theta^{(L)})$

Where the Hadamard test with random oracle padding is defined as follows.

###  5.2 Subprotocols: Hadamard Tests and Gadget Combination

##### RO-padded Hadamard test

The Hadamard tests used in our protocols are defined below. For this work, we
need to define different versions of RO-padded Hadamard tests, which deal with
the extra phases in different ways. In each of these tests, the client asks
the server to add an extra random oracle paddings before the Hadamard
operation. As discussed in the introduction and [46], this allows the client
to control the server-side states in a way that the un-padded version could
not give.

  * •

(Unphased Hadamard test) ${\mathsf{HadamardTest}}(K;1^{\kappa})$, where $K$ is
a key pair: this is the most basic form of Hadamard test used in our protocol.
Here the phases are trivial: In this protocol the honest server is suppose to
hold ${\mathsf{gadget}}(K)$ in the beginning. This test has only one-sided
error in the sense that if the honest server could pass with probability $1$
thus if the server fails the cheating behavior will be caught immediately.
This version will be used in the ${\mathsf{AddPhaseWithHelper}}$ and the
${\mathsf{BNTest}}$.

  * •

(Phased Hadamard test) ${\mathsf{HadamardTest}}(K,\Theta;1^{\kappa})$, where
$K$ is a key pair, $\Theta$ is a phase pair: in this version, the honest
server is suppose to hold ${\mathsf{gadget}}(K,\Theta)$ in the beginning. The
client will first reveal the relative phase to allow the server to dephase the
gadget and run the unphased Hadamard test in the previous bullet. This version
will be used in the ${\mathsf{CoPhTest}}$.

  * •

(Extra-phase-biased Hadamard test)
${\mathsf{HadamardTest}}(K,\Theta,\delta;1^{\kappa})$, where $K$ is a key
pair, $\Theta$ is a phase pair, $\delta\in\\{0,4,1\\}$: similar to the
previous bullet, the honest server is suppose to hold
${\mathsf{gadget}}(K,\Theta)$. Different from the previous bullet, when the
client reveals the phase, it adds an _extra-phase-bias_ $\delta$ ($\delta$
itself is hidden from the server): suppose $\Theta=(\theta_{0},\theta_{1})$,
it will reveal $\theta_{1}-\theta_{0}-\delta$. Then corresponding to different
$\delta$, the client will produce results in different ways:

    * –

If $\delta=0$, the honest server will first de-phase the gadget as the last
version and do unphased Hadamard test on ${\mathsf{gadget}}(K)$.

    * –

If $\delta=4$, the dephasing step will give $\ket{x_{0}}-\ket{x_{1}}$ (up to a
global phase, where $K=(x_{0},x_{1})$). Then the unphased Hadamard test on
this state gives opposite ${\mathsf{pass}}/{\mathsf{fail}}$ flag to
$\ket{x_{0}}+\ket{x_{1}}$. Thus for this case the client will reverse the
${\mathsf{pass}}/{\mathsf{fail}}$ from the $\delta=0$ step.

    * –

If $\delta=1$: the dephasing step will give
$\ket{x_{0}}+e^{{\mathrm{i}}\pi/4}\ket{x_{1}}$. Then the server will go
through an unphased Hadamard test from this state (note that $\delta$ is
hidden from the server so the server does not know the state description it
holds). The client will use the equation deciding the
${\mathsf{pass}}/{\mathsf{fail}}$ flags from the unphased version, but it will
only record ${\mathsf{win}}$ or ${\mathsf{lose}}$ for this case.

The honest server could also ${\mathsf{lose}}$ in this test with some
probability, and what we want to guarantee is the winning probability is not
far from the optimal value.

This version will be used in the ${\mathsf{InPhTest}}$.

######  Protocol 4 (${\mathsf{HadamardTest}}(K;1^{\kappa})$, unphased).

Suppose the security parameter is $\kappa$. Client holds a pair of keys
$K=(x_{0},x_{1})$. Honest server should hold state
$\frac{1}{\sqrt{2}}(\ket{x_{0}}+\ket{x_{1}})$. 1. The client samples
${\text{pad}}\leftarrow\\{0,1\\}^{\kappa}$. Send it to the server. 2. The
server is suppose to use the padding to map the state into
$\frac{1}{\sqrt{2}}(\ket{x_{0}}\underbrace{\ket{H({\text{pad}}||x_{0})}}_{\kappa\text{
qubits}}+\ket{x_{1}}\ket{H({\text{pad}}||x_{1})})$ and do Hadamard
measurements on all the qubits above. Suppose the measurement result is
$d\in\\{0,1\\}^{|x|+\kappa}$. $|x|$ is the length of keys in $K$. The server
sends back $d$. 3. The client outputs ${\mathsf{fail}}$ if the last $\kappa$
bits of $d$ are all-zero. Otherwise the client calculates
$d\cdot(x_{0}||H(pad||x_{0}))+d\cdot(x_{1}||H(pad||x_{1}))$ (77) If (77) is
$0$, ${\mathsf{pass}}$; if (77) is $1$, ${\mathsf{fail}}$.

######  Protocol 5 (${\mathsf{HadamardTest}}(K,\Theta;1^{\kappa})$, phased).

Suppose the security parameter is $\kappa$. Client holds a pair of keys
$K=(x_{0},x_{1}),\Theta=(\theta_{0},\theta_{1})$. Honest server should hold
state ${\mathsf{gadget}}(K,\Theta)$. 1. The client reveals the relative phase
$\theta_{1}-\theta_{0}$ to the server. The server could de-phase and get the
state ${\mathsf{gadget}}(K)$ up to a global phase. 2. Both parties run
${\mathsf{HadamardTest}}(K;1^{\kappa})$ on ${\mathsf{gadget}}(K)$.

######  Protocol 6 (${\mathsf{HadamardTest}}(K,\Theta,\delta;1^{\kappa})$, the
Hadamard test with extra phase bias).

Suppose the security parameter is $\kappa$. Client holds a pair of keys
$K=(x_{0},x_{1})$, a pair of phases $\Theta=(\theta_{0},\theta_{1})$, and an
extra phase bias $\delta\in\\{0,4,1\\}$. Honest server should hold state
${\mathsf{gadget}}(K,\Theta)$. 1. The client reveals
$\theta_{1}-\theta_{0}-\delta$ to the server. The honest server could use it
to transform ${\mathsf{gadget}}(K,\Theta)$ to the following state up to a
global phase:
$\frac{1}{\sqrt{2}}(\ket{x_{0}}+e^{\delta{\mathrm{i}}\pi/4}\ket{x_{1}})$ (78)
2. Both parties execute the non-phase-bias Hadamard test
${\mathsf{HadamardTest}}(K;1^{\kappa})$ above, where the server uses (78).
This subprotocol call returns a measurement result $d$ (see (77)) to the
client. The client outputs ${\mathsf{fail}}$ if the last $\kappa$ bits of $d$
are all-zero. Otherwise, depending on the value of $\delta$, the client
determines the output flags and scores as follows: • If $\delta=0$, the client
sets ${\boldsymbol{flag}}={\mathsf{pass}}$ if (77) is $0$ and
${\boldsymbol{flag}}={\mathsf{fail}}$ if (77) is $1$. • If $\delta=4$, the
client sets ${\boldsymbol{flag}}={\mathsf{fail}}$ if (77) is $0$ and
${\boldsymbol{flag}}={\mathsf{pass}}$ if (77) is $1$. • If $\delta=1$, the
client sets ${\boldsymbol{score}}={\mathsf{win}}$ if (77) is $0$ and
${\boldsymbol{score}}={\mathsf{lose}}$ if (77) is $1$. The unspecified flag is
${\mathsf{pass}}$ and the unspecified score is $\perp$ by default.

To formalize the phase test and basis norm test, we will use subprotocols for
combining two gadgets into one single gadget. This is defined as follows.

#####  ${\mathsf{Combine}}$: tools for phase tests and basis norm tests

${\mathsf{Combine}}(K,\Theta,I;1^{\kappa})$ combines multiple gadgets to a
single gadget. Here $I$ is a tuple of indices, which is a subset of $[L]$ or
$[0,L]$ arranged in increasing order. This subprotocol will be used in
${\mathsf{CoPhTest}}$ and ${\mathsf{BNTest}}$ in different ways. Let’s
introduce the following simplified notation:

  * •

In ${\mathsf{CoPhTest}}$, $I=[0,L]$. Correspondingly,
$K=(K^{(i)})_{i\in[0,L]}$, $\Theta=(\Theta^{(i)})_{i\in[0,L]}$. And we simply
write ${\mathsf{Combine}}(K,\Theta;1^{\kappa})$.

  * •

In ${\mathsf{BNTest}}$, $\Theta$ are taken to be all-zero. In this case we
simply write ${\mathsf{Combine}}(\tilde{K},I;1^{\kappa})$. What’s more note
$I$ is a subset of $[L]$ (instead of $[0,L]$) in ${\mathsf{BNTest}}$.
Correspondingly, $\tilde{K}=(K^{(i)})_{i\in[L]}$.

######  Protocol 7 (${\mathsf{Combine}}$ for ${\mathsf{CoPhTest}}$).

Suppose the security parameter is $\kappa$. Client holds a tuple of key pairs
$K=(K^{(i)})_{i\in[0,L]};K^{(i)}=(x_{0}^{(i)},x_{1}^{(i)})$. Correspondingly
it holds a tuple of phase pairs
$\Theta=(\Theta^{(i)})_{i\in[0,L]};\Theta^{(i)}=(\theta_{0}^{(i)},\theta_{1}^{(i)})$.
Each phase is in $\\{0,1\cdots 7\\}$. Honest server should hold
$\otimes_{i\in[0,L]}{\mathsf{gadget}}(K^{(i)},\Theta^{(i)})$ 1. For each
$i\in[L]$: The client samples different
$r_{0}^{(i)},r_{1}^{(i)}\leftarrow\\{0,1\\}^{\kappa}$, prepares the table
${\mathsf{LT}}^{(i)}:={\mathsf{LT}}(x_{0}^{(0)}x^{(i)}_{0}\rightarrow
r_{0}^{(i)},x_{1}^{(0)}x^{(i)}_{1}\rightarrow
r_{0}^{(i)},x_{0}^{(0)}x^{(i)}_{1}\rightarrow
r_{1}^{(i)},x_{1}^{(0)}x^{(i)}_{0}\rightarrow r_{1}^{(i)};1^{\kappa})$ and
sends the table to the server. 2. The client defines
$K^{(combined)}=(x_{0}^{(combined)},x_{1}^{(combined)})$, sets it to be
$K^{(0)}$ in the beginning. And it defines
$\Theta^{(combined)}=(\theta_{0}^{(combined)},\theta_{1}^{(combined)})$, set
it to be $\Theta^{(0)}$ in the beginning. For each $i\in[L]$: (a) If the
server is honest, by this time it should hold
${\mathsf{gadget}}(K^{(combined)},\Theta^{(combined)})$ and
${\mathsf{gadget}}(K^{(i)},\Theta^{(i)})$. The keys in $K^{(combined)}$ have
prefix in $K^{(0)}$. It will combine these two gadgets into a single gadget by
decrypting ${\mathsf{LT}}^{(i)}$ and measures to get
$r^{(i)}\in\\{r_{0}^{(i)},r_{1}^{(i)}\\}$. In more detail, the following
operations are applied by the honest server:
$\displaystyle{\mathsf{gadget}}(K^{(combined)},\Theta^{(combined)})\otimes{\mathsf{gadget}}(K^{(i)},\Theta^{(i)})$
(79) $\displaystyle=$
$\displaystyle\frac{1}{2}(e^{\theta_{0}^{(combined)}{\mathrm{i}}\pi/4}\ket{x_{0}^{(combined)}}+e^{\theta_{1}^{(combined)}{\mathrm{i}}\pi/4}\ket{x_{1}^{(combined)}})\otimes(e^{\theta_{0}^{(i)}{\mathrm{i}}\pi/4}\ket{x_{0}^{(i)}}+e^{\theta_{1}^{(i)}{\mathrm{i}}\pi/4}\ket{x_{1}^{(i)}})$
(80) $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{b^{(combined)}b^{(i)}\in\\{0,1\\}^{2}}e^{\theta_{b^{(combined)}}^{(combined)}+\theta_{b^{(i)}}^{(i)}{\mathrm{i}}\pi/4}\ket{x_{b^{(combined)}}^{(combined)}x_{b^{(i)}}^{(i)}}$
(81) (Decrypt ${\mathsf{LT}}^{(i)}$ with $K^{(0)}$ (in the prefix of
$K^{(combined)}$) and $K^{(i)}$): (82) $\displaystyle\rightarrow$
$\displaystyle\frac{1}{2}\sum_{b^{(combined)}b^{(i)}\in\\{0,1\\}^{2}}e^{\theta_{b^{(combined)}}^{(combined)}+\theta_{b^{(i)}}^{(i)}{\mathrm{i}}\pi/4}\ket{x_{b^{(combined)}}^{(combined)}x_{b^{(i)}}^{(i)}}\ket{r^{(i)}_{b^{(combined)}+b^{(i)}}}$
(83) $\displaystyle\rightarrow$ $\displaystyle\text{measure and get
$r^{(i)}\in\\{r_{0}^{(i)},r_{1}^{(i)}\\}$}:$ (84)
$\displaystyle(r^{(i)}=r_{0}^{(i)}):e^{(\theta_{0}^{(combined)}+\theta_{0}^{(i)}){\mathrm{i}}\pi/4}\ket{x_{0}^{(combined)}x_{0}^{(i)}}+e^{(\theta_{1}^{(combined)}+\theta_{1}^{(i)}){\mathrm{i}}\pi/4}\ket{x_{1}^{(combined)}x_{1}^{(i)}}$
(85)
$\displaystyle(r^{(i)}=r_{1}^{(i)}):e^{(\theta_{0}^{(combined)}+\theta_{1}^{(i)}){\mathrm{i}}\pi/4}\ket{x_{0}^{(combined)}x_{1}^{(i)}}+e^{(\theta_{1}^{(combined)}+\theta_{0}^{(i)}){\mathrm{i}}\pi/4}\ket{x_{1}^{(combined)}x_{0}^{(i)}}$
(86) The server sends back $r^{(i)}$ to the client. (b) The client checks the
server’s response $r^{(i)}$ is in $\\{r_{0}^{(i)},r_{1}^{(i)}\\}$ and stores •
If $r^{(i)}=r_{0}^{(i)}$:
$K^{(combined)}=(x_{0}^{(combined)}x_{0}^{(i)},x_{1}^{(combined)}x_{1}^{(i)}),$
$\Theta^{(combined)}=(\theta_{0}^{(combined)}+\theta_{0}^{(i)},\theta_{1}^{(combined)}+\theta_{1}^{(i)})$
• If $r^{(i)}=r_{1}^{(i)}$:
$K^{(combined)}=(x_{0}^{(combined)}x_{1}^{(i)},x_{1}^{(combined)}x_{0}^{(i)}),$
$\Theta^{(combined)}=(\theta_{0}^{(combined)}+\theta_{1}^{(i)},\theta_{1}^{(combined)}+\theta_{0}^{(i)})$
Correspondingly the honest server’s state is
${\mathsf{gadget}}(K^{(combined)},\Theta^{(combined)})$. Finally the client
holds $K^{(combined)}$, $\Theta^{(combined)}$ and the server holds
${\mathsf{gadget}}(K^{(combined)},\Theta^{(combined)})$.

######  Protocol 8 (${\mathsf{Combine}}$ for ${\mathsf{BNTest}}$).

Suppose the security parameter is $\kappa$. $I$ is a tuple of indices
$i_{1}i_{2}\cdots i_{|I|}$ which is a subset of $[L]$ arranged in increasing
order. Client holds a tuple of key pairs
$\tilde{K}=(K^{(i)})_{i\in[L]};K^{(i)}=(x_{0}^{(i)},x_{1}^{(i)})$. Honest
server should hold $\otimes_{i\in[L]}{\mathsf{gadget}}(K^{(i)})$ 1. For each
$i\in i_{2},i_{3}\cdots i_{|I|}$: The client samples different
$r_{0}^{(i)},r_{1}^{(i)}\leftarrow\\{0,1\\}^{\kappa}$, prepares the table
${\mathsf{LT}}^{(i)}:={\mathsf{LT}}(x_{0}^{(i_{1})}x^{(i)}_{0}\rightarrow
r_{0}^{(i)},x_{1}^{(i_{1})}x^{(i)}_{1}\rightarrow
r_{0}^{(i)},x_{0}^{(i_{1})}x^{(i)}_{1}\rightarrow
r_{1}^{(i)},x_{1}^{(i_{1})}x^{(i)}_{0}\rightarrow r_{1}^{(i)};1^{\kappa})$ and
sends the table to the server. 2. The client defines
$K^{(combined)}=(x_{0}^{(combined)},x_{1}^{(combined)})$, sets it to be
$K^{(i_{1})}$ in the beginning. For each $i\in i_{2},i_{3}\cdots i_{|I|}$: (a)
If the server is honest, by this time it should hold
${\mathsf{gadget}}(K^{(combined)})$ and ${\mathsf{gadget}}(K^{(i)})$. The keys
in $K^{(combined)}$ have prefix in $K^{(i_{1})}$. It will combine these two
gadgets into a single gadget by decrypting ${\mathsf{LT}}^{(i)}$ and measures
to get $r^{(i)}\in\\{r_{0}^{(i)},r_{1}^{(i)}\\}$. In more detail, the
following operations are applied by the honest server:
$\displaystyle{\mathsf{gadget}}(K^{(combined)})\otimes{\mathsf{gadget}}(K^{(i)})$
(88) $\displaystyle=$
$\displaystyle\frac{1}{2}(\ket{x_{0}^{(combined)}}+\ket{x_{1}^{(combined)}})\otimes(\ket{x_{0}^{(i)}}+\ket{x_{1}^{(i)}})$
(89) $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{b^{(combined)}b^{(i)}\in\\{0,1\\}^{2}}\ket{x_{b^{(combined)}}^{(combined)}x_{b^{(i)}}^{(i)}}$
(90) (Decrypt ${\mathsf{LT}}^{(i)}$ with $K^{(i_{1})}$ (in the prefix of
$K^{(combined)}$) and $K^{(i)}$): (91) $\displaystyle\rightarrow$
$\displaystyle\frac{1}{2}\sum_{b^{(combined)}b^{(i)}\in\\{0,1\\}^{2}}\ket{x_{b^{(combined)}}^{(combined)}x_{b^{(i)}}^{(i)}}\ket{r^{(i)}_{b^{(combined)}+b^{(i)}}}$
(92) $\displaystyle\rightarrow$ $\displaystyle\text{measure and get
$r^{(i)}\in\\{r_{0}^{(i)},r_{1}^{(i)}\\}$}:$ (93)
$\displaystyle(r^{(i)}=r_{0}^{(i)}):\ket{x_{0}^{(combined)}x_{0}^{(i)}}+\ket{x_{1}^{(combined)}x_{1}^{(i)}}$
(94)
$\displaystyle(r^{(i)}=r_{1}^{(i)}):\ket{x_{0}^{(combined)}x_{1}^{(i)}}+\ket{x_{1}^{(combined)}x_{0}^{(i)}}$
(95) The server sends back $r^{(i)}$ to the client. (b) The client checks the
server’s response $r^{(i)}$ is in $\\{r_{0}^{(i)},r_{1}^{(i)}\\}$ and stores •
If $r^{(i)}=r_{0}^{(i)}$:
$K^{(combined)}=(x_{0}^{(combined)}x_{0}^{(i)},x_{1}^{(combined)}x_{1}^{(i)}),$
• If $r^{(i)}=r_{1}^{(i)}$:
$K^{(combined)}=(x_{0}^{(combined)}x_{1}^{(i)},x_{1}^{(combined)}x_{0}^{(i)}),$
Correspondingly, the honest server’s state is
${\mathsf{gadget}}(K^{(combined)})$ In the end both parties combine the
gadgets with indices in $I$ into a single gadget and the gadgets with indices
outside $I$ remain unchanged.

###  5.3 Sub-tests

##### Collective Phase Test

The collective phase test is formalized as follows. The input gadgets are
indexed by $[0,L]$. The client first runs ${\mathsf{Combine}}$ to combine all
these $1+L$ gadgets into a single gadget. Then one of the following two are
randomly selected:

  * •

A standard basis test of the combined keys;

  * •

As the main step of this test, the client asks the server to do a Hadamard
test on the combined gadget.

######  Protocol 9 (${\mathsf{CoPhTest}}$).

Suppose the security parameter is $\kappa$ and the gadget number is controlled
by $L$. Client holds the key tuple $K=(K^{(i)})_{i\in[0,L]}$ which contains
$1+L$ key pairs and the phase tuple $\Theta=(\Theta^{(i)})_{i\in[0,L]}$ which
contains $1+L$ phase pairs. Honest server holds:
$\otimes_{i\in[0,L]}{\mathsf{gadget}}(K^{(i)},\Theta^{(i)})$ 1. Both parties
run ${\mathsf{Combine}}(K,\Theta;1^{\kappa})$. The client gets
$K^{(combined)}$ and $\Theta^{(combined)}$ and the server gets
${\mathsf{gadget}}(K^{(combined)},\Theta^{(combined)})$.  2. The client
chooses to run one of the following two randomly: • The client asks the server
to measure all the keys on the computational basis. The client outputs
${\mathsf{fail}}$ if the server’s response is not in $K^{(combined)}$. • Both
parties execute
${\mathsf{HadamardTest}}(K^{(combined)},\Theta^{(combined)};1^{\kappa})$.

##### Individual Phase Test

The individual phase test is defined as follows.

######  Protocol 10 (${\mathsf{InPhTest}}$).

Suppose the security parameter is $\kappa$ and the gadget number is $L$.
Client holds the key tuple $K=(K^{(i)})_{i\in[0,L]}$ which contains $1+L$ key
pairs and the phase tuple $\Theta=(\Theta^{(i)})_{i\in[0,L]}$ which contains
$1+L$ phase pairs. Honest server holds:
$\otimes_{i\in[0,L]}{\mathsf{gadget}}(K^{(i)},\Theta^{(i)})$ This protocol
will only use the first gadget, which corresponds to
${\mathsf{gadget}}(K^{(0)},\Theta^{(0)})$.
$\Theta^{(0)}=(\theta^{(0)}_{0},\theta_{1}^{(0)})$. 1. With probability
$\frac{1}{3}$ each, the client executes the following with the server without
telling the server which is the case: • Both parties execute
${\mathsf{HadamardTest}}(K^{(0)},\Theta^{(0)},0;1^{\kappa})$; • Both parties
execute ${\mathsf{HadamardTest}}(K^{(0)},\Theta^{(0)},4;1^{\kappa})$; • Both
parties execute ${\mathsf{HadamardTest}}(K^{(0)},\Theta^{(0)},1;1^{\kappa})$;
Note “${\mathsf{win}}$” or “${\mathsf{lose}}$” are recorded as the score
corresponding to the client’s checking result.

##### Basis Norm Test

Finally we formalize the basis norm test as follows. The input gadgets are
indexed by $1$ to $L$. The client selects a random subset of index $I$ from
$[L]$, which represents the indices of the gadgets that will be used for the
combine-and-test process; then it uses ${\mathsf{Combine}}$ to combine these
gadgets into a single gadget. Then:

  * •

For the gadgets outside $I$, the client will ask the server to measure them on
the standard basis.

  * •

For the combined gadget:

As the main step of this protocol, with probability $\frac{1}{2}$ the client
will execute a Hadamard test on this combined gadget.

For simplification of security proof, with probability $\frac{1}{2}$, The
client chooses to do a standard basis test on the combined gadget.

######  Protocol 11 (${\mathsf{BNTest}}$).

Suppose the security parameter is $\kappa$ and the gadget number is $L$.
Client holds a tuple of $L$ key pairs $\tilde{K}=(K^{(i)})_{i\in[L]}$ and a
tuple of $L$ phase pairs $(\Theta^{(i)})_{i\in[L]}$. Honest server holds:
${\mathsf{gadget}}(K^{(1)},\Theta^{(1)})\otimes{\mathsf{gadget}}(K^{(2)},\Theta^{(2)})\otimes\cdots\otimes{\mathsf{gadget}}(K^{(L)},\Theta^{(L)})$
(97) 1. The client reveals $\Theta^{(1)},\Theta^{(2)}\cdots\Theta^{(L)}$ and
the server could remove the phases from (72) and get
${\mathsf{gadget}}(K^{(1)})\otimes{\mathsf{gadget}}(K^{(2)})\otimes\cdots{\mathsf{gadget}}(K^{(L)})$
2. Both parties execute ${\mathsf{BNTest}}((K^{(i)})_{i\in[L]};1^{\kappa})$
defined below.

######  Protocol 12 (${\mathsf{BNTest}}$).

Suppose the security parameter is $\kappa$ and the gadget number is $L$.
Client holds the key tuple $\tilde{K}=(K^{(i)})_{i\in[L]}$ which is a tuple of
$L$ key pairs. Honest server holds:
${\mathsf{gadget}}(K^{(1)})\otimes{\mathsf{gadget}}(K^{(2)})\otimes\cdots\otimes{\mathsf{gadget}}(K^{(L)})$
(98) 1. The client samples a random subset of index $I\subseteq[L]$. Both
parties execute ${\mathsf{Combine}}(K,I;1^{\kappa})$. This combines the
gadgets with superscripts in $I$ into a single gadget. The client gets
$K^{(combined)}$ and the server gets ${\mathsf{gadget}}(K^{(combined)})$. The
gadgets with superscript in $[L]-I$ do not change. 2. The client asks the
server to measure all the gadgets excluding
${\mathsf{gadget}}(K^{(combined)})$ and send back the result (denoted as
$rp^{(i)}$ for $i\in[L]-I$). The client checks $rp^{(i)}\in K^{(i)}$ for all
$i\in[L]-I$, and rejects if it’s not satisfied. 3. The client chooses one of
the following two randomly: • The client asks the server to measure
$K^{(combined)}$ on the computational basis and send back the result. The
client checks the server’s response is within $K^{(combined)}$. • Both parties
execute ${\mathsf{HadamardTest}}(K^{(combined)};1^{\kappa})$ on the combined
gadget.

So far we have completed the formalization of our pre-RSPV protocol. Below we
give the correctness, efficiency and verifiability, which corresponds to
Definition 4.4, 4.5.

###  5.4 Properties of Our ${\mathsf{preRSPV}}$ Protocol

Protocol 2 has the following properties.

##### Round type probability

The round type is chosen from
$\\{{\mathsf{test}},{\mathsf{quiz}},{\mathsf{comp}}\\}$ with probability
$(\frac{4}{5},\frac{1}{10},\frac{1}{10})$ each. Denote them as
$p_{{\mathsf{test}}},p_{{\mathsf{quiz}}},p_{{\mathsf{comp}}}$.

##### Correctness

The protocol in the honest settings prepares the target state

$\ket{+_{\theta^{(1)}}}\otimes\ket{+_{\theta^{(2)}}}\otimes\cdots\otimes\ket{+_{\theta^{(L)}}}$

in the ${\mathsf{comp}}$ round. The client gets
$\theta^{(1)}\theta^{(2)}\cdots\theta^{(L)}\in_{r}\\{0,1\cdots 7\\}^{L}$. More
formally, this protocol has correctness formalized in Definition 4.4.

##### Winning Probability

The winning probability in the quiz round in the honest setting is

${\text{OPT}}=\frac{1}{3}|\frac{1}{2}+\frac{1}{2}e^{{\mathrm{i}}\pi/4}|^{2}=\frac{1}{3}\cos^{2}(\pi/8)=0.28451779686\cdots$

where the first $1/3$ comes from the fact that in the extra-biased Hadamard
test, if the extra phase bias $\delta\in\\{0,4\\}$ the protocol does not
generate ${\mathsf{win}}/{\mathsf{lose}}$ output.

##### Efficiency

The complexity of both parties is $O({\mathsf{poly}}(\kappa)|C|)$.

##### Optimality of OPT

######  Theorem 5.1.

OPT is optimal with error tolerance $(10^{-2000},10^{-220})$ (as formalized in
Definition 4.6).

For the verifiability we have:

##### Verifiability

######  Theorem 5.2.

As formalized in Definition 4.5, Protocol 2 has verifiability with error
tolerance $(10^{-2000},10^{-200})$.

We prove Theorem 5.1 and 5.2 in Section 12.

##  6 Basic Notions and Analysis of Key-Pair Preparation and Standard Basis
Test

In this section we develop tools for analyzing the part of Protocol 2 before
the verifiable state preparation step.

First, in Section 6.1 we give symbols for registers that appear in the
protocols. Then we get a clearer set-up for later proofs.

Then in Section 6.2 we will give some basic notions for characterizing the
state’s properties. They include the _efficiently preparable_ , _key
checkable_ and _claw-free_ properties, which are basically reviews or re-
formalizations of existing notions; and we define the _strong-claw-free_ to
characterize the uncorrelated claw-freeness of multiple key pairs. These
notions will also be the basis of later proofs. Then we analyze the first step
of Protocol 2, the parallel application of ${\mathsf{NTCF}}$. We will show the
output state of this step satisfies the properties above.

Then in Section 6.3 we give the notion of _semi-honest form_ , which means the
server holds exactly one key from each key pair that the client holds. We also
define the _branch_ of semi-honest form formally, which will be useful in
later proofs.

In Section 6.4 we analyze the properties of standard basis test. Note that the
standard basis test is not only used as a branch in the body of
${\mathsf{preRSPV}}$ protocol (Protocol 2); it is also used in subprotocols
like ${\mathsf{BNTest}}$, ${\mathsf{CoPhTest}}$. We will show the ability of
passing the standard basis test with high probability implies the state is
approximately isometric to a semi-honest form via a server-side isometry.

###  6.1 Symbols for Different Registers

By the time of the completion of step $1$ in Protocol 2, the registers
include:

  * •

The client-side key registers: denoted by
${\boldsymbol{K}}^{({\text{helper}})}=({\boldsymbol{x}}_{0}^{({\text{helper}})},{\boldsymbol{x}}_{1}^{({\text{helper}})}),{\boldsymbol{K}}=({\boldsymbol{K}}^{(i)})_{i\in[0,L]}$,
${\boldsymbol{K}}^{(i)}=({\boldsymbol{x}}_{0}^{(i)},{\boldsymbol{x}}_{1}^{(i)})$.

When the security parameter is $\kappa$, the size of each
${\boldsymbol{x}}_{b}^{(i)}$ register is $\kappa$.

For each $i\in\\{{\text{helper}},[0,L]\\}$, define
${\text{Domain}}({\boldsymbol{K}}^{(i)})$ as
$\\{(x_{0},x_{1}):x_{0}\in\\{0,1\\}^{\kappa},x_{1}\in\\{0,1\\}^{\kappa},x_{0}\neq
x_{1}\\}$.

As a convention, we use $\tilde{\boldsymbol{K}}$ to denote
$({\boldsymbol{K}}^{(i)})_{i\in[L]}$.

  * •

The transcript registers hold the server’s response in the first step, which
is denoted by $y^{({\text{helper}})}y^{(0)}\cdots y^{(L)}$ in the protocol;
denote the corresponding registers by
${\boldsymbol{Y}}=({\boldsymbol{Y}}^{({\text{helper}})},{\boldsymbol{Y}}^{(0)},{\boldsymbol{Y}}^{(1)},\cdots{\boldsymbol{Y}}^{(L)})$.

  * •

The client-side phase registers: although these phases are not sampled and
used in the protocol until the step (a) of the verifiable state preparation
step, we could assume the client has already sampled them out in advance.
These information is stored in registers
${\boldsymbol{\Theta}}=({\boldsymbol{\Theta}}^{(i)})_{i\in[0,L]}$.
${\boldsymbol{\Theta}}^{(i)}=({\boldsymbol{\theta}}_{0}^{(i)},{\boldsymbol{\theta}}_{1}^{(i)})$.
The domain of each ${\boldsymbol{\theta}}$ register is $\\{0,1\cdots 7\\}$.

  * •

The server’s registers. In general these registers are denoted by symbol
${\boldsymbol{S}}$; but there are indeed many different registers appeared in
different steps of the protocol. We will use superscripts to refer to these
different registers. Especially, denote the registers that holds the
${\mathsf{gadget}}(K^{(i)})$ in (71) in the honest setting as
${\boldsymbol{S}}_{smh}^{(i)}$. Denote
${\boldsymbol{S}}_{smh}=({\boldsymbol{S}}_{smh}^{(i)})_{i\in[0,L]}$.

  * •

The random oracle registers that store the random oracle outputs for each
input.

###  6.2 Basic Notions and the ${\mathsf{NTCF}}$ Evaluation Step

######  Definition 6.1 (Efficiently preparable states, repeated).

We say a purified joint state $\ket{\varphi}$ is efficiently-preparable if
there exists a polynomial time operator (which could include projections) $O$
such that $\ket{\varphi}=O\ket{0}$.

######  Definition 6.2 (Key-checkable).

Suppose ${\boldsymbol{x}}$ is a client-side register that holds a key. We say
a purified joint state $\ket{\varphi}$ is key-checkable for ${\boldsymbol{x}}$
if there exists an efficient server-side operation777In general this server-
side operation is implemented with the help of transcript register
${\boldsymbol{Y}}$ in our proofs. that implements
$\Pi^{{\boldsymbol{S}}}_{={\boldsymbol{x}}}$ on $\ket{\varphi}$ where
${\boldsymbol{S}}$ is an arbitrary server-side register,
$\Pi^{{\boldsymbol{S}}}_{={\boldsymbol{x}}}$ denotes the projection onto the
space that the content of ${\boldsymbol{S}}$ is equal to the content of
${\boldsymbol{x}}$.

Suppose the client holds a tuple of keys in registers ${\boldsymbol{K}}$. We
say a purified joint state $\ket{\varphi}$ is key-checkable for
${\boldsymbol{K}}$ if for any single key register ${\boldsymbol{x}}$ within
${\boldsymbol{K}}$, $\ket{\varphi}$ is key-checkable for ${\boldsymbol{x}}$.

Then we review the notion of claw-freeness.

######  Definition 6.3 (Claw-free [10]).

Suppose the client holds a key pair in register
${\boldsymbol{K}}=({\boldsymbol{x}}_{0},{\boldsymbol{x}}_{1})$. We say a
purified joint state $\ket{\varphi}$ is claw-free for ${\boldsymbol{K}}$
against adversary family ${\mathcal{F}}$ if for any adversary
${\mathsf{Adv}}\in{\mathcal{F}}$, for an arbitrary server-side register
${\boldsymbol{S}}$,

$|\Pi_{={\boldsymbol{x}}_{0}||{\boldsymbol{x}}_{1}}^{{\boldsymbol{S}}}{\mathsf{Adv}}\ket{\varphi}|\leq{\mathsf{negl}}(\kappa)$

where $\Pi^{{\boldsymbol{S}}}_{={\boldsymbol{x}}_{0}||{\boldsymbol{x}}_{1}}$
is a projection onto the subspace that the content of ${\boldsymbol{S}}$ is
equal to the content of ${\boldsymbol{x}}_{0}||{\boldsymbol{x}}_{1}$.

We omit ${\mathcal{F}}$ when it is taken to be the set of polynomial time
server-side operations.

And we further generalize it to the multi key pair setting:

######  Definition 6.4 (Strongly claw-free).

Suppose the client holds a tuple of key pairs in register
${\boldsymbol{K}}=({\boldsymbol{K}}^{(i)})_{i\in[L]}$ where
${\boldsymbol{K}}^{(i)}=({\boldsymbol{x}}_{0}^{(i)},{\boldsymbol{x}}_{1}^{(i)})$.
We say a purified joint state $\ket{\varphi}$ is strongly-claw-free for any
key pair in ${\boldsymbol{K}}$ if for any $i\in[L]$,
$\ket{\varphi}\odot({\boldsymbol{K}}-{\boldsymbol{K}}^{(i)})$ is claw-free for
${\boldsymbol{K}}^{(i)}$, where
$\ket{\varphi}\odot({\boldsymbol{K}}-{\boldsymbol{K}}^{(i)})$ means starting
from $\ket{\varphi}$ the client sends all the keys except the $i$-th key pair
to the server.

Then we have the following theorem which characterizes the properties of
output states from the first step of Protocol 2 (a parallel ${\mathsf{NTCF}}$
evaluation).

######  Theorem 6.1.

For any polynomial time adversary ${\mathsf{Adv}}$, denote the output state of
the first step of Protocol 2 as $\ket{\varphi^{1}}$. Then registers described
in Section 6.1 are initialized, and $\ket{\varphi^{1}}$ is:

  * •

efficiently preparable;

  * •

key checkable for both ${\boldsymbol{K}}^{({\text{helper}})}$ and
${\boldsymbol{K}}$;

  * •

strongly-claw-free for any key pair in
$({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}})$.

Note that we will interchangeably use
$({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}})$ or
$({\boldsymbol{K}}^{(i)})_{i\in\\{{\text{helper}},[0,L]\\}}$ to denote this
tuple of $2+L$ output key pairs.

###### Proof.

The efficiently preparable property comes from the efficiency of
${\mathsf{Adv}}$ and the protocol and key-checkable property comes from the
correctness of ${\mathsf{NTCF}}$. We only need to prove the strong claw-
freeness.

If this is not true, there will be an index $i\in({\text{helper}})\cup[0,L]$
such that an efficient operation $D$ can output both keys in
${\boldsymbol{K}}^{(i)}$ given the other keys. Then we can construct an
adversary that break the claw-free property of ${\mathsf{NTCF}}$:

  1. 1.

Instead of interacting with the client, the server simulates all the other
${\mathsf{NTCF}}$ evaluations on its own excluding the $i$-th evaluation. In
the simulated state the server has access to
$(({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}})-{\boldsymbol{K}}^{(i)})$
since the client-side key registers for this part are simulated. Denote the
simulated state as $\ket{\varphi}$.

  2. 2.

Then by the assumption $D$ applied on
$\ket{\varphi}\odot(({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}})-{\boldsymbol{K}}^{(i)})$
outputs both keys in ${\boldsymbol{K}}^{(i)}$. This contradicts the claw-free
property of ${\mathsf{NTCF}}$.

∎

Now we are ready to formalize a set-up that abstracts the property of the
output state of the first step of Protocol 2. In the remaining proofs we could
only refer to this set-up instead of applying Theorem 6.1 again and again.

######  Set-up 1.

We use ${\text{SETUP}}^{1}$ to denote the set of states that satisfy:

  * •

The parties are as described in Section 4.1.

  * •

The registers are as described in Section 6.1.

  * •

The state is efficiently preparable;

  * •

The state is key checkable for each key in
$({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}})$;

  * •

The state is strongly-claw-free for each key pair in
$({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}})$.

###  6.3 Semi-honest Form

We will define the semi-honest form as below. Recall that in the honest
setting, the client holds a tuple of keys, and the server holds superpositions
of keys. In the malicious setting, if the server also holds keys in
superpositions (which are possibly entangled with some auxiliary registers
since it’s malicious), we call this form the semi-honest form.

Let’s first introduce a convenient notation.

######  Notation 6.1 (Key vector and subscript vector).

Suppose the client holds a tuple of key pairs $\tilde{K}=(K^{(i)})_{i\in[L]}$,
$K^{(i)}=(x_{0}^{(i)},x_{1}^{(i)}),i\in[L]$. For subscript vector
$\vec{b}\in\\{0,1\\}^{L}$, denote

$\vec{x}_{\vec{b}}=x^{(1)}_{b^{(1)}}x^{(2)}_{b^{(2)}}\cdots x^{(L)}_{b^{(L)}}$

as the key vector of $\tilde{K}$ under subscript vector $\vec{b}$, which is
the concatenation of one key from each key tuple, with subscripts coming from
coordinates of $\vec{b}$.

If the superscripts of keys start from $0$, the subscript vector will be
$\vec{b}\in\\{0,1\\}^{1+L}$, and the key vector is defined correspondingly as
$x^{(0)}_{b^{(0)}}x^{(1)}_{b^{(1)}}x^{(2)}_{b^{(2)}}\cdots x^{(L)}_{b^{(L)}}$.

######  Definition 6.5 (Semi-honest form).

Suppose the client holds a tuple of key pairs in registers ${\boldsymbol{K}}$,
and correspondingly the server holds register ${\boldsymbol{S}}_{smh}$.
(Recall Setup 1.)

We say a purified joint state $\ket{\varphi}$ is in a semi-honest form of
${\boldsymbol{K}}$ if it has the form

$\ket{\varphi}=\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\underbrace{\ket{K}}_{\text{client-
side
}{\boldsymbol{K}}}\otimes\sum_{\vec{b}\in\\{0,1\\}^{1+L}}\underbrace{\ket{\vec{x}_{\vec{b}}}}_{\text{server-
side
}{\boldsymbol{S}}_{smh}}\underbrace{\ket{\varphi_{K,\vec{b}}}}_{\text{remaining
registers}}$ (99)

where $\vec{x}_{\vec{b}}$ is a key vector of ${\boldsymbol{K}}$.

We define $\Pi_{{\text{semihonest}}}$ as the projection onto the subspace that
the content of ${\boldsymbol{S}}_{smh}$ is a valid key vector of
${\boldsymbol{K}}$.

Correspondingly, when we focus on key tuple
$\tilde{\boldsymbol{K}}=({\boldsymbol{K}}^{(i)})_{i\in[L]}$, the semi-honest
form is defined to be the state where the server holds a key vector of
$(K^{(i)})_{i\in[L]}$.

And we define the semi-honest form of a specific key pair
${\boldsymbol{K}}^{(i)}=({\boldsymbol{x}}_{0}^{(i)},{\boldsymbol{x}}_{1}^{(i)})$
to be the state in the form of

$\ket{\varphi}=\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\underbrace{\ket{K}}_{\text{client-
side
}{\boldsymbol{K}}}\otimes\sum_{b\in\\{0,1\\}}\underbrace{\ket{x^{(i)}_{b}}}_{\text{server-
side
}{\boldsymbol{S}}_{smh}^{(i)}}\underbrace{\ket{\varphi_{K,b}}}_{\text{remaining
registers}}$ (100)

And we use $\Pi_{{\text{semihonest}}({\boldsymbol{K}}^{(i)})}$ to denote the
projection onto the space that ${\boldsymbol{S}}_{smh}^{(i)}$ is a valid key
of ${\boldsymbol{K}}^{(i)}$.

######  Definition 6.6 (Approximate semi-honest form).

If $|(\mathbb{I}-\Pi_{{\text{semihonest}}})\ket{\varphi}|\leq\epsilon$, we say
$\ket{\varphi}$ is in an $\epsilon$-semi-honest form of ${\boldsymbol{K}}$.

######  Definition 6.7 (Branch of semi-honest form).

Suppose $\ket{\varphi}$ is in a semi-honest form of ${\boldsymbol{K}}^{(i)}$
for some $i$, as shown in (100). For each $b\in\\{0,1\\}$, we call

$\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\underbrace{\ket{K}}_{\text{client}}\otimes\underbrace{\ket{x^{(i)}_{b}}}_{{\boldsymbol{S}}_{smh}^{(i)}}\ket{\varphi_{K,b}}$

the ${\boldsymbol{x}}^{(i)}_{b}$-branch of this state.

Suppose $\ket{\varphi}$ is in a semi-honest form of ${\boldsymbol{K}}$ as
shown in (99). For each $\vec{b}\in\\{0,1\\}$, we call

$\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\underbrace{\ket{K}}_{\text{client}}\otimes\underbrace{\ket{\vec{x}_{\vec{b}}}}_{{\boldsymbol{S}}_{smh}}\ket{\varphi_{K,\vec{b}}}$

the $\vec{{\boldsymbol{x}}}_{\vec{b}}$-branch of this state.

Note when we replace ${\boldsymbol{K}}=({\boldsymbol{K}}^{(i)})_{i\in[0,L]}$
by $\tilde{\boldsymbol{K}}=({\boldsymbol{K}}^{(i)})_{i\in[L]}$ or
$({\boldsymbol{K}}^{(i)})_{i\in\\{{\text{helper}},[0,L]\\}}$, the definition
could be adapted correspondingly.

One useful lemma is the collapsing property, which is used in different forms
in many previous works [38, 31]:

######  Lemma 6.2.

Suppose a subnormalized state $\ket{\varphi}$ is in Setup 1, and is in the
semi-honest form of ${\boldsymbol{K}}^{(0)}$. Then for any efficient server-
side operation $O$ that output a single bit in a register ${\boldsymbol{S}}$:

$|\Pi_{0}^{{\boldsymbol{S}}}O\ket{\varphi}|^{2}\approx_{{\mathsf{negl}}(\kappa)}|\Pi_{0}^{{\boldsymbol{S}}}O\Pi^{{\boldsymbol{S}}_{smh}^{(0)}}_{{\boldsymbol{x}}^{(0)}_{0}}\ket{\varphi}|^{2}+|\Pi_{0}^{{\boldsymbol{S}}}O\Pi^{{\boldsymbol{S}}_{smh}^{(0)}}_{{\boldsymbol{x}}^{(0)}_{1}}\ket{\varphi}|^{2}$

Finally we give a lemma that formalizes the following intuition. If a semi-
honest form state is claw-free for ${\boldsymbol{K}}^{(i)}$, if we only
consider one branch, for example, ${\boldsymbol{x}}^{(i)}_{0}$-branch, since
the server already knows the value of $x^{(i)}_{0}$, it won’t be able to
predict $x^{(i)}_{1}$ by the claw-freeness. This is still true even if the
server additionally gets polynomial number of ciphertexts encrypted under
${\boldsymbol{x}}_{1-b}^{(i)}$. Formally, we have the following lemma, which
will be useful later.

######  Lemma 6.3.

Suppose a purified joint state $\ket{\varphi}$ satisfies Setup 1 and is in a
semi-honest form of ${\boldsymbol{K}}$ with only the
${\boldsymbol{x}}^{(i)}_{b}$-branch. $(p_{pre}^{(t)})_{t\in[N]}$,
$(p_{post}^{(i)})_{t\in[N]}$ are both a tuple of strings in
$\\{0,1\\}^{\kappa}$. Define ${\mathsf{AuxInf}}$ as the following algorithm
that generates a tuple of salted hash values of
${\boldsymbol{x}}_{1-b}^{(i)}$:

$\forall
t\in[N]:(R^{(t)},H(R^{(t)}||p_{pre}^{(t)}||{\boldsymbol{x}}_{1-b}^{(i)}||p_{post}^{(t)})),R^{(t)}\leftarrow_{r}\\{0,1\\}^{\kappa}$

Then suppose $H^{\prime}$ is the blinded oracle where
$\\{0,1\\}^{2\kappa}||{\boldsymbol{x}}^{(i)}_{1-b}||\cdots$ are blinded. For
any efficient adversary ${\mathsf{Adv}}$, denote ${\mathsf{Adv}}^{\prime}$ as
the operation that each query in ${\mathsf{Adv}}$ is replaced by a query to
$H^{\prime}$. Then

${\mathsf{Adv}}(\ket{\varphi}\odot\llbracket{\mathsf{AuxInf}}\rrbracket)\approx_{{\mathsf{negl}}(\kappa)}{\mathsf{Adv}}^{\prime}(\ket{\varphi}\odot\llbracket{\mathsf{AuxInf}}\rrbracket)$

We put the proof in Appendix B.

###  6.4 Analysis of Standard Basis Test

Below we analyze the implications of the standard basis test. We have the
following lemma, which allows us to analyze the structure of state on the
server side assuming it can pass the standard basis test:

######  Theorem 6.4.

Suppose the client holds a tuple of key pairs in register
${\boldsymbol{K}}=({\boldsymbol{K}}^{(i)})_{i\in[L]}$. Suppose an efficient
adversary ${\mathsf{Adv}}$, operated on a normalized purified joint state
$\ket{\varphi}$, could pass the standard basis test with probability $p$. Then
there exists an efficient server-side operation $O$ such that $O\ket{\varphi}$
is in a $\sqrt{1-p}$-semi-honest form.

###### Proof.

Run the adversary’s operation but do not do the final measurement. Swap the
state in the response register to ${\boldsymbol{S}}_{smh}$ (See Definition
6.5). The fact that it passes the standard basis test with failure probability
$1-p$ implies the state on subspace $\mathbb{I}-\Pi_{{\text{semihonest}}}$ has
norm at most $\sqrt{1-p}$. ∎

We show a useful lemma that will be used for multiple times in later proofs.
It says, if a state is in a semi-honest form, if the adversary transforms it
to another semi-honest form, each of the outcome branch should only come from
the corresponding input branch:

######  Lemma 6.5.

Consider a normalized purified joint state $\ket{\varphi}$ in Setup 1. Use
${\boldsymbol{S}}_{smh}$ to denote the server-side system that holds the key
vectors in the semi-honest form definition. Use
$\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}$ to denote
the projection onto $\vec{{\boldsymbol{x}}}_{\vec{b}}$-branch (Definition
6.7). Then for any efficient server-side operation $D$ there is

$\Pi_{{\text{semihonest}}}D\Pi_{{\text{semihonest}}}\ket{\varphi}\approx_{{\mathsf{negl}}(\kappa)}\sum_{\vec{b}\in\\{0,1\\}^{L}}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}D\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}\ket{\varphi}$
(101)

###### Proof.

First suppose ${\boldsymbol{S}}_{smh}$ consists of registers
${\boldsymbol{S}}_{smh}^{(1)}{\boldsymbol{S}}^{(2)}_{smh}\cdots{\boldsymbol{S}}^{(L)}_{smh}$
where each ${\boldsymbol{S}}_{smh}^{(i)}$ stores a key in
${\boldsymbol{K}}^{(i)}$ in the semi-honest form.

$\forall i\in[L]$ define:

$\ket{\varphi^{i}}=\sum_{b^{(1)}\cdots
b^{(i)}\in\\{0,1\\}^{i}}\Pi_{b^{(1)}\cdots b^{(i)}}D\Pi_{b^{(1)}\cdots
b^{(i)}}\ket{\varphi}$

where $\Pi_{b^{(1)}\cdots b^{(i)}}$ denotes the projection onto the space that
the content of
${{\boldsymbol{S}}_{smh}^{(1)}{\boldsymbol{S}}^{(2)}_{smh}\cdots{\boldsymbol{S}}^{(i)}_{smh}}$
is equal to the content of
${\boldsymbol{x}}_{b^{(1)}}^{(1)}{\boldsymbol{x}}_{b^{(2)}}^{(2)}\cdots{\boldsymbol{x}}_{b^{(i)}}^{(i)}$.

Additionally define

$\ket{\varphi^{0}}=\Pi_{{\text{semihonest}}}D\Pi_{{\text{semihonest}}}\ket{\varphi}$

To prove (146) we only need to prove:

$\forall
i\in[L],\ket{\varphi^{i}}\approx_{{\mathsf{negl}}(\kappa)}\ket{\varphi^{i-1}}$
(102)

The observation is, although $\ket{\varphi^{i-1}},\ket{\varphi^{i}}$ are
written as linear sums, there exists an efficient operation that exactly
prepares this state from $\ket{\varphi}$. Recall $\ket{\varphi}$ has the form
shown in (99). Let’s give an operation that transforms it to
$\ket{\varphi^{i-1}}$ or $\ket{\varphi^{i}}$.

Initialize server-side auxiliary registers
${\boldsymbol{A}}^{(1)}\cdots{\boldsymbol{A}}^{(i)}$, and define the following
operations:

  * •

Define ${\sf COPY}_{1\sim i}$ as the operation that copies (bit-wise ${\sf
CNOT}$) the contents of
${\boldsymbol{S}}_{smh}^{(1)}\cdots{\boldsymbol{S}}_{smh}^{(i)}$ to registers
${\boldsymbol{A}}^{(1)}\cdots{\boldsymbol{A}}^{(i)}$. Define ${\sf COPY}_{i}$
as the operator that only copies ${\boldsymbol{S}}_{smh}^{(i)}$ to
${\boldsymbol{A}}^{(i)}$. Note for any subscript ${\sf COPY}^{\dagger}={\sf
COPY}$.

  * •

Define
$\Pi_{{\boldsymbol{S}}_{smh}^{(1)}\cdots{\boldsymbol{S}}_{smh}^{(i)}={\boldsymbol{A}}^{(1)}\cdots{\boldsymbol{A}}^{(i)}}$
as the operator that projects onto the space that the contents of
${\boldsymbol{S}}_{smh}^{(1)}\cdots{\boldsymbol{S}}_{smh}^{(i)}$ are equal to
${\boldsymbol{A}}^{(1)}\cdots{\boldsymbol{A}}^{(i)}$. Define
$\Pi_{{\boldsymbol{S}}_{smh}^{(i)}={\boldsymbol{A}}^{(i)}}$ as the operator
that projects onto the space that ${\boldsymbol{S}}_{smh}^{(i)}$ is equal to
${\boldsymbol{A}}^{(i)}$.

Then:

$\ket{\varphi^{i}}={\sf COPY}_{1\sim
i}\circ\Pi_{{\boldsymbol{S}}_{smh}^{(1)}\cdots{\boldsymbol{S}}_{smh}^{(i)}={\boldsymbol{A}}^{(1)}\cdots{\boldsymbol{A}}^{(i)}}D\circ{\sf
COPY}_{1\sim i}\circ\Pi_{{\text{semihonest}}}\ket{\varphi}$
$\ket{\varphi^{i-1}}={\sf COPY}_{1\sim
i-1}\circ\Pi_{{\boldsymbol{S}}_{smh}^{(1)}\cdots{\boldsymbol{S}}_{smh}^{(i-1)}={\boldsymbol{A}}^{(1)}\cdots{\boldsymbol{A}}^{(i-1)}}D\circ{\sf
COPY}_{1\sim i-1}\circ\Pi_{{\text{semihonest}}}\ket{\varphi}$

Define ${\mathcal{P}}={\sf COPY}_{1\sim
i-1}\circ\Pi_{{\boldsymbol{S}}_{smh}^{(1)}\cdots{\boldsymbol{S}}_{smh}^{(i-1)}={\boldsymbol{A}}^{(1)}\cdots{\boldsymbol{A}}^{(i-1)}}D\circ{\sf
COPY}_{1\sim i-1}$. Then (102) is reduced to proving

$\Pi_{{\text{semihonest}}}{\mathcal{P}}\Pi_{{\text{semihonest}}}\ket{\varphi}\approx_{{\mathsf{negl}}(\kappa)}\Pi_{{\text{semihonest}}}{\sf
COPY}_{i}\circ\Pi_{{\boldsymbol{S}}_{smh}^{(i)}={\boldsymbol{A}}^{(i)}}\circ{\mathcal{P}}\circ{\sf
COPY}_{i}\Pi_{{\text{semihonest}}}\ket{\varphi}$ (103)

Denote $\Pi_{{\boldsymbol{x}}_{b}^{(i)}}^{{\boldsymbol{S}}_{smh}}$ as the
operator that projects onto the ${\boldsymbol{x}}_{b}^{(i)}$-branch of the
semi-honest form. Then the left hand side of (103) is

$\Pi_{{\text{semihonest}}}{\mathcal{P}}\Pi_{{\text{semihonest}}}\ket{\varphi}=\sum_{b,b^{\prime}\in\\{0,1\\}^{2}}\Pi_{{\text{semihonest}}}\Pi_{{\boldsymbol{x}}_{b^{\prime}}^{(i)}}^{{\boldsymbol{S}}_{smh}}{\mathcal{P}}\Pi_{{\boldsymbol{x}}_{b}^{(i)}}^{{\boldsymbol{S}}_{smh}}\Pi_{{\text{semihonest}}}\ket{\varphi}$

and the right hand side of (103) is

$\sum_{b\in\\{0,1\\}}\Pi_{{\text{semihonest}}}\Pi_{{\boldsymbol{x}}_{b}^{(i)}}^{{\boldsymbol{S}}_{smh}}{\mathcal{P}}\Pi_{{\boldsymbol{x}}_{b}^{(i)}}^{{\boldsymbol{S}}_{smh}}\Pi_{{\text{semihonest}}}\ket{\varphi}$

then (103) is further reduced to

$\sum_{b,b^{\prime}\in\\{0,1\\}^{2},b\neq
b^{\prime}}\Pi_{{\boldsymbol{x}}^{(i)}_{b^{\prime}}}^{{\boldsymbol{S}}_{smh}}\circ{\mathcal{P}}\circ\Pi_{{\boldsymbol{x}}^{(i)}_{b}}^{{\boldsymbol{S}}_{smh}}\Pi_{{\text{semihonest}}}\ket{\varphi}\approx_{{\mathsf{negl}}(\kappa)}0$
(104)

which holds by the claw-free property of $\ket{\varphi}$.∎

##  7 The Helper Gadget Method

In this section we analyze the helper gadget method and how it affects the
state transformation step. We have discussed the helper gadget method briefly
in the introduction, and below we will give a deeper overview, and discuss its
formal analysis. The formal lemma that supports the helper gadget method is a
lemma about the Hadamard test with random oracle paddings, which is given and
proved in Section 7.2. Then in Section 7.3 we analyze the implications of the
helper gadget method in ${\mathsf{preRSPV}}$ protocol.

###  7.1 Overview

As discussed in the introduction, in the helper gadget method we design
protocols that go as follows:

  1. 1.

Encode a mapping onto a helper gadget;

  2. 2.

Do a Hadamard test (Protocol 6) on the helper gadget. This destroys the helper
gadget.

The helper gadget is used as a “switch” that controls whether the adversary
could make use of the mapping. With the helper gadget, the honest server could
implement the mapping; the problem is how to characterize the adversaries’
view, assuming it wants to pass the Hadamard test with high probability.

##### An intuitive discussion on Hadamard test

We need to formalize the intuition that

_$K$ is a key pair, and the initial state is claw-free for $K$. If the server
wants to pass the RO-padded Hadamard test for $K$, it loses the keys after the
test._

As [46] pointed out, passing the RO-padded Hadamard test implies the server
could not do powerful things about $K$ from the post-test state. However the
lemmas given in [46] are not suitable for our purpose here. Here we give a
lemma that captures the properties of RO-padded Hadamard test in terms of
_blinded oracle_. Our analysis of the RO-padded Hadamard test could also be of
independent interest elsewhere.

Suppose the Hadamard test is on key pair $K^{({\text{helper}})}$ and initial
state $\ket{\varphi}$. Suppose the post-test state is
$\ket{\varphi^{\prime}}$. To formalize the intuition above, we consider a
_blinded oracle_ $H^{\prime}$ where the entries in the form of
$\\{0,1\\}^{\kappa}||K^{({\text{helper}})}||\cdots$ are blinded. Then we will
show, informally, if the test passes with high probability:

_Starting from $\ket{\varphi^{\prime}}$, for any efficient adversary, querying
$H$ and querying $H^{\prime}$ should end up with similar states._

More formally, for any efficient operator $D$ on the post-test state, define
$D^{\prime}$ as the blinded version of $D$ where all the random oracle queries
in $D$ are replaced by queries to $H^{\prime}$, there is (where $p$ is the
failing probability of the Hadamard test):

$D^{\prime}\ket{\varphi^{\prime}}\approx_{O(\sqrt{p})+{\mathsf{negl}}(\kappa)}D\ket{\varphi^{\prime}}$
(105)

We note (105) captures and strengthens the intuition above: If the server
could still predict a key in $K$ from the post-test state, it can query the
oracle with this key and make two sides of (105) quite different.

We will see this lemma gives what we want for arguing about the helper gadget
method: the ciphertexts under our lookup tables are encrypted under
$\\{0,1\\}^{\kappa}||K^{({\text{helper}})}||\cdots$; thus applying this lemma
makes this part of the oracle blinded, which means the “switch” for decrypting
the ciphertexts has been turned off.

The formal theorem is given below.

###  7.2 Analysis of Hadamard Test with Random Oracle Paddings

We first formalize the set-up of the theorem as follows.

######  Set-up 2.

Suppose the parties are formalized in Section 4.1. Suppose the client holds a
key pair in register
${\boldsymbol{K}}=({\boldsymbol{x}}_{0},{\boldsymbol{x}}_{1})$. Define
${\text{SETUP}}^{2}({\boldsymbol{K}})$ as the set of purified joint states
that are

  * •

efficiently preparable;

  * •

key checkable for ${\boldsymbol{K}}$;

  * •

claw-free for ${\boldsymbol{K}}$.

In addition, a transcript register ${\boldsymbol{d}}$ is initialized, whose
length is equal to the length of keys in ${\boldsymbol{K}}$ plus $\kappa$.

Note the ${\boldsymbol{K}}$ is a key pair (that will be chosen to be different
key pairs in our later proofs) instead of the ${\boldsymbol{K}}$ in the Setup
1.

######  Theorem 7.1.

Suppose the client holds a key pair in register
${\boldsymbol{K}}^{({\text{helper}})}$. Suppose a normalized purified joint
state
$\ket{\varphi}\in{\text{SETUP}}^{2}({\boldsymbol{K}}^{({\text{helper}})})$ is
in the $\epsilon$-semi-honest form of ${\boldsymbol{K}}^{({\text{helper}})}$.
For any polynomial time adversary ${\mathsf{Adv}}$, denote the post-execution
state of the RO-padded Hadamard test as

$\ket{\varphi^{\prime}}={\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{({\text{helper}})};1^{\kappa})\ket{\varphi}$

Then at least one of the following two is true:

  * •

(Small passing probability)

$|\Pi_{{\mathsf{pass}}}\ket{\varphi^{\prime}}|^{2}\leq 1-p$

  * •

(RO hiding) Suppose $H^{\prime}$ is the blinded oracle where the entries
$\\{0,1\\}^{\kappa}||{\boldsymbol{K}}^{({\text{helper}})}||\cdots$ are
blinded. For any efficient operation $D$, suppose $D^{\prime}$ is the blinded
version of $D$ where all the oracle queries are replaced by queries to
$H^{\prime}$. Then

$D^{\prime}\ket{\varphi^{\prime}}\approx_{8\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}D\ket{\varphi^{\prime}}$
(106)

To prove this theorem, we use the following lemmas, whose proofs are given in
Appendix C.

We first introduce the following notations which explicitly describe the
passing/failing and winning/losing conditions of these Hadamard test. Below we
will use these notations to describe the output of Hadamard test.

######  Notation 7.1.

Suppose the client holds a key pair in register
${\boldsymbol{K}}=({\boldsymbol{x}}_{0},{\boldsymbol{x}}_{1})$. Suppose a
normalized purified joint state
$\ket{\varphi}\in{\text{SETUP}}^{2}({\boldsymbol{K}})$. Recall that in
${\mathsf{HadamardTest}}$ the client first sample a random padding in
$\\{0,1\\}^{\kappa}$, denote the register storing it as ${\boldsymbol{pad}}$.
Define the following operators on system ${\boldsymbol{d}}$ (introduced in
${\text{SETUP}}^{2}$):

  * •

$\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}$ denotes the projection onto the
space that the values of client side registers
${\boldsymbol{x}}_{0},{\boldsymbol{x}}_{1}$, the transcript register
${\boldsymbol{d}}$, ${\boldsymbol{pad}}$, and the random oracle register
satisfy: the result of calculation of (77) is $0$:

${\boldsymbol{d}}\cdot({\boldsymbol{x}}_{0}||\underbrace{H({\boldsymbol{pad}}||{\boldsymbol{x}}_{0})}_{\text{$\kappa$
bits}})+{\boldsymbol{d}}\cdot({\boldsymbol{x}}_{1}||H({\boldsymbol{pad}}||{\boldsymbol{x}}_{1}))=0$

  * •

$\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}$ is defined similarly.

  * •

$\Pi_{=0}^{\text{last $\kappa$ bits of }{\boldsymbol{d}}}$ is the projection
onto the space that the last $\kappa$ bits of ${\boldsymbol{d}}$ is all zero.
And $\Pi_{\neq 0}^{\text{last $\kappa$ bits of }{\boldsymbol{d}}}$ is defined
as its complement. Note this is one of the client’s checking in
${\mathsf{HadamardTest}}$.

The following lemma studies the output property of ${\mathsf{HadamardTest}}$
on a single branch:

######  Lemma 7.2.

Suppose the client holds a key pair in register
${\boldsymbol{K}}=({\boldsymbol{x}}_{0},{\boldsymbol{x}}_{1})$. Suppose a
normalized purified joint state
$\ket{\varphi}\in{\text{SETUP}}^{2}({\boldsymbol{K}})$ and is in the semi-
honest form of ${\boldsymbol{K}}$ with only ${\boldsymbol{x}}_{0}$ branch.
Then for any efficient adversary ${\mathsf{Adv}}$ there is

$|\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq 0}^{\text{last $\kappa$
bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi}|\approx_{{\mathsf{negl}}(\kappa)}\frac{1}{\sqrt{2}}|\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi}|$
$|\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq 0}^{\text{last $\kappa$
bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi}|\approx_{{\mathsf{negl}}(\kappa)}\frac{1}{\sqrt{2}}|\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi}|$

Then we have the following corollary (proved in Appendix C), which studies the
relations of two branches if a state could pass the ${\mathsf{HadamardTest}}$:

######  Corollary 7.3.

Suppose the client holds a key pair in register
${\boldsymbol{K}}=({\boldsymbol{x}}_{0},{\boldsymbol{x}}_{1})$. Suppose a
normalized purified joint state
$\ket{\varphi}\in{\text{SETUP}}^{2}({\boldsymbol{K}})$ and is in an
$\epsilon$-semi-honest form of ${\boldsymbol{K}}$. Denote the
${\boldsymbol{x}}_{0}$-branch as $\ket{\varphi_{0}}$ and
${\boldsymbol{x}}_{1}$-branch as $\ket{\varphi_{1}}$. If an efficient
adversary ${\mathsf{Adv}}$ could make the client output ${\mathsf{pass}}$ in
the Hadamard test (Protocol 4) from initial state $\ket{\varphi}$ with
probability $\geq 1-p$, then

$\displaystyle\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi_{0}}$
$\displaystyle\approx_{\sqrt{2(p+2\epsilon)}+{\mathsf{negl}}(\kappa)}$
$\displaystyle\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi_{1}}$
(107) $\Pi_{=0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi_{0}}\approx_{\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}0,$
$\Pi_{=0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi_{1}}\approx_{\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}0$
(108) $\displaystyle\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi_{0}}$
$\displaystyle\approx_{\sqrt{p+\epsilon}+{\mathsf{negl}}(\kappa)}$
$\displaystyle-\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}};1^{\kappa})\ket{\varphi_{1}}$
(109)

Now we give the proof of Theorem 7.1 with this lemma.

###### Proof of Theorem 7.1.

Suppose $|\Pi_{{\mathsf{pass}}}\ket{\varphi^{\prime}}|^{2}\geq 1-p$. Denote
the ${\boldsymbol{x}}_{0}$-branch of $\ket{\varphi}$ as $\ket{\varphi_{0}}$
and ${\boldsymbol{x}}_{1}$-branch of $\ket{\varphi}$ as $\ket{\varphi_{1}}$.
Then $\ket{\varphi}=\ket{\varphi_{0}}+\ket{\varphi_{1}}$. Define the
corresponding output term:

$\ket{\varphi^{\prime}_{0}}={\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{({\text{helper}})};1^{\kappa})\ket{\varphi_{0}}$
$\ket{\varphi^{\prime}_{1}}={\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{({\text{helper}})};1^{\kappa})\ket{\varphi_{1}}$

Then
$\ket{\varphi^{\prime}}=\ket{\varphi^{\prime}_{0}}+\ket{\varphi_{1}^{\prime}}$.

We will blind the oracle in two steps.

  1. 1.

Define $H^{mid}$ as the blinded oracle where the entries
$\\{0,1\\}^{\kappa}||{\boldsymbol{x}}_{0}^{({\text{helper}})}||\cdots$ are
blinded. Define $D^{mid}$ as the adversary where all the random oracle queries
in $D$ are replaced by queries to $H^{mid}$. And our goal is to prove

$D^{mid}\ket{\varphi^{\prime}}\approx_{4\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}D\ket{\varphi^{\prime}}$
(110)

The reason is as follows.

We will first analyze the effect of replacing $D$ by $D^{mid}$ on
$\ket{\varphi^{\prime}_{1}}$. Intuitively $\ket{\varphi_{1}}$ is the
${\boldsymbol{x}}_{1}$-branch, the server could not predict
${\boldsymbol{x}}_{0}$ by claw-freeness thus the blinding operation on
${\boldsymbol{x}}_{0}$-related entries will not be detected. Formally
speaking, the following is implied by Lemma 6.3:

$D^{mid}\ket{\varphi^{\prime}_{1}}\approx_{{\mathsf{negl}}(\kappa)}D\ket{\varphi^{\prime}_{1}}$
(111)

since the ${\boldsymbol{d}}$ register, after generated in the Hadamard test,
is read-only, this implies both sides of (111) are still close if a projection
on a subset of possible values of ${\boldsymbol{d}}$ is applied. Concretely:

$D^{mid}\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq 0}^{\text{last
$\kappa$ bits of
}{\boldsymbol{d}}}\ket{\varphi^{\prime}_{1}}\approx_{{\mathsf{negl}}(\kappa)}D\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of }{\boldsymbol{d}}}\ket{\varphi^{\prime}_{1}},$
(112) $D^{mid}\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}\ket{\varphi^{\prime}_{1}}\approx_{{\mathsf{negl}}(\kappa)}D\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of }{\boldsymbol{d}}}\ket{\varphi^{\prime}_{1}}$
(113)

Now we use properties of the Hadamard test to argue about the
$\ket{\varphi^{\prime}_{0}}$ branch. By Corollary 7.3 we have

$\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq 0}^{\text{last $\kappa$
bits of
}{\boldsymbol{d}}}\ket{\varphi_{0}^{\prime}}\approx_{\sqrt{2(p+2\epsilon)}+{\mathsf{negl}}(\kappa)}\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of }{\boldsymbol{d}}}\ket{\varphi_{1}^{\prime}}$
(114) $\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq 0}^{\text{last
$\kappa$ bits of
}{\boldsymbol{d}}}\ket{\varphi_{0}^{\prime}}\approx_{\sqrt{p+\epsilon}+{\mathsf{negl}}(\kappa)}-\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of }{\boldsymbol{d}}}\ket{\varphi_{1}^{\prime}}$
(115)

which together with (112) (113) implies

$D^{mid}\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq 0}^{\text{last
$\kappa$ bits of
}{\boldsymbol{d}}}\ket{\varphi^{\prime}_{0}}\approx_{\sqrt{2(p+2\epsilon)}+{\mathsf{negl}}(\kappa)}D\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of }{\boldsymbol{d}}}\ket{\varphi^{\prime}_{0}},$
(116) $D^{mid}\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}\ket{\varphi^{\prime}_{0}}\approx_{\sqrt{p+\epsilon}+{\mathsf{negl}}(\kappa)}D\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of }{\boldsymbol{d}}}\ket{\varphi^{\prime}_{0}}$
(117)

which together with (108) implies

$D^{mid}\ket{\varphi^{\prime}_{0}}\approx_{4\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}D\ket{\varphi^{\prime}_{0}}$
(118)

which together with (111) implies (110).

  2. 2.

Now we hide the ${\boldsymbol{x}}_{1}^{({\text{helper}})}$ part using similar
techniques. Consider $H^{\prime}$ as the blinded oracle of $H^{mid}$ where the
entries $\\{0,1\\}^{\kappa}||{\boldsymbol{x}}_{1}^{({\text{helper}})}||\cdots$
are blinded. Then $H^{\prime}$ could also be seen as a blinded version of $H$
where $\\{0,1\\}^{\kappa}||{\boldsymbol{K}}^{({\text{helper}})}||\cdots$ are
blinded. Correspondingly, $D^{\prime}$ is defined to be: in $D^{mid}$ all the
queries to $H^{mid}$ are replaced by queries to $H^{\prime}$. Then
$D^{\prime}$ is also the blinded version of $D$ where all the queries to $H$
are replaced by queries to $H^{\prime}$. Our goal is to prove

$D^{\prime}\ket{\varphi^{\prime}}\approx_{4\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}D^{mid}\ket{\varphi^{\prime}}$
(119)

Here we will start with the ${\boldsymbol{x}}_{0}$ branch of
$\ket{\varphi^{\prime}}$. By Lemma 6.3 there is

$D^{\prime}\ket{\varphi^{\prime}_{0}}\approx_{{\mathsf{negl}}(\kappa)}D^{mid}\ket{\varphi^{\prime}_{0}}$
(120)

Then arguments (112)-(118) hold after all the appearances of $D$ in them are
replaced by $D^{\prime}$, $\ket{\varphi_{0}^{\prime}}$ are replaced by
$\ket{\varphi_{1}^{\prime}}$ and $\ket{\varphi_{1}^{\prime}}$ are replaced by
$\ket{\varphi_{0}^{\prime}}$. Thus we get

$D^{mid}\ket{\varphi^{\prime}_{1}}\approx_{4\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}D^{\prime}\ket{\varphi^{\prime}_{1}}$
(121)

Combining it with (120) completes the proof of (119).

Now combining (110)(119) completes the proof. ∎

###  7.3 Helper Gadget Method in ${\mathsf{preRSPV}}$

Now we return to the ${\mathsf{preRSPV}}$ protocol and see how the helper
gadget method is used to argue about the security.

We will consider the post-execution state after the
${\mathsf{AddPhaseWithHelper}}$ protocol. Denote this post-execution state as
$\ket{\varphi^{2.a}}$. Denote the remaining steps in ${\mathsf{preRSPV}}$
(after ${\mathsf{AddPhaseWithHelper}}$ completes) as ${\mathsf{preRSPV}}_{\geq
2.b}$. Denote the part of adversary in ${\mathsf{Adv}}$ for
${\mathsf{preRSPV}}_{\geq 2.b}$ as ${\mathsf{Adv}}_{\geq 2.b}$. We will use
Theorem 7.1 to show ${\mathsf{Adv}}_{\geq 2.b}$ and the blinded version of
${\mathsf{Adv}}_{\geq 2.b}$, when applied on $\ket{\varphi^{2.a}}$, is
approximately close to each other.

######  Theorem 7.4.

Suppose a normalized purified joint state $\ket{\varphi}\in{\text{SETUP}}^{1}$
and is in an $\epsilon$-semi-honest form for ${\boldsymbol{K}}$. For any
polynomial-time adversary ${\mathsf{Adv}}$, suppose the state after the state
preparation is $\ket{\varphi^{2.a}}$:

$\ket{\varphi^{2.a}}={\mathsf{AddPhaseWithHelper}}^{{\mathsf{Adv}}_{2.a}}(({\boldsymbol{K}}^{(i)})_{i\in({\text{helper}})\cup[0,L]},{\boldsymbol{\Theta}};1^{\kappa})\ket{\varphi}$

where ${\mathsf{Adv}}_{2.a}$ is the part of adversary in ${\mathsf{Adv}}$ in
the ${\mathsf{AddPhaseWithHelper}}$ step. Suppose

$|\Pi_{{\mathsf{pass}}}\ket{\varphi^{2.a}}|^{2}\geq 1-p$ (122)

Use $H^{\prime}$ to denote the blinded version of $H$ where the entries
$\\{0,1\\}^{\kappa}||{\boldsymbol{K}}^{({\text{helper}})}||\cdots$ are
blinded. Denote ${\mathsf{Adv}}_{\geq 2.b}^{blind}$ as the adversary which
replaces all the oracle queries in ${\mathsf{Adv}}_{\geq 2.b}$ by queries to
$H^{\prime}$. Then we have

${\mathsf{preRSPV}}_{\geq 2.b}^{{\mathsf{Adv}}_{\geq
2.b}}\ket{\varphi^{2.a}}\approx_{8\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}{\mathsf{preRSPV}}_{\geq
2.b}^{{\mathsf{Adv}}_{\geq 2.b}^{blind}}\ket{\varphi^{2.a}}$ (123)

The difference of this theorem from Theorem 7.4 is the client might send
additional messages to the server. Notice that the client-side messages in
${\mathsf{preRSPV}}_{\geq 2.b}$ will not take
${\boldsymbol{K}}^{({\text{helper}})}$ as inputs, we are able to reduce this
theorem to Theorem 7.1 by constructing an adversary that simulates these
messages:

###### Proof.

Note that in each step of ${\mathsf{preRSPV}}_{\geq 2.b}$, the client’s
messages are output of some algorithms which take
$({\boldsymbol{K}}^{(i)})_{i\in[0,L]}$ and ${\boldsymbol{\Theta}}$ as inputs,
and ${\boldsymbol{K}}^{({\text{helper}})}$ is not used any more. Consider an
adversary ${\mathsf{Adv}}_{\geq 2.b}$ that violates (123). We can construct an
adversary for breaking Theorem 7.1 as follows:

  1. 0.

The initial state is

$\ket{\varphi}\odot({\boldsymbol{K}}^{(i)})_{i\in[0,L]}\odot{\boldsymbol{\Theta}}\odot\llbracket{\mathsf{AddPhaseWithHelper}}_{1}(({\boldsymbol{K}}^{(i)})_{i\in({\text{helper}})\cup[0,L]},{\boldsymbol{\Theta}};1^{\kappa})\rrbracket$
(124)

where ${\mathsf{AddPhaseWithHelper}}_{1}$ is the first step in
${\mathsf{AddPhaseWithHelper}}$ (where the client sends lookup tables that
encode the phases).

By Lemma 6.3 we know (124) is claw-free for
${\boldsymbol{K}}^{({\text{helper}})}$.

  2. 1.

The adversary goes through the Hadamard test with the client.

  3. 2.

The adversary simulates all the client side messages in
${\mathsf{preRSPV}}_{\geq 2.b}$ using $({\boldsymbol{K}}^{(i)})_{i\in[0,L]}$
and ${\boldsymbol{\Theta}}$;

  4. 3.

Run ${\mathsf{Adv}}_{\geq 2.b}$ with the simulated messages.

(124) satisfies the conditions required in Theorem 7.1. Since (122) holds we
know the first case in Theorem 7.1 is not true. Then the violation of (123)
implies a violation of the second case in Theorem 7.1, where $D$, $D^{\prime}$
in Theorem 7.1 translate to:

  * •

$D$ corresponds to ${\mathsf{Adv}}_{\geq 2.b}$ run on the simulated messages.

  * •

$D^{\prime}$ corresponds to ${\mathsf{Adv}}_{\geq 2.b}^{blind}$ on simulated
messages.

This completes the proof.∎

##### Implications for later proofs

The implication of Theorem 7.4 is, in the protocol analysis later, we can
first use this theorem to replace the adversary by an adversary that only
queries the blinded oracle. Especially, the lookup tables used in
${\mathsf{AddPhaseWithHelper}}$ are encrypted under the helper keys, making
this part of the oracle blinded implies the tables seem completely random in
the adversary’s view.

###  7.4 Set-up for The Output State of ${\mathsf{AddPhaseWithHelper}}$

In this section we formalize a set-up that captures the basic properties of
the output states of ${\mathsf{AddPhaseWithHelper}}$.

######  Set-up 3.

${\text{SETUP}}^{3}$ is defined as the set of states that could be expressed
as

${\mathsf{AddPhaseWithHelper}}^{\mathsf{Adv}}({\boldsymbol{K}},{\boldsymbol{\Theta}};1^{\kappa})\ket{\varphi^{1}},$
(125)

where ${\mathsf{Adv}}$ is efficient, $\ket{\varphi^{1}}\in{\text{SETUP}}^{1}$.

Accompanied with Setup 3, we introduce the following symbols for registers and
describe the property of states in Setup 3:

######  Notation 7.2.

We introduce the following notations that describe the transcript registers
initialized in the first step of ${\mathsf{AddPhaseWithHelper}}$:

The client-side messages in the first step of ${\mathsf{AddPhaseWithHelper}}$
contain ciphertexts that encrypt $\theta^{(i)}_{b}$ under
$x^{({\text{helper}})}_{b^{({\text{helper}})}}$ for each
$i\in[0,L],b\in\\{0,1\\},b^{({\text{helper}})}\in\\{0,1\\}$. In the protocol
it is denote as

$x^{({\text{helper}})}_{b^{({\text{helper}})}}||x_{b}^{(i)}\rightarrow\theta_{b}^{(i)}$
(126)

Recall in Definition 3.7, 3.6, the ciphertext part of (126) is defined as

$R^{(i)}_{b^{({\text{helper}})},b},H(R^{(i)}_{b^{({\text{helper}})},b}||x^{({\text{helper}})}_{b^{({\text{helper}})}}||x_{b}^{(i)})+\theta_{b}^{(i)}$
(127)

where $R^{(i)}_{b^{({\text{helper}})},b}$ is uniformly sampled from
$\\{0,1\\}^{\kappa}$.

Denote the registers in (127) by
${\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b},{\boldsymbol{ct}}^{(i)}_{b^{({\text{helper}})},b}$
correspondingly. Then related registers for (127) are:

$\underbrace{{\boldsymbol{x}}^{({\text{helper}})}_{b^{({\text{helper}})}},{\boldsymbol{x}}^{(i)}_{b},{\boldsymbol{\theta}}_{b}^{(i)}}_{\text{client}},\underbrace{{\boldsymbol{H}}({\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b}||{\boldsymbol{x}}^{({\text{helper}})}_{b^{({\text{helper}})}}||{\boldsymbol{x}}^{(i)}_{b})}_{\text{random
oracle}},\underbrace{{\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b},{\boldsymbol{ct}}_{b^{({\text{helper}})},b}^{(i)}}_{\text{transcript}}$
(128)

and there is (recall Notation 3.2):

${\boldsymbol{ct}}^{(i)}_{b^{({\text{helper}})},b}={\boldsymbol{H}}({\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b}||{\boldsymbol{x}}^{({\text{helper}})}_{b^{({\text{helper}})}}||{\boldsymbol{x}}^{(i)}_{b})+{\boldsymbol{\theta}}_{b}^{(i)}$
(129)

######  Fact 10.

For any state in ${\text{SETUP}}^{3}$, for any $i\in[0,L]$, $b\in\\{0,1\\}$,
$b^{({\text{helper}})}\in\\{0,1\\}$, there are registers shown in (128) and
their values satisfy (129).

We also introduce the following blinded oracle that accompanied Setup 3:

######  Notation 7.3.

Under Setup 3, define $H^{\prime}$ as the blinded oracle where
$\\{0,1\\}^{\kappa}||{\boldsymbol{K}}^{({\text{helper}})}||\cdots$ are
blinded. Define ${\mathcal{F}}_{blind}$ as the set of server-side operators
that could only query this blinded oracle.

##  8 Analysis of ${\mathsf{AddPhaseWithHelper}}$

Starting from this section, we will move towards the security proof by
analyzing each subprotocol. As described in the introduction, we will prove
the joint state of the client and the server remain indistinguishable under a
series of randomization operators.

In this section, we will focus on what the ${\mathsf{AddPhaseWithHelper}}$
protocol itself could tell us. The analysis will be based on the structure of
phase tables. Recall that the phase tables have the following structure for
each row:

$x^{({\text{helper}})}_{b^{({\text{helper}})}}||x^{(i)}_{b}\rightarrow\theta^{(i)}_{b};\quad
i\in[0,L],b^{({\text{helper}})},b\in\\{0,1\\}$ (130)

Intuitively, the theorems that we prove in this section is based on the
following intuition:

_If the server does not hold $x_{b}^{(i)}$, it could not decrypt (130), thus
$\theta^{(i)}_{b}$ remains secure._

Or in other words:

_If the server does not hold $x_{b}^{(i)}$, the joint state after a
randomization of ${\boldsymbol{\theta}}_{b}^{(i)}$ should be indistinguishable
from the original state._

The condition “the server does not hold $x_{b}^{(i)}$” could come by assuming
the initial state is semi-honest and considering only the
${\boldsymbol{x}}^{(i)}_{1-b}$-branch.

Formalizing this intuition leads to the randomization operator
${\mathcal{R}}_{1}$.

Recall that an intuitive introduction of the ${\mathcal{R}}_{1}$ operator is
given in Example 2.1. Considering the $x_{0}$-branch, if we omit the unused
registers, Equation (46) in the example becomes

$\ket{\Delta_{1}}\ket{\theta_{1}}\ket{x_{0}}\rightarrow\ket{\theta_{1}}\ket{\Delta_{1}}\ket{x_{0}}$
(131)

Under Setup 3, considering the ${\boldsymbol{x}}^{(0)}_{0}$-branch as the
example, (131) becomes

$\ket{\Delta_{1}^{(0)}}\underbrace{\ket{\theta_{1}^{(0)}}}_{{\boldsymbol{\theta}}^{(0)}_{0}}\underbrace{\ket{x_{0}^{(0)}}}_{\text{server-
side register
${\boldsymbol{S}}_{smh}^{(0)}$}}\rightarrow\ket{\theta_{1}^{(0)}}\ket{\Delta_{1}^{(0)}}\ket{x_{0}^{(0)}}$
(132)

We will see ${\mathcal{R}}_{1}$ is defined to be this type of operations
applied on each possible superscript in $[0,L]$ and each possible subscript in
$\\{0,1\\}$.

###  8.1 Randomization operator ${\mathcal{R}}_{1}$

To formalize this operator, let’s define an operator that operates on a
${\boldsymbol{x}}^{(i)}_{1-b}$ branch of a semi-honest state, and erase the
phase information stored in ${\boldsymbol{\theta}}_{b}^{(i)}$ by swapping it
with a completely new random value $\Delta^{(i)}_{b}$:

######  Definition 8.1.

Suppose the client holds a tuple of key pairs in register
${\boldsymbol{K}}=({\boldsymbol{K}}^{(i)})_{i\in[0,L]}$,
${\boldsymbol{K}}^{(i)}=({\boldsymbol{x}}^{(i)}_{b})_{b\in\\{0,1\\}}$. And the
client additionally holds a tuple of phase pairs in register
${\boldsymbol{\Theta}}=({\boldsymbol{\Theta}}^{(i)})_{i\in[0,L]}$,
${\boldsymbol{\Theta}}^{(i)}=({\boldsymbol{\theta}}^{(i)}_{b})_{b\in\\{0,1\\}}$,
${\boldsymbol{\theta}}^{(i)}_{b}\in\\{0,1\cdots 7\\}$.

For a purified joint state $\ket{\varphi}$, expand the semi-honest part:

$\Pi_{{\text{semihonest}}}\ket{\varphi}=\underbrace{\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\ket{K}\otimes\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}}_{\text{client}}\otimes\underbrace{\sum_{\vec{b}\in\\{0,1\\}^{1+L}}\ket{\vec{x}_{\vec{b}}}}_{\text{server-
side register
${\boldsymbol{S}}_{smh}$}}\otimes\ket{\varphi_{K,\Theta,\vec{b}}}$ (133)

Recall $\Pi_{{\text{semihonest}}}$ is defined in Definition 6.5 where the
server-side register ${\boldsymbol{S}}_{smh}$ is introduced.

Define ${\sf SWAP}_{1-b,b}^{(i)}$ as follows. First initialize randomness
register ${\boldsymbol{\Delta}}^{(i)}_{b}$ to hold uniformly distributed value
$\in\\{0,1\cdots 7\\}$. Then ${\sf SWAP}_{1-b,b}^{(i)}$ is the following
control-swap operation that acts nontrivially on the
${\boldsymbol{x}}^{(i)}_{1-b}$ branch of (133) and swaps the value of
${\boldsymbol{\theta}}^{(i)}_{b}$ with the values of
${\boldsymbol{\Delta}}_{b}^{(i)}$:

$\displaystyle\underbrace{\ket{\Delta^{(i)}_{b}}}_{{\boldsymbol{\Delta}}^{(i)}_{b}}\underbrace{\ket{K}\ket{\cdots,\underbrace{\theta^{(i)}_{b}}_{{\boldsymbol{\theta}}^{(i)}_{b}},\cdots}}_{\text{client}}\otimes\underbrace{\ket{\cdots
x^{(i)}_{1-b}\cdots}}_{\text{server-side register
${\boldsymbol{S}}_{smh}$}}\quad\quad(K=(K^{(i)})_{i\in[0,L]},K^{(i)}=(x^{(i)}_{b})_{b\in\\{0,1\\}})$
(134) $\displaystyle\xrightarrow{{\sf SWAP}_{1-b,b}^{(i)}}$
$\displaystyle\ket{\theta_{b}^{(i)}}\ket{K}\ket{\cdots,\Delta^{(i)}_{b},\cdots}\otimes\ket{\cdots
x^{(i)}_{1-b}\cdots}$ (135)

The operator acts as identity on the other branch and outside
$\Pi_{{\text{semihonest}}}$.

Then the randomization operator ${\mathcal{R}}_{1}$ is to apply ${\sf
SWAP}^{(i)}_{1-b,b}$ for all the possible $i,b$:

######  Definition 8.2.

Consider the same register set-up as Definition 8.1. Additionally introduce
registers ${\boldsymbol{\Delta}}^{(i)}_{b}$, $i\in[0,L],b\in\\{0,1\\}$, which
are initialized to hold the state

$\ket{\$_{1}}=\frac{1}{\sqrt{8^{2(L+1)}}}\sum_{\forall i\in[0,L],\forall
b\in\\{0,1\\}:\Delta^{(i)}_{b}\in\\{0,1\cdots
7\\}}\ket{(\underbrace{\Delta^{(i)}_{b}}_{{\boldsymbol{\Delta}}_{b}^{(i)}})_{i\in[0,L],b\in\\{0,1\\}}}$

Define randomization operator ${\mathcal{R}}_{1}$ as

$\circ_{\forall i\in[0,L],\forall b\in\\{0,1\\}}{\sf SWAP}^{(i)}_{1-b,b}$

Note that (1) for each $i,b$ the ${\sf SWAP}$ operator uses freshly new
randomness; (2) $\circ$ denote the operator composition; since these ${\sf
SWAP}$ operators commute with each other the order of applying these ${\sf
SWAP}$ operators does not matter.

We will show applying ${\mathcal{R}}_{1}$ to the output of
${\mathsf{AddPhaseWithHelper}}$ keeps the state indistinguishable, as follows:

####  8.1.1 Preparation for the proof: ${\sf ReviseRO}$ Operator

But we note there is an important missing factor in Example 2.1 and
discussions around (131)(132). In the real protocol (characterized by Setup
3), the server also has access to the ciphertexts in the messages of
${\mathsf{AddPhaseWithHelper}}$. Taking this into consideration, the left hand
side of (132) should be replaced by

${\underbrace{\ket{\Delta_{1}^{(0)}}}_{\text{randomness for
${\mathcal{R}}_{1}$}}\underbrace{\ket{H(R^{(0)}_{b^{({\text{helper}})},1}||x^{({\text{helper}})}_{b^{({\text{helper}})}}||x_{1}^{(0)})}}_{\text{RO
register for entry
}R^{(i)}_{b^{({\text{helper}})},1}||x^{({\text{helper}})}_{b^{({\text{helper}})}}||x_{0}^{(i)}}\underbrace{\ket{\theta_{1}^{(0)}}}_{{\boldsymbol{\theta}}_{1}^{(0)}}\underbrace{\ket{H(R^{(0)}_{b^{({\text{helper}})},1}||x^{({\text{helper}})}_{b^{({\text{helper}})}}||x_{1}^{(0)})+\theta_{1}^{(0)}}}_{{\boldsymbol{ct}}^{(0)}_{b^{({\text{helper}})},1}}\underbrace{\ket{x_{0}^{(0)}}}_{\text{server-
side ${\boldsymbol{S}}_{smh}^{(0)}$}}}$ (136)

where $b^{({\text{helper}})}\in\\{0,1\\}$.

Taking these ciphertexts into consideration, the swapping operator in
${\mathcal{R}}_{1}$ does not keep the state invariant, since after the
swapping the random oracle content, ${\boldsymbol{\theta}}$ register, and the
${\boldsymbol{ct}}$ register does not necessarily satisfy Equation (129) given
in Setup 3. However, we note that in Theorem 8.1 we do not actually require
both sides to be approximately the same; what we want is both sides are
indistinguishable under ${\mathcal{F}}_{blind}$. This allows us to first
introduce a ${\sf ReviseRO}$ operator that erases the content of the random
oracle registers in (136). After the application of ${\sf ReviseRO}$, the
application of ${\mathcal{R}}_{1}$ will keep the state invariant.

######  Definition 8.3 (${\sf ReviseRO}$).

Under Setup 3, for each
$i\in[0,L],b^{({\text{helper}})}\in\\{0,1\\},b\in\\{0,1\\}$, the ${\sf
ReviseRO}^{(i)}_{b^{({\text{helper}})},b}$ operator is defined as follows.
Recall Setup 3 for notations of registers; we omit some registers and the
client-side key registers that are not directly used in ${\sf
ReviseRO}^{(i)}_{b^{({\text{helper}})},b}$ (for example,
${\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b}$; it is only used to index
the random oracle registers).

$\displaystyle\underbrace{\ket{H({\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b}||{\boldsymbol{x}}^{({\text{helper}})}_{b^{({\text{helper}})}}||{\boldsymbol{x}}_{b}^{(i)})}}_{\text{RO
register for entry
}{\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b}||{\boldsymbol{x}}^{({\text{helper}})}_{b^{({\text{helper}})}}||{\boldsymbol{x}}_{b}^{(i)}}\underbrace{\ket{\theta_{b}^{(i)}}}_{{\boldsymbol{\theta}}_{b}^{(i)}}\underbrace{\ket{H({\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b}||{\boldsymbol{x}}^{({\text{helper}})}_{b^{({\text{helper}})}}||{\boldsymbol{x}}_{b}^{(i)})+\theta_{b}^{(i)}}}_{{\boldsymbol{ct}}^{(i)}_{b^{({\text{helper}})},b}}$
(137) $\displaystyle\xrightarrow{{\sf
ReviseRO}^{(i)}_{b^{({\text{helper}})},b}}$
$\displaystyle\underbrace{\ket{0}}_{\text{RO register for entry
}{\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b}||{\boldsymbol{x}}^{({\text{helper}})}_{b^{({\text{helper}})}}||{\boldsymbol{x}}_{b}^{(i)}}\underbrace{\ket{\theta_{b}^{(i)}}}_{{\boldsymbol{\theta}}_{b}^{(i)}}\underbrace{\ket{H({\boldsymbol{R}}^{(i)}_{b^{({\text{helper}})},b}||{\boldsymbol{x}}^{({\text{helper}})}_{b^{({\text{helper}})}}||{\boldsymbol{x}}_{b}^{(i)})+\theta_{b}^{(i)}}}_{{\boldsymbol{ct}}^{(i)}_{b^{({\text{helper}})},b}}$
(138)

Then define ${\sf ReviseRO}$ to be the following operation:

  1. 1.

For each $i\in[0,L],b^{({\text{helper}})}\in\\{0,1\\},b\in\\{0,1\\}$:

    1. (a)

Apply ${\sf ReviseRO}^{(i)}_{b^{({\text{helper}})},b}$.

    2. (b)

Apply Hadamard gates on each bit of the RO register for entry
$R^{(i)}_{b^{({\text{helper}})},b}||x^{({\text{helper}})}_{b^{({\text{helper}})}}||x_{b}^{(i)}$.

The second step above is to re-create uniformly random coins for the random
oracle, and thus preserve the validity of the state in the random oracle model
(Definition 3.5). Since this step only applies on the blinded part of $H$ and
the registers are expected to be in state $\ket{0}$ (as shown in (138)) and
thus are not entangled with the other registers, this step will not have
observable influence for operations in ${\mathcal{F}}_{blind}$.

######  Fact 11.

Suppose $\ket{\varphi}\in{\text{SETUP}}^{3}$. Then ${\sf
ReviseRO}\ket{\varphi}\approx^{ind:{\mathcal{F}}_{blind}}\ket{\varphi}$ where
${\mathcal{F}}_{blind}$ is defined in Setup 3.

###### Proof.

Recall that operators in ${\mathcal{F}}_{blind}$ only have read-only access to
existing transcripts and could not query the blinded part of $H$. ∎

###  8.2 Randomization under ${\mathcal{R}}_{1}$

######  Theorem 8.1.

Suppose a normalized purified joint state $\ket{\varphi^{2.a}}$ is in Setup 3.
Then

${\mathcal{R}}_{1}(\ket{\$_{1}}\otimes{\sf
ReviseRO}\ket{\varphi^{2.a}})\approx_{{\mathsf{negl}}(\kappa)}{\sf
ReviseRO}\ket{\varphi^{2.a}}$ (139)

####  8.2.1 Proof of Theorem 8.1

Now we are ready to prove Theorem 8.1.

###### Proof.

Unrolling the definition of ${\mathcal{R}}_{1}$, we only need to prove, for
all $i\in[0,L]$, $b\in\\{0,1\\}$:

${\sf
SWAP}^{(i)}_{1-b,b}(\frac{1}{\sqrt{8}}\sum_{\Delta_{b}^{(i)}\in\\{0,1\cdots
7\\}}\underbrace{\ket{\Delta_{b}^{(i)}}}_{{\boldsymbol{\Delta}}^{(i)}_{b}}\otimes{\sf
ReviseRO}\ket{\varphi^{2.a}})\approx_{{\mathsf{negl}}(\kappa)}{\sf
ReviseRO}\ket{\varphi^{2.a}}$ (140)

Denote the ${\boldsymbol{x}}^{(i)}_{1-b}$ branch of $\ket{\varphi^{2.a}}$ as
$\ket{\varphi_{(i),1-b}^{2.a}}$. Since the operator only operates nontrivially
on $\ket{\varphi_{(i),1-b}^{2.a}}$, (140) is further reduced to proving

${\sf
SWAP}^{(i)}_{1-b,b}(\frac{1}{\sqrt{8}}\sum_{\Delta_{b}^{(i)}\in\\{0,1\cdots
7\\}}\ket{\Delta_{0}^{(i)}}\otimes{\sf
ReviseRO}\ket{\varphi_{(i),1-b}^{2.a}})\approx_{{\mathsf{negl}}(\kappa)}{\sf
ReviseRO}\ket{\varphi_{(i),1-b}^{2.a}}$ (141)

Recall the definition of $\ket{\varphi^{2.a}}$ in Setup 3:

$\ket{\varphi^{2.a}}={\mathsf{AddPhaseWithHelper}}^{{\mathsf{Adv}}}({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}},{\boldsymbol{\Theta}};1^{\kappa})\ket{\varphi^{1}}$

Applying Lemma 6.5 we get

$\ket{\varphi^{2.a}_{(i),1-b}}\approx_{{\mathsf{negl}}(\kappa)}{\mathsf{AddPhaseWithHelper}}^{{\mathsf{Adv}}}({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}},{\boldsymbol{\Theta}};1^{\kappa})\ket{\varphi^{1}_{(i),1-b}}$
(142)

Now we are going to use Fact 4. We need to show
$\ket{\varphi_{(i),1-b}^{2.a}}$ is close to a state that satisfies the
condition of Fact 4. This is by replacing state and operations in (142) by
states and operators that does not depend on the values of
${\boldsymbol{\theta}}^{(i)}_{b}$ step by step:

  1. 1.

Since $\ket{\varphi_{(i),1-b}^{1}}$ is efficiently-preparable, we can apply
Lemma 3.4. Suppose the random paddings used within the
${\mathsf{AddPhaseWithHelper}}$ are sampled and stored in client-side register
${\boldsymbol{R}}$. By Lemma 3.4:

$\exists\ket{\tilde{\varphi}^{1}_{(i),1-b}}\text{ independent of
$H({\boldsymbol{R}}||\cdots)$
}:\ket{\tilde{\varphi}^{1}_{(i),1-b}}\approx_{{\mathsf{negl}}(\kappa)}\ket{\varphi^{1}_{(i),1-b}}$
(143)

  2. 2.

Define ${\mathsf{Adv}}^{\prime}$ as the adversary that compared to
${\mathsf{Adv}}$, all the queries to $H$ are replaced by $H^{mid}$ where
$H^{mid}$ is a blinded oracle where entries in the form of
$\\{0,1\\}^{\kappa}||\\{0,1\\}^{|x^{({\text{helper}})}|}||{\boldsymbol{x}}^{(i)}_{b}$
are blinded. ($|x^{({\text{helper}})}|$ is the length of key in
$K^{({\text{helper}})}$.) Intuitively, recall we are studying the
${\boldsymbol{x}}^{(i)}_{1-b}$-branch thus ${\boldsymbol{x}}^{(i)}_{b}$ is not
predictable by the server. Formally, by Lemma 6.3 we have

$\displaystyle{\mathsf{AddPhaseWithHelper}}^{\mathsf{Adv}}({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}},{\boldsymbol{\Theta}};1^{\kappa})\ket{\varphi_{(i),1-b}^{1}}$
(144) $\displaystyle\approx_{{\mathsf{negl}}(\kappa)}$
$\displaystyle{\mathsf{AddPhaseWithHelper}}^{{\mathsf{Adv}}^{\prime}}({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}},{\boldsymbol{\Theta}};1^{\kappa})\ket{\varphi_{(i),1-b}^{1}}$
(145)

  3. 3.

Combining (143)(145) above we have

$\ket{\tilde{\varphi}^{2.a}_{(i),1-b}}:={\mathsf{AddPhaseWithHelper}}^{{\mathsf{Adv}}^{\prime}}({\boldsymbol{K}}^{({\text{helper}})},{\boldsymbol{K}},{\boldsymbol{\Theta}};1^{\kappa})\ket{\tilde{\varphi}^{1}_{(i),1-b}}\approx_{{\mathsf{negl}}(\kappa)}\ket{\varphi^{2.a}_{(i),1-b}}$

and by its definition it is independent to random oracle output register
${\boldsymbol{H}}({\boldsymbol{R}}||\\{0,1\\}^{|x^{({\text{helper}})}|}||{\boldsymbol{x}}_{b}^{(i)})$.
Recall the encryptions of $\theta_{b}^{(i)}$ in the client-side messages of
${\mathsf{AddPhaseWithHelper}}$ have the form

$ct^{(i)}_{b^{({\text{helper}})},b}=h+\theta_{b}^{(i)},h=H(R^{(i)}_{b^{({\text{helper}})},b}||x^{({\text{helper}})}_{b^{({\text{helper}})}}||x_{b}^{(i)})$

Thus after the application of ${\sf ReviseRO}^{(i)}_{b^{({\text{helper}})},b}$
on $\ket{\tilde{\varphi}^{2.a}_{(i),1-b}}$ the overall state could be written
as

$\sum_{\theta^{(i)}_{b^{({\text{helper}})},b}\in\\{0,1\cdots
7\\}}\sum_{h\in\\{0,1\cdots
7\\}}\underbrace{\ket{\theta^{(i)}_{b^{({\text{helper}})},b}}}_{{\boldsymbol{\theta}}^{(i)}_{b^{({\text{helper}})},b}}\underbrace{\ket{ct^{(i)}_{b^{({\text{helper}})},b}}}_{{\boldsymbol{ct}}^{(i)}_{b^{({\text{helper}})},b}}\underbrace{\ket{\psi_{ct^{(i)}_{b^{({\text{helper}})},b}}}}_{\text{other
parts}}$

That is, the rightmost term does not depend on the values of register
${\boldsymbol{\theta}}^{(i)}_{b^{({\text{helper}})},b}$ (but could depend on
the transcript). Now the condition for applying Fact 4 is satisfied. This
completes the proof of (141).

This completes the proof of (140) and completes the whole proof. ∎

###  8.3 New Set-up

Now we are going to formalize a new setup that captures the properties of
states after the randomization of ${\mathcal{R}}_{1}$.

######  Set-up 4.

Define ${\text{SETUP}}^{4}$ as the set of states that could be written as

${\mathcal{R}}_{1}(\ket{\$_{1}}\otimes{\sf
ReviseRO}\ket{\varphi}),\ket{\varphi}\in{\text{SETUP}}^{3}.$

Since there have been lots of nesting in the definition, let’s give a recap of
the properties of states in ${\text{SETUP}}^{4}$.

In ${\text{SETUP}}^{4}$ the client holds a tuple of key pairs in register
${\boldsymbol{K}}=({\boldsymbol{K}}^{(i)})_{i\in[0,L]}$,
${\boldsymbol{K}}^{(i)}=({\boldsymbol{x}}^{(i)}_{b})_{b\in\\{0,1\\}}$. And the
client additionally holds a tuple of phase pairs in register
${\boldsymbol{\Theta}}=({\boldsymbol{\Theta}}^{(i)})_{i\in[0,L]}$,
${\boldsymbol{\Theta}}^{(i)}=({\boldsymbol{\theta}}^{(i)}_{b})_{b\in\\{0,1\\}}$,
${\boldsymbol{\theta}}^{(i)}_{b}\in\\{0,1\cdots 7\\}$. $H^{\prime}$ is defined
to be the blinded oracle where entries in the form of
$\\{0,1\\}^{\kappa}||{\boldsymbol{K}}^{({\text{helper}})}||\cdots$ are
blinded, which covers the target registers of ${\sf ReviseRO}$.
${\mathcal{F}}_{blind}$ is defined to be the set of server-side operators that
could only query this blinded oracle.

A state $\ket{\varphi}\in{\text{SETUP}}^{4}$ satisfies:

  * •

It is key checkable for each key pair in ${\boldsymbol{K}}$ by an operator in
${\mathcal{F}}_{blind}$;

  * •

It is strongly-claw-free for each key pair in ${\boldsymbol{K}}$ against
efficient operators in ${\mathcal{F}}_{blind}$;

  * •

For each possible value $\Theta$ of registers ${\boldsymbol{\Theta}}$, the
corresponding component of $\ket{\varphi}$ has norm
$\frac{1}{\sqrt{|{\text{Domain}}({\boldsymbol{\Theta}})|}}$.

  * •

For any $i\in[0,L],b\in\\{0,1\\}$, the ${\boldsymbol{x}}^{(i)}_{1-b}$-branch
of $\ket{\varphi}$ does not depend on the value of
${\boldsymbol{\theta}}^{(i)}_{b}$.

We note that since the operator ${\sf ReviseRO}$ is introduced in the
definition of ${\text{SETUP}}^{4}$ the state is not obviously efficiently-
preparable. But generally the lemmas that are proved with efficient-preparable
property still holds for states in ${\text{SETUP}}^{4}$ against adversary in
${\mathcal{F}}_{blind}$. The reason is ${\sf ReviseRO}$ is not observable by
${\mathcal{F}}_{blind}$, and ${\mathcal{R}}_{1}$ keeps the state approximately
invariant by Theorem 8.1.

We list the following lemmas that will be used in later proofs.

######  Lemma 8.2 (Analog of Lemma 6.5).

Consider a normalized purified joint state $\ket{\varphi}$ in Setup 4. Suppose
$\ket{\varphi^{\prime}}={\mathsf{Prtl}}^{\mathsf{Adv}}\ket{\varphi}$ where the
protocol ${\mathsf{Prtl}}$ and adversary ${\mathsf{Adv}}$ are both efficient
and do not query the blinded part of $H$. Suppose $\ket{\varphi^{\prime}}$
satisfies all the conditions in Setup 1 except the third bullet.

Use $\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}$ to
denote the projection onto $\vec{{\boldsymbol{x}}}_{\vec{b}}$-branch
(Definition 6.7). Then for any efficient server-side operation
$D\in{\mathcal{F}}_{blind}$ there is

$\Pi_{{\text{semihonest}}}D\Pi_{{\text{semihonest}}}\ket{\varphi}\approx_{{\mathsf{negl}}(\kappa)}\sum_{\vec{b}\in\\{0,1\\}^{L}}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}D\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}\ket{\varphi}$
(146)

The two lemmas below are analog of Lemma 7.2 and Corollary 7.3, and we use
${\boldsymbol{K}}^{\prime}$ to replace ${\boldsymbol{K}}$ in these lemmas
since the symbol ${\boldsymbol{K}}$ is occupied by the key tuple appeared in
the protocol.

######  Lemma 8.3 (Analog of Lemma 7.2).

Consider a normalized purified joint state $\ket{\varphi}$ in Setup 4. Suppose
$\ket{\varphi^{\prime}}={\mathsf{Prtl}}^{{\mathsf{Adv}}_{0}}\ket{\varphi}$
where the protocol ${\mathsf{Prtl}}$ and adversary ${\mathsf{Adv}}_{0}$ are
both efficient and do not query the blinded part of $H$. Then suppose the
client holds a key pair in register
${\boldsymbol{K}}^{\prime}=({\boldsymbol{x}}_{0}^{\prime},{\boldsymbol{x}}_{1}^{\prime})$,
and $\ket{\varphi^{\prime}}$ satisfies all the conditions in
${\text{SETUP}}^{2}({\boldsymbol{K}}^{\prime})$ except the first bullet, and
is in the semi-honest form of ${\boldsymbol{K}}^{\prime}$ with only
${\boldsymbol{x}}_{0}^{\prime}$ branch. Then for any efficient adversary
${\mathsf{Adv}}\in{\mathcal{F}}_{blind}$ there is

$|\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq 0}^{\text{last $\kappa$
bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi^{\prime}}|\approx_{{\mathsf{negl}}(\kappa)}\frac{1}{\sqrt{2}}|\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi^{\prime}}|$
$|\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq 0}^{\text{last $\kappa$
bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi^{\prime}}|\approx_{{\mathsf{negl}}(\kappa)}\frac{1}{\sqrt{2}}|\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi^{\prime}}|$

######  Corollary 8.4 (Analog of Corollary 7.3).

Consider a normalized purified joint state $\ket{\varphi}$ in Setup 4. Suppose
$\ket{\varphi^{\prime}}={\mathsf{Prtl}}^{{\mathsf{Adv}}_{0}}\ket{\varphi}$
where the protocol ${\mathsf{Prtl}}$ and adversary ${\mathsf{Adv}}_{0}$ are
both efficient and do not query the blinded part of $H$. Then suppose the
client holds a key pair in register
${\boldsymbol{K}}^{\prime}=({\boldsymbol{x}}_{0}^{\prime},{\boldsymbol{x}}_{1}^{\prime})$,
and $\ket{\varphi^{\prime}}$ satisfies all the conditions in
${\text{SETUP}}^{2}({\boldsymbol{K}}^{\prime})$ except the first bullet, and
is in an $\epsilon$-semi-honest form of ${\boldsymbol{K}}^{\prime}$. Denote
the ${\boldsymbol{x}}_{0}^{\prime}$-branch as $\ket{\varphi_{0}^{\prime}}$ and
${\boldsymbol{x}}_{1}^{\prime}$-branch as $\ket{\varphi_{1}^{\prime}}$. If an
efficient adversary ${\mathsf{Adv}}\in{\mathcal{F}}_{blind}$ could make the
client output ${\mathsf{pass}}$ in the Hadamard test (Protocol 4) from initial
state $\ket{\varphi^{\prime}}$ with probability $\geq 1-p$, then

$\displaystyle\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi_{0}^{\prime}}$
$\displaystyle\approx_{\sqrt{2(p+2\epsilon)}+{\mathsf{negl}}(\kappa)}$
$\displaystyle\Pi_{\eqref{eq:htt}=0}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi_{1}^{\prime}}$
(147) $\Pi_{=0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi_{0}^{\prime}}\approx_{\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}0,$
$\Pi_{=0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi_{1}^{\prime}}\approx_{\sqrt{p+2\epsilon}+{\mathsf{negl}}(\kappa)}0$
(148) $\displaystyle\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi_{0}^{\prime}}$
$\displaystyle\approx_{\sqrt{p+\epsilon}+{\mathsf{negl}}(\kappa)}$
$\displaystyle-\Pi_{\eqref{eq:htt}=1}^{{\boldsymbol{d}}}\Pi_{\neq
0}^{\text{last $\kappa$ bits of
}{\boldsymbol{d}}}{\mathsf{HadamardTest}}^{\mathsf{Adv}}({\boldsymbol{K}}^{\prime};1^{\kappa})\ket{\varphi_{1}^{\prime}}$
(149)

We put their proofs in Appendix D.

##  9 Analysis of the Collective Phase Test (${\mathsf{CoPhTest}}$)

In this section, we will analyze the implication of collective phase test.

Before going to the protocol analysis, we will define a series of notions
including the _pre-phase-honest form_ , and the _phase-honest form_. Then in
Section 9.2, we will show, if an efficient adversary could pass the collective
phase test from a state in Setup 4, the overall state could be further
randomized under a new randomization operator ${\mathcal{R}}_{2}$. This
operator will transform a state in a semi-honest form to a pre-phase-honest
form.

###  9.1 Pre-phase-honest Form and Phase-honest Form

Let’s assume the Setup 4 and assume the state is in a semi-honest form for
$K$. We say this state is a pre-phase-honest form or a phase-honest form if it
is a semi-honest form and has additional structure related to the phase
information $\Theta$. Recall by Definition 6.7 and Notation 3.14 the semi-
honest form could be written as a linear sum of different branches, and each
branch could be written as the sum of different components based on different
values of ${\boldsymbol{\Theta}}$ register.

For preparation, let’s first define the _honest joint phase_ of a branch:

######  Definition 9.1 (Honest joint phase).

Suppose the client holds phase tuple
${\boldsymbol{\Theta}}=({\boldsymbol{\theta}}^{(i)}_{b})_{i\in[0,L],b\in\\{0,1\\}}$.
We call
${\text{SUM}}(\vec{\Theta}_{\vec{b}})=\theta^{(0)}_{b^{(0)}}+\theta^{(1)}_{b^{(1)}}+\theta^{(2)}_{b^{(2)}}+\cdots+\theta^{(L)}_{b^{(L)}}$
for $\vec{b}=b^{(0)}b^{(1)}b^{(2)}\cdots b^{(L)}\in\\{0,1\\}^{1+L}$ the honest
joint phase for $\vec{{\boldsymbol{x}}}_{\vec{b}}$-branch.

Then informally:

  * •

A pre-phase honest form satisfies if
${\text{SUM}}(\vec{\Theta}_{\vec{b}_{1}})={\text{SUM}}(\vec{\Theta}_{\vec{b}_{2}})$
then the $\vec{x}_{\vec{b}_{1}}$ branch is the same as the
$\vec{x}_{\vec{b}_{2}}$ branch (if we only consider the registers excluding
the client side $\Theta$.) But we do not restrict the phases of states with
different ${\text{SUM}}(\vec{\Theta}_{\vec{b}})$.

  * •

A state in the phase-honest form means the branch
$\vec{{\boldsymbol{x}}}_{\vec{b}}$ has phase
${\text{SUM}}(\vec{\Theta}_{\vec{b}})$.

######  Definition 9.2 (Pre-phase-honest form).

Assume Setup 4. We say a semi-honest purified joint state $\ket{\varphi}$ is
in the pre-phase honest form if there exists a family of states
$\ket{\varphi_{K,\vec{b},sum}}$ where
$K\in{\text{Domain}}({\boldsymbol{K}}),\vec{b}\in\\{0,1\\}^{1+L},sum\in\\{0,1\cdots
7\\}$ such that $\ket{\varphi}$ could be written as

$\underbrace{\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\ket{K}\otimes\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}}_{\text{client}}\otimes\underbrace{\sum_{\vec{b}\in\\{0,1\\}^{1+L}}\ket{\vec{x}_{\vec{b}}}}_{\text{server}}\otimes\ket{\varphi_{K,\vec{b},{\text{SUM}}(\vec{\Theta}_{\vec{b}}})}$
(150)

######  Definition 9.3 (Phase-honest form).

Assume Setup 4. We say a semi-honest purified joint state $\ket{\varphi}$ is
in the pre-phase honest form if there exists a family of states
$\ket{\varphi_{K,\vec{b},+}},\ket{\varphi_{K,\vec{b},-}}$ where
$K\in{\text{Domain}}({\boldsymbol{K}}),\vec{b}\in\\{0,1\\}^{1+L}$ such that
$\ket{\varphi}$ could be written as

$\underbrace{\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\ket{K}\otimes\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}}_{\text{client}}\otimes\underbrace{\sum_{\vec{b}\in\\{0,1\\}^{1+L}}\ket{\vec{x}_{\vec{b}}}}_{\text{server}}\otimes(e^{{\text{SUM}}(\vec{\Theta}_{\vec{b}}){\mathrm{i}}\pi/4}\ket{\varphi_{K,\vec{b},+}}+e^{-{\text{SUM}}(\vec{\Theta}_{\vec{b}}){\mathrm{i}}\pi/4}\ket{\varphi_{K,\vec{b},-}})$
(151)

As expected, in the formal definition we need to take the complex-conjugate
term into consideration.

###  9.2 Randomization Operator ${\mathcal{R}}_{2}$

Let’s start to define the randomization operator that randomizes a semi-honest
form to a pre-phase-honest form. To do that, we will define an operator ${\sf
Add}_{\vec{b}}$ operated on the $\vec{x}_{\vec{b}}$-branch for each
$\vec{b}\in\\{0,1\\}^{1+L}$.

######  Definition 9.4.

Assume Setup 4. Consider a purified joint state $\ket{\varphi}$ in semi-honest
form:

$\ket{\varphi}=\underbrace{\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\ket{K}\otimes\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}}_{\text{client}}\otimes\underbrace{\sum_{\vec{b}\in\\{0,1\\}^{1+L}}\ket{\vec{x}_{\vec{b}}}}_{\text{server}}\otimes\ket{\varphi_{K,\Theta,\vec{b}}}$

Define the control-sum operator ${\sf Add}_{\vec{b}}$ controlled on a specific
branch indexed by $\vec{b}=b^{(0)}b^{(1)}b^{(2)}\cdots b^{(L)}$, with
randomness $\Delta^{(1)}_{b^{(1)}}\cdots\Delta^{(L)}_{b^{(L)}}$:

$\displaystyle\ket{\Delta^{(1)}_{b^{(1)}}\cdots\Delta^{(L)}_{b^{(L)}}}\underbrace{\ket{\theta^{(0)}_{b^{(0)}}\theta^{(1)}_{b^{(1)}}\cdots\theta^{(L)}_{b^{(L)}}}}_{\text{client-
side registers
${\boldsymbol{\theta}}^{(0)}_{b^{(0)}}{\boldsymbol{\theta}}^{(1)}_{b^{(1)}}\cdots{\boldsymbol{\theta}}^{(L)}_{b^{(L)}}$}}\underbrace{\ket{\vec{x}_{\vec{b}}}}_{\text{server}}$
(152) $\displaystyle\xrightarrow{{\sf Add}_{\vec{b}}}$
$\displaystyle\ket{\theta^{(1)}_{b^{(1)}}\cdots\theta^{(L)}_{b^{(L)}}}\underbrace{\ket{(\sum_{i\in[0,L]}\theta^{(i)}_{b^{(i)}}-\sum_{i\in[L]}\Delta^{(i)}_{b^{(i)}})\Delta^{(1)}_{b^{(1)}}\cdots\Delta^{(L)}_{b^{(L)}}}}_{{\boldsymbol{\theta}}^{(0)}_{b^{(0)}}{\boldsymbol{\theta}}^{(1)}_{b^{(1)}}\cdots{\boldsymbol{\theta}}^{(L)}_{b^{(L)}}}\ket{\vec{x}_{\vec{b}}}$
(153)

and acts as identity on the other branches and outside
$\Pi_{{\text{semihonest}}}$.

Which means:

  * •

This operator only operates on the ${\vec{x}_{\vec{b}}}$-branch of the state,
and randomize the
$\theta^{(0)}_{b^{(0)}}\theta^{(1)}_{b^{(1)}}\cdots\theta^{(L)}_{b^{(L)}}$
information stored on the client side with randomness $\Delta$. Recall that in
the ${\mathsf{preRSPV}}$ protocol $\theta_{b^{(i)}}^{(i)}$ could be decrypted
with keys in $\vec{x}_{\vec{b}}$. Thus this operator aims at randomizing the
phases that could be decrypted by the server’s keys, which is different from
the operator ${\mathcal{R}}_{1}$.

  * •

The randomization is done in a way that for each branch, the honest joint
phase (Definition 9.1) of this branch remains the same.

Then define the overall randomization operator for the collective phase test
as the composition of ${\sf Add}_{\vec{b}}$ for each $\vec{b}$, with different
randomness:

######  Definition 9.5 (${\mathcal{R}}_{2}$).

Assume Setup 4. For each $i\in[L]$, $b\in\\{0,1\\}$, initialize register
${\boldsymbol{\Delta}}^{(i)}_{b}$ to store a uniform superposition of
$\\{0,1\cdots 7\\}$. Overall these registers are initialized to hold the state

$\ket{\$_{2}}=\frac{1}{\sqrt{8^{2L}}}\sum_{\forall
b\in\\{0,1\\},i\in[L]:\Delta^{(i)}_{b}\in\\{0,1\cdots
7\\}}\ket{(\underbrace{\Delta_{b}^{(i)}}_{{\boldsymbol{\Delta}}_{b}^{(i)}})_{i\in[L],b\in\\{0,1\\}}}$
(154)

Define ${\mathcal{R}}_{2}$ as

${\mathcal{R}}_{2}=\circ_{\vec{b}\in\\{0,1\\}^{1+L}}{\sf Add}_{\vec{b}}$

We have the following theorem about ${\mathcal{R}}_{2}$.

######  Theorem 9.1.

${\mathcal{R}}_{2}$ is an efficient operator.

###### Proof.

${\mathcal{R}}_{2}$ can be implemented through the following operations.

  1. 1.

Use values of registers ${\boldsymbol{K}}$ and ${\boldsymbol{S}}_{smh}$ to
calculate the index of each branch.

  2. 2.

For the $\vec{{\boldsymbol{x}}}_{\vec{b}}$-branch, controlled by the index
$\vec{b}$, apply operator ${\sf Add}_{\vec{b}}$.

  3. 3.

Reverse the first step.

∎

######  Theorem 9.2.

If $\ket{\varphi}\in{\text{SETUP}}^{4}$ is in a semi-honest form,
${\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\ket{\varphi})$ is in a pre-phase-honest
form.

###### Proof.

By the definition of pre-phase-honest form we only need to consider each
branch separately. For $\vec{b}\in\\{0,1\\}^{1+L}$, denote the
$\vec{{\boldsymbol{x}}}_{\vec{b}}$-branch of $\ket{\varphi}$ as

$\ket{\varphi_{\vec{b}}}=\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}\otimes\ket{\varphi_{\Theta,\vec{b}}}$

By the condition that $\ket{\varphi}\in{\text{SETUP}}^{4}$, we know
$\ket{\varphi_{\vec{b}}}$ does not depend on the values of registers
${\boldsymbol{\theta}}_{1-b^{(0)}}^{(0)}{\boldsymbol{\theta}}_{1-b^{(1)}}^{(1)}\cdots{\boldsymbol{\theta}}_{1-b^{(L)}}^{(L)}$.
Thus we could further simplify the notation of $\ket{\varphi_{\vec{b}}}$:

$\ket{\varphi_{\vec{b}}}=\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}\otimes\ket{\varphi_{\vec{b},\theta_{b^{(0)}}^{(0)}\theta_{b^{(1)}}^{(1)}\cdots\theta_{b^{(L)}}^{(L)}}}$

By direct calculation, after the application of ${\sf Add}_{\vec{b}}$ it
becomes

$\displaystyle{\sf Add}_{\vec{b}}(\ket{\$_{2}}\otimes\ket{\varphi_{\vec{b}}})$
(155) $\displaystyle=$ $\displaystyle\sum_{\forall
b\in\\{0,1\\},i\in[L]:\Delta^{(i)}_{b}\in\\{0,1\cdots
7\\}}\ket{\theta_{b^{(0)}}^{(0)}\theta^{(1)}_{b^{(1)}}\cdots\theta^{(L)}_{b^{(L)}}}\ket{(\sum_{i\in[0,L]}\theta^{(i)}_{b^{(i)}}-\sum_{i\in[L]}\Delta^{(i)}_{b^{(i)}})\Delta^{(1)}_{b^{(1)}}\cdots\Delta^{(L)}_{b^{(L)}}}\otimes\ket{\varphi_{\vec{b},\theta_{b^{(0)}}^{(0)}\theta_{b^{(1)}}^{(1)}\cdots\theta_{b^{(L)}}^{(L)}}}$
(156) $\displaystyle=$ $\displaystyle\sum_{\forall
b\in\\{0,1\\},i\in[0,L]:\tilde{\Delta}^{(i)}_{b}\in\\{0,1\cdots
7\\},\sum_{i\in[0,L]}\tilde{\Delta}^{(i)}_{b^{(i)}}=\sum_{i\in
0,L]}\theta^{(i)}_{b^{(i)}}}\ket{\theta_{b^{(0)}}^{(0)}\theta^{(1)}_{b^{(1)}}\cdots\theta^{(L)}_{b^{(L)}}}\ket{\tilde{\Delta}^{(0)}_{b^{(0)}}\tilde{\Delta}^{(1)}_{b^{(1)}}\cdots\tilde{\Delta}^{(L)}_{b^{(L)}}}\otimes\ket{\varphi_{\vec{b},\theta_{b^{(0)}}^{(0)}\theta_{b^{(1)}}^{(1)}\cdots\theta_{b^{(L)}}^{(L)}}}$
(157)

which has the form of pre-phase-honest form if we define

$\ket{\varphi_{\vec{b},sum}}=\sum_{\forall
i\in[0,L]:\theta^{(i)}_{b^{(i)}}\in\\{0,1\cdots 7\\},\sum_{i\in
0,L]}\theta^{(i)}_{b^{(i)}}=sum}\ket{\theta_{b^{(0)}}^{(0)}\theta^{(1)}_{b^{(1)}}\cdots\theta^{(L)}_{b^{(L)}}}\ket{\varphi_{\vec{b},\theta_{b^{(0)}}^{(0)}\theta_{b^{(1)}}^{(1)}\cdots\theta_{b^{(L)}}^{(L)}}}$

∎

Then we can prove, if the attacker wants to pass the collective phase test,
the state should be indistinguishable under randomization of
${\mathcal{R}}_{2}$.

###  9.3 Analysis of ${\mathsf{CoPhTest}}$

######  Theorem 9.3.

Assume Setup 4. Suppose a normalized purified joint state $\ket{\varphi}$ is
in $\epsilon_{0}$-semi-honest form. Suppose ${\mathsf{Adv}}$ is an efficient
adversary that could make the client output ${\mathsf{pass}}$ in the
collective phase test with probability $\geq 1-\epsilon_{1}$ from initial
state $\ket{\varphi}$. Then there is

${\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\ket{\varphi})\approx_{(12\epsilon_{1}^{1/4}+\epsilon_{0}+{\mathsf{negl}}(\kappa))}\ket{\$_{2}}\otimes\ket{\varphi}$
(158)

The proof is given below.

###### Proof.

Let’s denote $\ket{\varphi^{\prime}}$ as the output of running
${\mathsf{CoPhTest}}$ on $\ket{\varphi}$ with ${\mathsf{Adv}}$:

$\ket{\varphi^{\prime}}={\mathsf{CoPhTest}}^{\mathsf{Adv}}({\boldsymbol{K}},{\boldsymbol{\Theta}};1^{\kappa})\ket{\varphi}$
$|\Pi_{{\mathsf{pass}}}\ket{\varphi^{\prime}}|^{2}\geq 1-\epsilon_{1}$ (159)

The first step in the ${\mathsf{CoPhTest}}$ protocol is a call to the
${\mathsf{Combine}}$ protocol. This protocol combines $(1+L)$ gadgets into one
single gadget. Denote the output state after this step as
$\ket{\varphi^{mid}}$:

$\ket{\varphi^{mid}}:={\sf
Calc}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)})\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}(\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket)$

where

  * •

$\llbracket{\mathsf{Combine}}\rrbracket$ is the client-side messages in the
${\mathsf{Combine}}$ step,

  * •

${\mathsf{Adv}}_{1}$ is the adversary’s operation in this step,

  * •

${\mathsf{Response}}$ is the operation that the server sends back a response
(which is the output of ${\mathsf{Adv}}_{1}$),

  * •

and ${\sf
Calc}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)})$ is
the client-side operation that calculates
${\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)}$ based on
the server’s response.

Let’s first define some notations for preparation. Recall the key vector
notation in Notation 6.1, when the key tuple is
$K=(x_{0}^{(i)},x_{1}^{(i)})_{i\in[0,L]}\in{\text{Domain}}({\boldsymbol{K}})$
and the phase tuple is
$\Theta=(\theta_{0}^{(i)},\theta_{1}^{(i)})_{i\in[0,L]}\in{\text{Domain}}({\boldsymbol{\Theta}})$,
suppose the server’s measurement response is

$r_{b^{(1)}}^{(1)}r_{b^{(2)}}^{(2)}\cdots r_{b^{(L)}}^{(L)}$

the final $K^{(combined)}$ could be denoted as

$K^{(combined)}=(\vec{x}_{\vec{b}_{0}},\vec{x}_{\vec{b}_{1}})$

where

$\vec{b}_{0}=0b^{(1)}b^{(2)}\cdots
b^{(L)},\vec{b}_{1}=1(1-b^{(1)})(1-b^{(2)})\cdots(1-b^{(L)}),b^{(1)}\cdots
b^{(L)}\in\\{0,1\\}^{L}$ (160)

Below we will use

$\vec{b}_{0}+\vec{b}_{1}=\vec{1}$

to denote $\vec{b}_{0},\vec{b}_{1}$ that satisfy (160), and use
$0||\\{0,1\\}^{L}$, $1||\\{0,1\\}^{L}$ to denote the domain of
$\vec{b}_{0},\vec{b}_{1}$ above.

Correspondingly, the combined phases are

$\Theta^{(combined)}=(\theta^{(combined)}_{0},\theta^{(combined)}_{1})=(\sum_{i\in[0,L]}\theta^{(i)}_{b^{(i)}},\sum_{i\in[0,L]}\theta^{(i)}_{1-b^{(i)}})$

Adopting the notation of honest joint phase in Definition 9.1, this could be
written as

$\Theta^{(combined)}=({\text{SUM}}(\vec{\Theta}_{\vec{b}_{0}}),{\text{SUM}}(\vec{\Theta}_{\vec{b}_{1}}))$

Now we analyze the protocol. Starting from $\ket{\varphi^{mid}}$, with $1/2$
probability both parties will do a standard basis test. By (159) the passing
probability of this step should be $\geq 1-2\epsilon_{1}$, by Theorem 6.4 we
can expand the state $\ket{\varphi^{mid}}$ based on the combined keys:

$\exists\text{ efficient
}O:\ket{\tilde{\varphi}^{mid}}:=O\ket{\varphi^{mid}},\ket{\tilde{\varphi}^{mid}}\text{
is $1.5\sqrt{\epsilon_{1}}$-semi-honest for ${\boldsymbol{K}}^{(combined)}$}$
(161)

Conventionally denote the server-side register that stores the keys in
${\boldsymbol{K}}^{(combined)}$ in the semi-honest form as
${\boldsymbol{S}}_{smh}$. Then:

$\Pi_{{\text{semihonest}}({\boldsymbol{K}}^{(combined)})}^{{\boldsymbol{S}}_{smh}}\ket{\tilde{\varphi}^{mid}}=\underbrace{\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\ket{K}\otimes\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}}_{\text{client}}$
$\otimes\sum_{\vec{b}_{0},\vec{b}_{1}\in\\{0,1\\}^{1+L}:\vec{b}_{0}+\vec{b}_{1}=\vec{1}}\underbrace{\ket{\vec{x}_{\vec{b}_{0}},\vec{x}_{\vec{b}_{1}}}}_{{\boldsymbol{K}}^{(combined)}}\underbrace{\ket{{\text{SUM}}(\vec{\Theta}_{\vec{b}_{0}}),{\text{SUM}}(\vec{\Theta}_{\vec{b}_{1}})}}_{{\boldsymbol{\Theta}}^{(combined)}}\otimes\underbrace{\ket{r_{b^{(1)}}^{(1)}r_{b^{(2)}}^{(2)}\cdots
r_{b^{(L)}}^{(L)}}}_{\text{transcript}}\otimes\underbrace{\sum_{\vec{b}\in(\vec{b}_{0},\vec{b}_{1})}\ket{\vec{x}_{\vec{b}}}}_{{\boldsymbol{S}}_{smh}}\otimes\ket{\varphi_{K,\Theta,\vec{b}}}$

To show (158), we will first show:

${\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\ket{\tilde{\varphi}^{mid}})\approx_{11\epsilon_{1}^{1/4}+{\mathsf{negl}}(\kappa)}\ket{\tilde{\varphi}^{mid}}$
(162)

Note that
$\Pi_{{\text{semihonest}}({\boldsymbol{K}}^{(combined)})}^{{\boldsymbol{S}}_{smh}}\ket{\tilde{\varphi}^{mid}}$
we are considering the semi-honest form for key pair
${\boldsymbol{K}}^{(combined)}$ and there are only two branches. Denote the
two branches as
$\ket{\tilde{\varphi}_{0}^{mid}},\ket{\tilde{\varphi}_{1}^{mid}}$:

$\ket{\tilde{\varphi}^{mid}_{0}}=\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\ket{K}\otimes\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}\otimes$
$\sum_{\vec{b}_{0},\vec{b}_{1}\in\\{0,1\\}^{1+L}:\vec{b}_{0}+\vec{b}_{1}=\vec{1}}\ket{\vec{x}_{\vec{b}_{0}},\vec{x}_{\vec{b}_{1}}}\ket{{\text{SUM}}(\vec{\Theta}_{\vec{b}_{0}}),{\text{SUM}}(\vec{\Theta}_{\vec{b}_{1}})}\otimes\ket{r_{b^{(1)}}^{(1)}r_{b^{(2)}}^{(2)}\cdots
r_{b^{(L)}}^{(L)}}\otimes\ket{\vec{x}_{\vec{b_{0}}}}\otimes\ket{\varphi_{K,\Theta,\vec{b_{0}}}}$
$\ket{\tilde{\varphi}^{mid}_{1}}=\sum_{K\in{\text{Domain}}({\boldsymbol{K}})}\ket{K}\otimes\sum_{\Theta\in{\text{Domain}}({\boldsymbol{\Theta}})}\ket{\Theta}\otimes$
$\sum_{\vec{b}_{0},\vec{b}_{1}\in\\{0,1\\}^{1+L}:\vec{b}_{0}+\vec{b}_{1}=\vec{1}}\ket{\vec{x}_{\vec{b}_{0}},\vec{x}_{\vec{b}_{1}}}\ket{{\text{SUM}}(\vec{\Theta}_{\vec{b}_{0}}),{\text{SUM}}(\vec{\Theta}_{\vec{b}_{1}})}\otimes\ket{r_{b^{(1)}}^{(1)}r_{b^{(2)}}^{(2)}\cdots
r_{b^{(L)}}^{(L)}}\otimes\ket{\vec{x}_{\vec{b_{1}}}}\otimes\ket{\varphi_{K,\Theta,\vec{b_{1}}}}$

Thus
$\Pi_{{\text{semihonest}}({\boldsymbol{K}}^{(combined)})}^{{\boldsymbol{S}}_{smh}}\ket{\tilde{\varphi}^{mid}}=\ket{\tilde{\varphi}^{mid}_{0}}+\ket{\tilde{\varphi}^{mid}_{1}}$.

Then (162) is further reduced to proving:

${\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\ket{\tilde{\varphi}^{mid}_{0}})\approx_{5\epsilon_{1}^{1/4}+{\mathsf{negl}}(\kappa)}\ket{\$_{2}}\otimes\ket{\tilde{\varphi}^{mid}_{0}}$
(163)
${\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\ket{\tilde{\varphi}^{mid}_{1}})\approx_{5\epsilon_{1}^{1/4}+{\mathsf{negl}}(\kappa)}\ket{\$_{2}}\otimes\ket{\tilde{\varphi}^{mid}_{1}}$
(164)

Without loss of generality we prove (163). We make use of the fact that the
state and the adversary can also pass the Hadamard test (the other round type
in ${\mathsf{CoPhTest}}$). By (159) the passing probability of Hadamard test
is $\geq 1-2\epsilon_{1}$. By Lemma 6.3 we know $\ket{\tilde{\varphi}^{mid}}$
is claw-free for ${\boldsymbol{K}}^{(combined)}$. Then together with (161) by
Corollary 7.3 there is:

$\displaystyle\Pi_{{\mathsf{pass}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})\ket{\tilde{\varphi}_{0}^{mid}}$
(165) $\displaystyle\approx_{2.5\epsilon_{1}^{1/4}+{\mathsf{negl}}(\kappa)}$
$\displaystyle\Pi_{{\mathsf{pass}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})\ket{\tilde{\varphi}_{1}^{mid}}.$
(166)
$\displaystyle\Pi_{{\mathsf{fail}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})\ket{\tilde{\varphi}_{0}^{mid}}$
(167) $\displaystyle\approx_{2\epsilon_{1}^{1/4}+{\mathsf{negl}}(\kappa)}$
$\displaystyle-\Pi_{{\mathsf{fail}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})\ket{\tilde{\varphi}_{1}^{mid}}.$
(168)

Now we go back to prove (163). The randomization operator operates on client
side registers
${\boldsymbol{\theta}}^{(0)}_{0},{\boldsymbol{\theta}}^{(1)}_{b^{(1)}},\cdots{\boldsymbol{\theta}}^{(L)}_{b^{(L)}}$.
Applying Fact 5 (with details in the box below) we know:

$\displaystyle{\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\Pi_{{\mathsf{pass}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})\ket{\tilde{\varphi}_{0}^{mid}})$
(169) $\displaystyle\approx_{2.5\epsilon_{1}^{1/4}+{\mathsf{negl}}(\kappa)}$
$\displaystyle\ket{\$_{2}}\otimes\Pi_{{\mathsf{pass}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})\ket{\tilde{\varphi}_{1}^{mid}}.$
(170)
$\displaystyle{\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\Pi_{{\mathsf{fail}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})\ket{\tilde{\varphi}_{0}^{mid}})$
(171) $\displaystyle\approx_{2\epsilon_{1}^{1/4}+{\mathsf{negl}}(\kappa)}$
$\displaystyle-\ket{\$_{2}}\otimes\Pi_{{\mathsf{fail}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})\ket{\tilde{\varphi}_{1}^{mid}}.$
(172) Proof of (170): By Lemma 6.5 we have
$\ket{\tilde{\varphi}^{mid}_{0}}\approx_{{\mathsf{negl}}(\kappa)}\sum_{\vec{b}\in
0||\\{0,1\\}^{L}}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}O\circ{\sf
Calc}\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}(\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket)$
(173)
$\ket{\tilde{\varphi}^{mid}_{1}}\approx_{{\mathsf{negl}}(\kappa)}\sum_{\vec{b}\in
1||\\{0,1\\}^{L}}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}O\circ{\sf
Calc}\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}(\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket)$
(174) Then (165)(174) implies, there exists a set of non-negative real values
$t_{\vec{b}}$ for each $\vec{b}\in 0||\\{0,1\\}^{L}$ such that,
$\sum_{\vec{b}}t_{\vec{b}}\leq 2.5\epsilon_{1}^{1/4}$, and for all $\vec{b}$,
$\displaystyle\Pi_{{\mathsf{pass}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})$
$\displaystyle\qquad\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}O\circ{\sf
Calc}\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}(\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket)$
(175) $\displaystyle\approx_{t_{\vec{b}}+{\mathsf{negl}}(\kappa)}$
$\displaystyle\Pi_{{\mathsf{pass}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)};1^{\kappa})$
$\displaystyle\qquad\Pi_{\vec{{\boldsymbol{x}}}_{\vec{1}-\vec{b}}}^{{\boldsymbol{S}}_{smh}}O\circ{\sf
Calc}\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{1}-\vec{b}}}^{{\boldsymbol{S}}_{smh}}(\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket).$
(176) Expanding the operation of
${\mathsf{HadamardTest}}({\boldsymbol{K}}^{(combined)},{\boldsymbol{\Theta}}^{(combined)})$
we get
$\displaystyle\Pi_{{\mathsf{pass}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)};1^{\kappa})$
$\displaystyle\qquad\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}O\circ{\sf
Calc}\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}(\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket\odot({\boldsymbol{\theta}}^{(combined)}_{1}-{\boldsymbol{\theta}}^{(combined)}_{0}))$
(177) $\displaystyle\approx_{t_{\vec{b}}+{\mathsf{negl}}(\kappa)}$
$\displaystyle\Pi_{{\mathsf{pass}}}{\mathsf{HadamardTest}}^{{\mathsf{Adv}}_{HT}\circ
O^{-1}}({\boldsymbol{K}}^{(combined)};1^{\kappa})$
$\displaystyle\qquad\Pi_{\vec{{\boldsymbol{x}}}_{\vec{1}-\vec{b}}}^{{\boldsymbol{S}}_{smh}}O\circ{\sf
Calc}\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{1}-\vec{b}}}^{{\boldsymbol{S}}_{smh}}(\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket\odot({\boldsymbol{\theta}}^{(combined)}_{1}-{\boldsymbol{\theta}}^{(combined)}_{0}))$
(178) and by the condition that $\ket{\varphi}\in{\text{SETUP}}^{3}$ we know
(178) does not depend on the values of registers
${\boldsymbol{\theta}}^{(0)}_{0},{\boldsymbol{\theta}}^{(1)}_{b^{(1)}},\cdots{\boldsymbol{\theta}}^{(L)}_{b^{(L)}}$
for the same
$({\boldsymbol{\theta}}^{(0)}_{0}+\sum_{i\in[L]}{\boldsymbol{\theta}}_{b^{(i)}}^{(i)})$.
(179) Thus applying Fact 5 we get, for each $\vec{b}\in 0||\\{0,1\\}^{L}$,
$\displaystyle{\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\eqref{eq:168dk})$ (180)
$\displaystyle\approx_{t_{\vec{b}}+{\mathsf{negl}}(\kappa)}$
$\displaystyle\ket{\$_{2}}\otimes\eqref{eq:169dk}$ (181) summing up for all
the possible $\vec{b}$, substituting (173)(174) completes the proof of (170).

which implies (163). Similarly we prove (164). Thus we complete the proof of
(162).

Then we port (162) to $\ket{\varphi}$. Recall $\ket{\tilde{\varphi}^{mid}}$ is
defined by

$\ket{\tilde{\varphi}^{mid}}:=O\circ{\sf
Calc}\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}(\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket)$

Starting from (162), apply the inverse of
$O\circ{\mathsf{Response}}\circ{\mathsf{Adv}}_{1}$, we have

${\mathsf{Adv}}^{-1}_{1}{\mathsf{Response}}^{-1}\circ{\sf Calc}^{-1}\circ
O^{-1}({\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\ket{\tilde{\varphi}^{mid}}))\approx_{11\epsilon_{1}^{1/4}+{\mathsf{negl}}(\kappa)}\ket{\$_{2}}\otimes\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket$
(182)
$\Rightarrow\Pi_{{\text{semihonest}}}^{{\boldsymbol{S}}_{smh}}{\mathsf{Adv}}^{-1}_{1}{\mathsf{Response}}^{-1}\circ{\sf
Calc}^{-1}\circ
O^{-1}({\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\Pi_{{\text{semihonest}}}^{{\boldsymbol{S}}_{smh}}\ket{\tilde{\varphi}^{mid}}))\approx_{12\epsilon_{1}^{1/4}+\epsilon_{0}+{\mathsf{negl}}(\kappa)}\ket{\$_{2}}\otimes\ket{\varphi}\odot\llbracket{\mathsf{Combine}}\rrbracket$
(183)

Applying Theorem 6.5 we get

$\displaystyle\Pi_{{\text{semihonest}}}^{{\boldsymbol{S}}_{smh}}{\mathsf{Adv}}^{-1}_{1}{\mathsf{Response}}^{-1}\circ{\sf
Calc}^{-1}\circ
O^{-1}({\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\Pi_{{\text{semihonest}}}^{{\boldsymbol{S}}_{smh}}\ket{\tilde{\varphi}^{mid}}))$
(184) $\displaystyle\approx_{{\mathsf{negl}}(\kappa)}$
$\displaystyle\sum_{\vec{b}\in\\{0,1\\}^{1+L}}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}{\mathsf{Adv}}^{-1}_{1}{\mathsf{Response}}^{-1}\circ{\sf
Calc}^{-1}\circ
O^{-1}({\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}\ket{\tilde{\varphi}^{mid}}))$
(185) $\displaystyle=$
$\displaystyle{\mathcal{R}}_{2}\sum_{\vec{b}\in\\{0,1\\}^{1+L}}\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}({\mathsf{Adv}}^{-1}_{1}{\mathsf{Response}}^{-1}\circ{\sf
Calc}^{-1}\circ
O^{-1}(\ket{\$_{2}}\otimes\Pi_{\vec{{\boldsymbol{x}}}_{\vec{b}}}^{{\boldsymbol{S}}_{smh}}\ket{\tilde{\varphi}^{mid}}))$
(186) $\displaystyle\approx_{{\mathsf{negl}}(\kappa)}$
$\displaystyle{\mathcal{R}}_{2}\Pi_{{\text{semihonest}}}^{{\boldsymbol{S}}_{smh}}({\mathsf{Adv}}^{-1}_{1}{\mathsf{Response}}^{-1}\circ{\sf
Calc}^{-1}\circ
O^{-1}(\ket{\$_{2}}\otimes\Pi_{{\text{semihonest}}}^{{\boldsymbol{S}}_{smh}}\ket{\tilde{\varphi}^{mid}}))$
(187)

where (185)-(186) is because ${\mathcal{R}}_{2}$ applying only on the
$\vec{{\boldsymbol{x}}}_{\vec{b}}$-branch state could be seen as a local
operator ${\sf Add}_{\vec{b}}$ applying on the ${\boldsymbol{\Theta}}$
registers, and thus commutes with operations
${\mathsf{Adv}},{\mathsf{Response}},O$.

(184)-(187) together with (183) implies

${\mathcal{R}}_{2}(\ket{\$_{2}}\otimes\ket{\varphi})\approx_{12\epsilon_{1}^{1/4}+\epsilon_{0}+{\mathsf{negl}}(\kappa)}\ket{\$_{2}}\otimes\ket{\varphi}$

which completes the proof. ∎

##  10 Analysis of the Individual Phase Test (${\mathsf{InPhTest}}$)

In this section we analyze the implication of the individual phase test
(${\mathsf{InPhTest}}$).

  1. 1.

In the first subsection we will give two linear algebra lemmas which are the
basis for later proofs.

  2. 2.

In the second subsection we will show the optimality of OPT for the winning
probability of ${\mathsf{InPhTest}}$. Recall that the OPT is defined to be
$\frac{1}{3}\cos^{2}(\pi/8)$ in Section 5.

  3. 3.

In the third subsection we will show how ${\mathsf{InPhTest}}$ helps us make
progress towards proving the verifiability of ${\mathsf{preRSPV}}$. As
discussed in the introduction, we will show the state is indistinguishable
under the operator ${\mathcal{P}}$ defined later. And the operation of
${\mathcal{P}}$ transforms a pre-phase-honest form to a phase-honest form.

Recall that in the ${\mathsf{InPhTest}}$ the client-side inputs are values of
registers ${\boldsymbol{K}}^{(0)},{\boldsymbol{\Theta}}^{(0)}$. For the
simplicity of current discussions we make ${\boldsymbol{K}}^{(0)}$ implicit
and make ${\boldsymbol{\Theta}}^{(0)}$ explicit. Note that different values of
${\boldsymbol{\Theta}}^{(0)}$ corresponds to different server-side states. In
more detail, when the value of ${\boldsymbol{\Theta}}^{(0)}$ is
$(\theta^{(0)}_{0},\theta^{(0)}_{1})$:

  * •

Honestly, the server should hold
$\frac{1}{\sqrt{2}}(e^{\theta_{0}^{(0)}{\mathrm{i}}\pi/4}\ket{x_{0}^{(0)}}+e^{\theta_{1}^{(0)}{\mathrm{i}}\pi/4}\ket{x_{1}^{(0)}})$.

  * •

In the malicious setting, if we additionally assume the server’s state is
semi-honest and invariant under ${\mathcal{R}}_{1}$ (or equivalently, has been
randomized by ${\mathcal{R}}_{1}$), its state could be written as

$\ket{x_{0}^{(0)}}\ket{\varphi_{0,\theta_{0}^{(0)}}}+\ket{x_{1}^{(0)}}\ket{\varphi_{1,\theta_{1}^{(0)}}}$

And ${\mathsf{InPhTest}}$ aims at testing
$\ket{\varphi_{0,\theta_{0}^{(0)}}}$, $\ket{\varphi_{1,\theta_{1}^{(0)}}}$
satisfy: there exist $\ket{\varphi_{0}},\ket{\varphi_{1}}$ such that

$\text{on average over $\theta_{0},\theta_{1}$, up to a server-side isometry,
for each $b\in\\{0,1\\}$, }\ket{\varphi_{b,\theta_{b}}}\approx
e^{\theta_{b}^{(0)}{\mathrm{i}}\pi/4}\ket{\varphi_{b}}.$ (188)

In more detail, in ${\mathsf{InPhTest}}$ (Protocol 10) for the extra phase
bias of Hadamard test, one of three choices is chosen randomly, which
corresponds to two cases:

  * •

The extra bias is $0,4$: the server is required to make the client output
${\mathsf{pass}}$ in these two tests, which verifies

$\text{on average over $\theta$,
}\ket{\varphi_{0,\theta}}\approx\ket{\varphi_{1,\theta}},\ket{\varphi_{0,\theta+4}}\approx-\ket{\varphi_{1,\theta}}.$
(189)

  * •

The extra bias is $1$: the server is expected to make the client output
${\mathsf{win}}$ to the score register with close-to-optimal winning
probability ($=\frac{1}{3}\cos^{2}(\pi/8)$), which verifies

$\text{on average over $\theta$,
}|\ket{\varphi_{0,\theta}}+\ket{\varphi_{1,\theta+1}}|^{2}\geq{\text{OPT}}-\epsilon$
(190)

These two types of tests, when combined together, will certify the relations
of these states. In the next subsection we first provide the linear algebra
lemmas that support the statement “(189)(190) could verify (188)”.

###  10.1 Linear Algebra Lemmas for Self-testing of State Sequences

First, we have the following lemma which leads to the optimal winning
probability:

######  Lemma 10.1.

Suppose
$\ket{\varphi_{0,0}},\ket{\varphi_{0,1}},\ket{\varphi_{0,2}},\cdots,\ket{\varphi_{0,7}}$,
$\ket{\varphi_{1,0}},\ket{\varphi_{1,1}},\ket{\varphi_{1,2}},\cdots,\ket{\varphi_{1,7}}$
satisfy:

  * •

$\forall i\in\\{0,1\cdots 7\\}$,
$\frac{1}{8}A_{0}-\epsilon\leq|\ket{\varphi_{0,i}}|^{2}\leq\frac{1}{8}A_{0}$,