t_{i\theta}^{\prime}}\lvert v_{t,t^{\prime}}\rangle\Big{\|}$ (124)

Writing $\lvert\psi^{\prime}\rangle=\lvert v_{0}\rangle+\lvert v_{1}\rangle$
where $\lvert v_{0}\rangle=\sum_{t\in(\mathbb{Z}_{2}^{2})^{n}}\lvert
v_{t,t}\rangle$ and $\lvert v_{1}\rangle=\sum_{t\neq t^{\prime}}\lvert
v_{t,t^{\prime}}\rangle$. Then,

$\displaystyle\left\|\lvert v_{1}\rangle\right\|^{2}$
$\displaystyle=\sum_{t\neq
t^{\prime}}\vphantom{v_{t,t^{\prime}}}\left\langle{v_{t,t^{\prime}}}\middle|{v_{t,t^{\prime}}}\right\rangle\leq\sum_{\theta}\sum_{i=1}^{n}\sum_{t_{i\theta}\neq
t^{\prime}_{i\theta}}\vphantom{v_{t,t^{\prime}}}\left\langle\smash{v_{t,t^{\prime}}}\middle|\smash{v_{t,t^{\prime}}}\right\rangle\leq
2n\left[(Ln^{2}+2\sqrt{5})\sqrt{\varepsilon}\right]^{2}.$ (125)

Now, let $\lvert
v_{\beta}\rangle=\sum_{t\in(\mathbb{Z}_{2}^{2})^{n}}(\vphantom{\beta_{t_{1}}}\left\lvert\smash{\beta_{t_{1}}}\middle\rangle\\!\middle\langle\smash{\beta_{t_{1}}}\right\rvert\otimes\cdots\vphantom{\beta_{t_{n}}}\left\lvert\smash{\beta_{t_{n}}}\middle\rangle\\!\middle\langle\smash{\beta_{t_{n}}}\right\rvert)\lvert
v_{t,t}\rangle$, then $\left\|\left\lvert v_{\beta}\right\rangle-\left\lvert
v_{\beta,n}\right\rangle\right\|\leq\|\left\lvert v_{1}\right\rangle\|,$ so

$\displaystyle\begin{split}\|\left\lvert\psi^{\prime}\right\rangle-\left\lvert
v_{\beta}\right\rangle\|&\leq\|\left\lvert\psi^{\prime}\right\rangle-\left\lvert
v_{\beta,n}\right\rangle\|+\|\left\lvert v_{\beta,n}\right\rangle-\left\lvert
v_{\beta}\right\rangle\|\\\
&\leq\left[\tfrac{n}{\sqrt{2}}(Ln^{2}+\sqrt{5}(2+8^{1/4}))+\sqrt{2n}(Ln^{2}+2\sqrt{5})\right]\sqrt{\varepsilon}.\end{split}$
(126)

Now, $\lvert v_{\beta}\rangle$ has the form we want, but it may not be
normalised. Define $\lvert\phi\rangle=\frac{\lvert
v_{\beta}\rangle}{\left\|\lvert v_{\beta}\rangle\right\|}$. We have

$\displaystyle\left\|\lvert\phi\rangle-\lvert
v_{\beta}\rangle\right\|=\left\|\lvert\psi^{\prime}\rangle\right\|-\left\|\lvert
v_{\beta}\rangle\right\|\leq\left\|\lvert\psi^{\prime}\rangle-\lvert
v_{\beta}\rangle\right\|,$ (127)

giving

$\displaystyle\|\left\lvert\psi^{\prime}\right\rangle-\left\lvert\phi\right\rangle\|\leq
2\|\left\lvert\psi^{\prime}\right\rangle-\left\lvert
v_{\beta}\right\rangle\|\leq\sqrt{2}\left[n(Ln^{2}+\sqrt{5}(2+8^{1/4}))+2\sqrt{n}(Ln^{2}+2\sqrt{5})\right]\sqrt{\varepsilon}$
(128)

∎

We can, as in the single-round case, generalise this result slightly to a
general strategy.

######  Corollary 4.8.

Let $n\in\mathbb{N}$ and let
$\texttt{S}=\left\lparen\textsf{B},\textsf{C},B,C,\rho\right\rparen$ be an
arbitrary strategy for $\texttt{TFKW}^{n}$. Suppose that for some
$\varepsilon\geq 0$, for each $i\in[n]$, the $i$-th game wins with probability
$\mathfrak{w}_{\texttt{TFKW}^{n}}^{i}(\texttt{S})\geq\cos^{2}\tfrac{\pi}{8}-\varepsilon$.
Then there exists a constant $K\geq 0$ and isometries
$V:\textsf{B}\rightarrow\textsf{B}^{\prime}$ and
$W:\textsf{C}\rightarrow\textsf{C}^{\prime}$ such that

$\displaystyle\left\|(V\otimes W)\rho(V\otimes
W)^{\dagger}-\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)\right\|_{\operatorname{Tr}}\leq
Kn^{3}\sqrt{\varepsilon},$ (129)

where $R$ is an auxiliary register such that

$\displaystyle\lvert\phi\rangle=\sum_{t\in(\mathbb{Z}_{2}^{2})^{n}}X^{t_{10}}Z^{t_{11}}\lvert\beta\rangle\otimes\cdots\otimes
X^{t_{n0}}Z^{t_{n1}}\lvert\beta\rangle\otimes\lvert\psi_{t}\rangle$ (130)

for some vectors
$\lvert\psi_{t}\rangle\in\textsf{B}^{\prime}\otimes\textsf{C}^{\prime}\otimes\textsf{R}$
with orthogonal supports on both $\textsf{B}^{\prime}$ and
$\textsf{C}^{\prime}$.

The proof follows the same method as Corollary 4.3.

###  4.6 Observed Statistics

In any self-testing scenario, the referee cannot actually query the winning
probability of the adversaries’ strategy. To get around this, she may play
many rounds of the game in parallel and use the players’ winning statistics to
approximate their winning probability. The difficulty that arises, however, is
that the players’ strategies need not be independent for the different rounds
of the game, and therefore the information Alice receives might not be
meaningful. A technique of [RUV13] allows us to get around this: first, we
bound the probability of winning too many of the games if enough are too far
from optimal, and then find good values of the bounding constants, depending
on the application, so Alice may extract information about the state.

######  Lemma 4.9.

Let $0<\varepsilon,\eta<1$ and let $\delta\in\mathbb{R}$ such that
$\delta\leq\eta\varepsilon$. Let S be a strategy for $\texttt{TFKW}^{n}$. Let
$E\subseteq\\{0,\ldots,n\\}$ be the set of rounds $i$ such that
$\mathfrak{w}_{\texttt{TFKW}^{n}}^{i}(\texttt{S})\geq\cos^{2}\tfrac{\pi}{8}-\varepsilon$,
and let $W\in\\{0,\ldots,n\\}$ be the number of rounds the adversaries win.
Then, if $|E|<(1-\eta)n$,

$\displaystyle\Pr\left\lparen
W\geq(\cos^{2}\tfrac{\pi}{8}-\delta)n\right\rparen\leq
e^{-2n(\eta\varepsilon-\delta)^{2}}.$ (131)

We can make use of this in contrapositive. That is, other than with small
probability, if the adversaries win at least
$(\cos^{2}\tfrac{\pi}{8}-\delta)n$ games, then at least $(1-\eta)n$ of the
games win with near-optimal winning probability. The proof proceeds in the
same way as a similar result for sequentially repeated games in [RUV13].

###### Proof.

Write $w^{\ast}=\cos^{2}\tfrac{\pi}{8}$ for convenience. Let $W_{i}$ be the
random variable that is $1$ if the adversaries won round $i$ and $0$ if they
lost. Then, we have that $W$ is the random variable $W=\sum_{i=1}^{n}W_{i}$.
Since $\Pr(W_{i}=1)=\mathfrak{w}_{\texttt{TFKW}^{n}}^{i}(\texttt{S})$, if
$i\in E$, we know that $\Pr(W_{i}=1)\leq w^{\ast}$, and if $i\notin E$,
$\Pr(W_{i}=1)\leq w^{\ast}-\varepsilon.$ Let
$\Gamma_{1},\ldots,\Gamma_{n},\Lambda_{1},\ldots,\Lambda_{n}$ be independent
Bernoulli variables such that the $\Pr(\Gamma_{i}=1)=w^{\ast}$ and
$\Pr(\Lambda_{i}=1)=w^{\ast}-\varepsilon$. By the above, we can couple them to
the $W_{i}$ so that $W_{i}\leq\Gamma_{i}$ if $i\in E$ and
$W_{i}\leq\Lambda_{i}$ is $i\notin E$. This implies directly that
$W\leq\sum_{i\in E}\Gamma_{i}+\sum_{i\notin E}\Lambda_{i}$, so

$\displaystyle\Pr(W\geq(w^{\ast}-\delta)n)\leq\Pr\Big{\lparen}\sum_{i\in
E}\Gamma_{i}+\sum_{i\notin E}\Lambda_{i}\geq(w^{\ast}-\delta)n\Big{\rparen}.$
(132)

Since $\mathbb{E}\Big{\lparen}\sum_{i\in E}\Gamma_{i}+\sum_{i\notin
E}\Lambda_{i}\Big{\rparen}=|E|w^{\ast}+(n-|E|)(w^{\ast}-\varepsilon)$,
Hoeffding’s inequality implies

$\displaystyle Pr(W\geq(w^{\ast}-\delta)n)\leq
e^{-\frac{2}{n}((n-|E|)\varepsilon-\delta n)^{2}}\leq
e^{-2n(\eta\varepsilon-\delta)^{2}}$ (133)

∎

A simple canonical choice of variables for large $n$ is
$\varepsilon=\eta=\delta=\frac{1}{n^{1/4}}$, which allows Alice to test sets
of $k\sim n^{1/25}$ parallel rounds, where she is able say that the state is
$\sim\frac{1}{k^{1/8}}$ near-optimal for those rounds with probability
exponentially close to $1$ in $k$.

In view of applications, we give in Theorem 4.10 a version of Corollary 4.8
where Alice has less information about the winning probabilities of the
strategy. Rather than assuming that she knows that they win each round near-
optimally, we will assume that Alice only knows with high probability that
each round wins near-optimally. Then, we are able to ascertain the behaviour
of the shared state in expectation. This will allow us to directly apply the
result of Lemma 4.9 to get conclusions about the rigidity of the state.

######  Theorem 4.10.

Let $n\in\mathbb{N}$ and let
$\texttt{S}=\left\lparen\textsf{B},\textsf{C},B,C,\rho\right\rparen$ be a
strategy for $\texttt{TFKW}^{n}$. Suppose that for some
$\varepsilon,\eta\in[0,1]$, for each $i\in[n]$, there is a probability
$1-\eta$ that the $i$-th game wins with probability
$\mathfrak{w}_{\texttt{TFKW}^{n}}^{i}(\texttt{S})\geq\cos^{2}\tfrac{\pi}{8}-\varepsilon$.
Then, there exists a constant $K\geq 0$, Hilbert spaces $\textsf{B}^{\prime}$
and $\textsf{C}^{\prime}$, and isometries
$V:\textsf{B}\rightarrow\textsf{B}^{\prime}$ and
$W:\textsf{C}\rightarrow\textsf{C}^{\prime}$ such that the expected value of
the distance between quantum states

$\displaystyle\mathbb{E}\left\|(V\otimes W)\rho(V\otimes
W)^{\dagger}-\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)\right\|\leq
Kn^{3}\sqrt{\varepsilon}+n\eta,$ (134)

where
$\lvert\phi\rangle=\sum_{t\in(\mathbb{Z}_{2}^{2})^{n}}X^{t_{10}}Z^{t_{11}}\lvert\beta\rangle\otimes\cdots\otimes
X^{t_{n0}}Z^{t_{n1}}\lvert\beta\rangle\otimes\lvert\psi_{t}\rangle$ for some
auxiliary register $R$ and
$\lvert\psi_{t}\rangle\in\textsf{B}^{\prime}\otimes\textsf{C}^{\prime}\otimes\textsf{R}$
with orthogonal supports on both $\textsf{B}^{\prime}$ and
$\textsf{C}^{\prime}$.

###### Proof.

For each $i\in[n]$, let $H_{i}$ be the random variable indicating if
$\mathfrak{w}_{\texttt{TFKW}^{n}}^{i}(\texttt{S})\geq\cos^{2}\tfrac{\pi}{8}-\varepsilon$.
We have $\Pr(H_{i}=1)=1-\eta$. Let $H\subseteq[n]$ be the register-valued
random variable such that $i\in H$ if and only if $H_{i}=1$; let
$L=[n]\backslash H$ be the complement. Since for any round in $H$,
$\mathfrak{w}_{\texttt{TFKW}^{n}}^{i}(\texttt{S})\geq\cos^{2}\tfrac{\pi}{8}-\varepsilon$,
we can apply the rigidity of Corollary 4.8 to those rounds. Then, there exists
a constant $K\geq 0$, Hilbert spaces $\textsf{B}^{\prime}$ and
$\textsf{C}^{\prime}$, isometries $V:\textsf{B}\rightarrow\textsf{B}^{\prime}$
and $W:\textsf{C}\rightarrow\textsf{C}^{\prime}$, and a state
$\lvert\phi\rangle\in\textsf{A}_{H}\otimes\textsf{A}_{L}\otimes\textsf{B}^{\prime}\otimes\textsf{C}^{\prime}\otimes\textsf{R}$
of the form
$\lvert\phi\rangle=\sum_{t\in(\mathbb{Z}_{2}^{2})^{|H|}}\lvert\beta_{t}\rangle_{A_{H}}\otimes\lvert\psi_{t}\rangle\in\textsf{A}\otimes\textsf{B}^{\prime}\otimes\textsf{C}^{\prime}\otimes\textsf{R}$
where the supports of the
$\lvert\psi_{t}\rangle\in\textsf{A}_{L}\otimes\textsf{B}^{\prime}\otimes\textsf{C}^{\prime}\otimes\textsf{R}$
on both $\textsf{B}^{\prime}$ and $\textsf{C}^{\prime}$ are orthogonal such
that

$\displaystyle\left\|(V\otimes W)\rho(V\otimes
W)^{\dagger}-\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)\right\|_{\operatorname{Tr}}\leq
K|H|^{3}\sqrt{\varepsilon}\leq Kn^{3}\sqrt{\varepsilon}.$ (135)

Let
$\sigma=\vphantom{\beta}\left\lvert\smash{\beta}\middle\rangle\\!\middle\langle\smash{\beta}\right\rvert^{\otimes
L}_{A_{L}}\otimes\operatorname{Tr}_{A_{L}R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)$.
Then, $\sigma$ has the form we want and
$\|\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)-\sigma\|\leq
n-|H|$, giving that
$\mathbb{E}\|\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)-\sigma\|\leq
n-\mathbb{\sum}_{i}H_{i}=n\eta$. Using the triangle inequality, we get the
wanted result. ∎

We give an example of the use of the results of this section by considering an
explicit choice of parameters.

######  Example 4.11.

Fix some large $n\in\mathbb{N}$. Take $\varepsilon=n^{-8}$, $\eta=n^{-2}$, and
$\delta=\frac{1}{2}n^{-10}$. Suppose Alice plays $N=n^{21}$ rounds of the TFKW
game in parallel with Bob and Charlie, and that the players are able to win at
least $\cos^{2}\frac{\pi}{8}N-\frac{1}{2}n^{11}$ of them. Then Lemma 4.9
implies that, other than with probability $e^{-\frac{n}{2}}$, there are at
least $(1-n^{-2})N$ rounds that won with probability
$\mathfrak{w}_{\texttt{TFKW}^{n}}^{i}(\texttt{S})\geq\cos^{2}\tfrac{\pi}{8}-n^{-8}$.
Then Alice can check the rigidity on $n$ rounds chosen uniformly at random:
call this register $A^{\prime}$. Due to the uniform randomness, each of the
$n$ has probability $1-n^{-2}$ of being within $n^{-8}$ of optimal. Then, we
can use the rigidity of Theorem 4.10 to say that there exists a constant
$K\geq 0$, Hilbert spaces $\textsf{B}^{\prime}$ and $\textsf{C}^{\prime}$, and
isometries $V:\textsf{B}\rightarrow\textsf{B}^{\prime}$ and
$W:\textsf{C}\rightarrow\textsf{C}^{\prime}$ such that the expected value of
the distance between quantum states

$\displaystyle\mathbb{E}\left\|(V\otimes W)\rho_{A^{\prime}BCR}(V\otimes
W)^{\dagger}-\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)\right\|\leq\frac{K+1}{n},$
(136)

where
$\lvert\phi\rangle=\sum_{t\in(\mathbb{Z}_{2}^{2})^{n}}X^{t_{10}}Z^{t_{11}}\lvert\beta\rangle\otimes\cdots\otimes
X^{t_{n0}}Z^{t_{n1}}\lvert\beta\rangle\otimes\lvert t\rangle_{BCR}$ for some
auxiliary register $R$ and $\lvert
t\rangle_{BCR}\in\textsf{B}^{\prime}\otimes\textsf{C}^{\prime}\otimes\textsf{R}$
with orthogonal supports on both $\textsf{B}^{\prime}$ and
$\textsf{C}^{\prime}$.

##  5 Applications

In this section, we present applications of our rigidity result. In Section
5.1, we introduce further definitions and techniques we will need in this
section. In Section 5.2, we construct a three-party weak string erasure
scheme. In Section 5.3, we discuss bit commitment constructed from this weak
string erasure scheme, and contrast our model with prev0ious three-party
models. In Section 5.4, we construct a everlasting randomness expansion
protocol in a model closely following the model for MoE games, that requires
temporary computational assumptions but no entanglement.

###  5.1 Preliminaries and Notation

A _classical-quantum state_ (cq) is a state
$\rho_{XH}\in\mathcal{D}(\textsf{X}\otimes\textsf{H})$ that takes the form

$\displaystyle\rho_{XH}=\sum_{x\in
X}p_{x}\vphantom{x}\left\lvert\smash{x}\middle\rangle\\!\middle\langle\smash{x}\right\rvert_{X}\otimes\rho^{x}_{H},$
(137)

where $p_{x}\geq 0$, $\sum_{x}p_{x}=1$, and the
$\rho^{x}_{H}\in\mathcal{D}(\textsf{H})$ are quantum states. As the part of
the state on the register $X$ is diagonal in the canonical basis, we consider
that as a classical register. Since classical information may be cloned, we
may write the ccq state with the classical part duplicated as

$\displaystyle\rho_{XXH}=\sum_{x\in
X}p_{x}\vphantom{x}\left\lvert\smash{x}\middle\rangle\\!\middle\langle\smash{x}\right\rvert\otimes\vphantom{x}\left\lvert\smash{x}\middle\rangle\\!\middle\langle\smash{x}\right\rvert\otimes\rho^{x}_{H}\in\mathcal{D}(\textsf{X}\otimes\textsf{X}\otimes\textsf{H}).$
(138)

If a quantum register decomposes as a product $H=H_{1}\times\cdots\times
H_{n}$, for any set $\iota=\\{i_{1},\ldots,i_{k}\\}\subseteq[n]$ with
$i_{1}<\ldots<i_{k}$ and state $\rho_{H}\in\mathcal{D}(\textsf{H})$, write

$\displaystyle\rho_{H_{\iota}}=\rho_{H_{i_{1}}\cdots
H_{i_{k}}}\in\mathcal{D}(\textsf{H}_{\iota})=\mathcal{D}(\textsf{H}_{i_{1}}\otimes\cdots\otimes\textsf{H}_{i_{k}}).$
(139)

Finally, for a cq state
$\rho_{IH}\in\mathcal{D}(\textsf{I}\otimes\textsf{H})$, where $I=P([n])$ the
power set, write

$\displaystyle\rho_{IH_{I}}=\sum_{\iota\in
I}p_{\iota}\vphantom{\iota}\left\lvert\smash{\iota}\middle\rangle\\!\middle\langle\smash{\iota}\right\rvert\otimes\rho^{\iota}_{H_{\iota}}\in\mathcal{D}\left\lparen\bigoplus_{\iota\in
I}\lvert\iota\rangle\otimes\textsf{H}_{\iota}\right\rparen\subseteq\mathcal{D}(\textsf{I}\otimes\textsf{H}).$
(140)

We also want to be able to estimate the uncertainty of a register given
another. This is done using the _conditional min-entropy_ : for
$\rho_{HK}\in\mathcal{D}(\textsf{H}\otimes\textsf{K})$, the uncertainty of $H$
knowing $K$ is

$\displaystyle
H_{\mathrm{min}}(H|K)_{\rho}=-\lg\inf\vphantom{\operatorname{Tr}(\sigma_{K})\rho_{HK}\leq\mathbb{I}_{H}\otimes\sigma_{K},\sigma_{K}\in\mathcal{P}(\textsf{K})}\left\\{{\operatorname{Tr}(\sigma_{K})}\middle|{\rho_{HK}\leq\mathbb{I}_{H}\otimes\sigma_{K},\sigma_{K}\in\mathcal{P}(\textsf{K})}\right\\}.$
(141)

Importantly, if $\rho$ is classical on H, $2^{-H_{\mathrm{min}}(H|K)_{\rho}}$
corresponds exactly to the probability of guessing $H$ when holding $K$. The
robust version of this entropy is the _smooth min-entropy_. For
$\varepsilon>0$,

$\displaystyle
H^{\varepsilon}_{\mathrm{min}}(H|K)_{\rho}=\sup\vphantom{H_{\mathrm{min}}(H|K)_{\sigma}\sigma\in\mathcal{P}(\textsf{H}\otimes\textsf{K}),\|\rho-\sigma\|_{\operatorname{Tr}}\leq\operatorname{Tr}(\rho)\varepsilon,\operatorname{Tr}(\sigma)\leq\operatorname{Tr}(\rho)}\left\\{{H_{\mathrm{min}}(H|K)_{\sigma}}\middle|{\sigma\in\mathcal{P}(\textsf{H}\otimes\textsf{K}),\|\rho-\sigma\|_{\operatorname{Tr}}\leq\operatorname{Tr}(\rho)\varepsilon,\operatorname{Tr}(\sigma)\leq\operatorname{Tr}(\rho)}\right\\}.$
(142)

For more information, see [Tom16].

Generally, the evolution of a quantum system is given by a quantum channel,
which subsumes both measurements and unitary evolution. A quantum channel is
represented by a completely positive trace-preserving (CPTP) map, which is a
linear map $\Phi:\mathcal{L}(\textsf{H})\rightarrow\mathcal{L}(\textsf{K})$
such that, for any Hilbert space Z and any
$P\in\mathcal{P}(\textsf{Z}\otimes\textsf{H})$,
$(\mathbb{I}_{Z}\otimes\Phi)(P)\geq 0$; and
$\operatorname{Tr}(\Phi(L))=\operatorname{Tr}(L)$ for all
$L\in\mathcal{L}(\textsf{H})$. The partial trace provides an example of a
quantum channel.

We write the orthonormal basis that diagonalises the Pauli $Y$ matrix as
$\lvert 0_{\circlearrowleft}\rangle=\frac{1}{\sqrt{2}}(\lvert 0\rangle+i\lvert
1\rangle)$ and $\lvert 1_{\circlearrowleft}\rangle=\frac{1}{\sqrt{2}}(\lvert
0\rangle-i\lvert 1\rangle)$. Then,
$Y=\vphantom{0_{\circlearrowleft}}\left\lvert\smash{0_{\circlearrowleft}}\middle\rangle\\!\middle\langle\smash{0_{\circlearrowleft}}\right\rvert-\vphantom{1_{\circlearrowleft}}\left\lvert\smash{1_{\circlearrowleft}}\middle\rangle\\!\middle\langle\smash{1_{\circlearrowleft}}\right\rvert$.

A function $f:\mathbb{N}\rightarrow[0,\infty)$ is called _negligible_ if, for
every polynomial $p$, $p(n)f(n)\rightarrow 0$ as $n\rightarrow\infty$. Write
$\texttt{negl}(n)$ for the set of negligible functions in $n$; abusing
notation a bit, we will also write $\texttt{negl}(n)$ to represent some
function taken from the set.

###  5.2 Weak String Erasure

Weak string erasure (WSE) is a fundamental cryptographic primitive, introduced
in [KWW12]. It is a simple yet powerful way to share partial information
between a sender Alice and a receiver Bob. A WSE protocol provides Alice with
a random string $x\in\mathbb{Z}_{2}^{n}$, and Bob with a string
$\hat{x}\in\mathbb{Z}_{2}^{n}$ and a subset $\iota\subseteq[n]$ such that
$|\iota|$ is on average $n/2$. The strings satisfy the property that they are
equal on the positions indexed by the elements of $\iota$:
$x_{\iota}=\hat{x}_{\iota}$. Security for such a scheme consists of Alice
being unable to guess which substring of $x$ Bob knows, while Bob is unable to
guess the remaining bits of $x$, _i.e._ the substring $x_{\iota^{c}}$. WSE was
used in [KWW12] to create bit commitment and oblivious transfer schemes. In
their construction of a BC scheme, the roles of the sender and the receiver
are preserved: the string Alice commits to is the image of her WSE output $x$
by a randomness extractor, and in the reveal phase, Bob uses the part of the
string he knows $x_{\iota}$ to verify that Alice had in fact committed to this
string. Hence, however, since bit commitment is impossible with no additional
assumptions [BS16], WSE needs some assumptions about the model to hold.
Accordingly, [KWW12] used a quantum noisy-storage model to achieve it,
generalising results on bounded quantum storage used to achieve oblivious
transfer [DFSS08]. We formally define security for WSE in the original two-
party model.

######  Definition 5.1 ([KWW12]).

A _$(n,\lambda,\varepsilon)$ -weak string erasure (WSE) scheme_ is a protocol
between two parties, Alice and Bob, that creates a state $\rho_{XAI\hat{X}B}$,
where $X$, $I$, and $\hat{X}$ are classical registers such that
$X=\mathbb{Z}_{2}^{n}$ holds string $x$, $\hat{X}=\mathbb{Z}_{2}^{n}$ holds
Bob’s guess of $x$, and $I=P([n])$ holds $\iota$; and $A$ and $B$ are optional
quantum registers corresponding to Alice and Bob’s remaining quantum states.
The scheme must satisfy _correctness_ , and _security_ for both Alice and Bob:

Correctness: If both Alice and Bob are honest then
$\rho_{XI\hat{X}_{I}}=\rho_{XIX_{I}}$ and $\rho_{XI}=\mu_{X}\otimes\mu_{I}$.

Security for Alice: If Alice is honest
$H^{\varepsilon}_{\mathrm{min}}(X|B)_{\rho}\geq\lambda n$.

Security for Bob: If Bob is honest, $\rho_{AI}=\rho_{A}\otimes\mu_{I}$ in the
event that Alice does not abort.

We say that a protocol is a _$(n,\lambda,\varepsilon)$ -WSE scheme that fails
with probability $p$_ if any one of the three conditions does not hold with
probability at most $p$.

Here, we show WSE in an alternative model. Instead of resorting to limitations
on the quantum devices of parties, we add an additional dishonest prover,
Charlie, who colludes with the receiver.222Note that oblivious transfer in yet
another three-party model has been considered before. In [YXTZ14], they
consider a model where an untrusted third party prepares entangled states for
Alice and Bob to use. However, they make use of much stronger assumptions: the
third party produces each state identically and independently, Alice and Bob
need to cooperate to verify that these states are correct before running the
protocol, and the third party does not collude with any of the other parties.
Instead of the storage limitation, we place restrictions on the
communications: the prover is not allowed to communicate with the receiver,
and the sender is required to communicate by publicly broadcasting. The former
restriction helps an honest sender constrain the action of a dishonest
receiver; the latter condition blocks a subtle cheating method of a dishonest
sender, where she attempts to extract different information from the receiver
and the prover.

######  Definition 5.2.

A WSE scheme in the _three-party model_ consists of a sender, Alice, a
receiver, Bob, and a prover, Charlie. It satisfies the following:

  * •

Charlie is dishonest if and only if Bob is dishonest.

  * •

Alice communicates by publicly broadcasting.

  * •

Bob and Charlie are isolated from each other once Alice starts broadcasting.

In this model, there is an additional prover Charlie, so the state takes the
form $\rho_{XAI\hat{X}BC}$, where $C$ is an additional register held by
Charlie. If he is dishonest, he should not be able to get more information out
of the protocol than his collaborator, Bob. Thus, we require that the security
for Alice from Definition 5.1 is satisfied with respect to either Bob or
Charlie’s registers. We state this formally.

######  Definition 5.3.

A _$(n,\lambda,\varepsilon)$ -WSE scheme in the three-party model_ is a
protocol that produces a shared state $\rho_{XAI\hat{X}BC}$ such that it is a
two-party scheme for Alice and Bob, and the security for Alice is symmetric:

Two-party WSE: $\rho_{XAI\hat{X}B}$, the state with Charlie’s register traced
out, satisfies Definition 5.1.

Symmetric security for Alice: If Alice is honest
$H^{\varepsilon}_{\mathrm{min}}(X|C)\geq\lambda n$.

For our protocol in this model, as Bob colludes with Charlie but may not
communicate with him, an honest sender exploits the rigidity of the TFKW game
to constrain their actions. Note that Charlie needs to remain out of the reach
of Bob’s communications for as long as Bob is using his output data in order
for it to stay secure. Since Alice must broadcast publicly, Bob and Charlie
will receive the same TFKW game questions even if she is dishonest.

Now, we formally present our protocol.

######  Protocol 5.4 (three-party weak string erasure).

1. Bob prepares the shared state ${}^{\otimes N}\lvert x^{\varphi}\rangle_{A}\otimes\lvert x\varphi\rangle_{B}\otimes\lvert x\varphi\rangle_{C}$ for $x,\varphi\in\mathbb{Z}_{2}^{N}$ chosen uniformly at random. Bob and Charlie are then no longer allowed to communicate. 2. Alice chooses a set of $n$ indices $J\subseteq[N]$ and a string $\theta\in\mathbb{Z}_{2}^{N}$ uniformly at random. She measures each of her qubits $1\leq i\leq N$ in basis $\\{\lvert 0^{\theta_{i}}\rangle,\lvert 1^{\theta_{i}}\rangle\\}$ if $i\notin J$ and in basis $\\{\be\lvert 0^{\theta_{i}}\rangle,\be\lvert 1^{\theta_{i}}\rangle\\}$ if $i\in J$. This produces a string $y\in\mathbb{Z}_{2}^{N}$ that she keeps; and she broadcasts $J$ and $\theta$. 3. Bob and Charlie, without communicating, each measure their subspaces to get strings corresponding to their optimal guess at the TFKW game on $J^{c}$, $y^{B}=y^{C}=x+1^{J^{c}}\land\theta\land\varphi\in\mathbb{Z}_{2}^{N}$, and they then send $y^{B}_{J^{c}}$ and $y^{C}_{J^{c}}$, respectively, to Alice. 4. Alice checks if her string everywhere but the index set, $y_{J^{c}}$, matches $y^{B}_{J^{c}}$ and $y^{C}_{J^{c}}$ simultaneously on at least $(\cos^{2}\frac{\pi}{8}-\delta)N$ bits. If it does not, she aborts. 5. Alice takes as output $y_{J}$, and Bob takes as output the set $\iota(\theta,\varphi)\subseteq J$ where the bits of $\theta$ and $\varphi$ match, and the string $y^{B}_{J}$.

In Fig. 3, we give a setup for our WSE scheme, where we see that the single
round of communication makes it possible to devise a way to run the protocol
relativistically.

Sender (Alice)$J,\theta$Prover (Charlie)$y^{C}_{J^{c}}$Receiver
(Bob)$y^{B}_{J^{c}}$$y_{J}$$y^{B}_{J},\iota(\theta,\varphi)$$\Delta
t/2$$\Delta t/2$ Figure 3: A setup for the three-party weak string erasure
scheme 5.4. The parties communicate by broadcasting publicly, and as there is
only one round of communication, the spacelike separation between Bob and
Charlie ensures they do not communicate in the time $\Delta t$ needed to run
the protocol.

Note that the protocol requires no quantum storage to run honestly by
considering it in a prepare-and-measure way. That is, Alice may come up with
the random $\theta$ and $J$ before Bob prepares the state, measure her
register one qubit at a time as soon she receives it from Bob, and only reveal
$\theta$ and $J$ once she knows that Bob and Charlie are no longer
communicating. Since her measurements are local, this has the same effect on
the state as if she waited until Bob and Charlie finish communicating to make
her measurements.

To illustrate the protocol, we consider in more detail the case where the
players are honest. Bob should prepare some unentangled optimal state for the
TFKW game uniformly at random:

$\displaystyle\rho_{ABC}$
$\displaystyle=\underset{x,\varphi\in\mathbb{Z}_{2}^{N}}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}{}^{\otimes
N}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert_{A}{}^{\otimes
N}\otimes\vphantom{x\varphi}\left\lvert\smash{x\varphi}\middle\rangle\\!\middle\langle\smash{x\varphi}\right\rvert_{B}\otimes\vphantom{x\varphi}\left\lvert\smash{x\varphi}\middle\rangle\\!\middle\langle\smash{x\varphi}\right\rvert_{C}.$
(143)

Alice then comes up with uniformly random $\theta$ and $J$ and makes her
measurements, so the state becomes

$\displaystyle\rho_{YBC}$
$\displaystyle=\underset{x,\varphi,\theta,J}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{y}\left\lvert\vphantom{y^{\theta}{}^{1^{J^{c}}}x^{\varphi}}\left\langle\smash{y^{\theta}}\middle\rvert\smash{{}^{1^{J^{c}}}}\middle\rvert\smash{x^{\varphi}}\right\rangle\right\rvert^{2}\vphantom{y}\left\lvert\smash{y}\middle\rangle\\!\middle\langle\smash{y}\right\rvert_{Y}\otimes\vphantom{x\varphi\theta
J}\left\lvert\smash{x\varphi\theta
J}\middle\rangle\\!\middle\langle\smash{x\varphi\theta
J}\right\rvert_{B}\otimes\vphantom{x\varphi\theta
J}\left\lvert\smash{x\varphi\theta
J}\middle\rangle\\!\middle\langle\smash{x\varphi\theta J}\right\rvert_{C}.$
(144)

Now, the honest Bob measures his register in the computational basis and gets
full information about $x$ and $\varphi$. Knowing $J$, Bob sends
$y^{B}_{J^{c}}=x_{J^{c}}+\theta_{J^{c}}\land\varphi_{J^{c}}$ corresponding to
his best guess of $y$ in the TFKW game, and keeps $y^{B}_{J}=x_{J}$ to
himself. Charlie does the same and sends $y^{C}_{J^{c}}=y^{B}_{J^{c}}$ to
Alice. Bob and Charlie win at each copy of TFKW with probability exactly
$\cos^{2}\frac{\pi}{8}$, so with overwhelming probability for large $N$, they
do not cause Alice to abort. Assuming the protocol does not abort, Bob defines
$\iota(\theta,\varphi)\subseteq(\mathbb{Z}_{2}^{N})_{J}=\mathbb{Z}_{2}^{n}$ as
the set $\iota(\theta,\varphi)=\vphantom{i\in
J\theta_{i}=\varphi_{i}}\left\\{\smash{i\in
J}\middle|\smash{\theta_{i}=\varphi_{i}}\right\\}$. Alice and Bob have no use
for $x_{J^{c}}$, $\varphi$, $y_{J^{c}}$, $\theta$, and $J$ and may forget
them. Alice calls her remaining register $X$ and Bob calls his remaining
registers $I$ and $\hat{X}$, so the state becomes

$\displaystyle\rho_{XI\hat{X}C}=\underset{x,\varphi,\theta,J}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{y_{J}}\left\lvert\vphantom{y_{J}H^{\theta_{J}+\varphi_{J}}x_{J}}\left\langle\smash{y_{J}}\middle\rvert\smash{H^{\theta_{J}+\varphi_{J}}}\middle\rvert\smash{x_{J}}\right\rangle\right\rvert^{2}\vphantom{y_{J}}\left\lvert\smash{y_{J}}\middle\rangle\\!\middle\langle\smash{y_{J}}\right\rvert_{X}\otimes\vphantom{\iota(\theta,\varphi)}\left\lvert\smash{\iota(\theta,\varphi)}\middle\rangle\\!\middle\langle\smash{\iota(\theta,\varphi)}\right\rvert_{I}\otimes\vphantom{x_{J}}\left\lvert\smash{x_{J}}\middle\rangle\\!\middle\langle\smash{x_{J}}\right\rvert_{\hat{X}}\otimes\rho_{C}^{x,\varphi,\theta,J},$
(145)

where each $\rho_{C}^{x,\varphi,\theta,J}$ is a quantum state representing
what Charlie continues to hold, but the structure of this state is
unimportant. From the coefficients
$\left\lvert\vphantom{y_{J}H^{\theta_{J}+\varphi_{J}}x_{J}}\left\langle\smash{y_{J}}\middle\rvert\smash{H^{\theta_{J}+\varphi_{J}}}\middle\rvert\smash{x_{J}}\right\rangle\right\rvert^{2}=\left\lvert\vphantom{y_{J}H^{1^{\iota(\theta,\varphi)^{c}}}x_{J}}\left\langle\smash{y_{J}}\middle\rvert\smash{H^{1^{\iota(\theta,\varphi)^{c}}}}\middle\rvert\smash{x_{J}}\right\rangle\right\rvert^{2}$,
we see that $(y_{J})_{i}=(x_{J})_{i}$ for $i\in\iota(\theta,\varphi)$ while
for $i\notin\iota(\theta,\varphi)$, $(x_{J})_{i}$ is uniformly random with
respect to $(y_{J})_{i}$. Therefore, Alice holds the string $y_{J}$, Bob has
the substring $(y_{J})_{\iota(\theta,\varphi)}$ and full information about
where in the string they are found, but Bob has no information about the
remaining bits. Formally, this gives correctness of the protocol.

######  Lemma 5.5.

5.4 is correct as a WSE scheme.

###### Proof.

We need to show that $\rho_{XI}=\mu_{X}\otimes\mu_{I}$ and
$\rho_{XIX_{I}}=\rho_{XI\hat{X}_{I}}$ for honest Alice and Bob. By the above
argument,

$\displaystyle\rho_{XI\hat{X}}=\underset{x,\varphi,\theta,J}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{\begin{subarray}{c}y_{J}\\\
(y_{J})_{\iota(\theta,\varphi)}=\\\
(x_{J})_{\iota(\theta,\varphi)}\end{subarray}}\frac{1}{2^{|\theta_{J}+\varphi_{J}|}}\vphantom{y_{J}}\left\lvert\smash{y_{J}}\middle\rangle\\!\middle\langle\smash{y_{J}}\right\rvert_{X}\otimes\vphantom{\iota(\theta,\varphi)}\left\lvert\smash{\iota(\theta,\varphi)}\middle\rangle\\!\middle\langle\smash{\iota(\theta,\varphi)}\right\rvert_{I}\otimes\vphantom{x_{J}}\left\lvert\smash{x_{J}}\middle\rangle\\!\middle\langle\smash{x_{J}}\right\rvert_{\hat{X}},$
(146)

and therefore

$\displaystyle\rho_{XI}=\underset{y_{J},\varphi,\theta,J}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\vphantom{y_{J}}\left\lvert\smash{y_{J}}\middle\rangle\\!\middle\langle\smash{y_{J}}\right\rvert_{X}\otimes\vphantom{\iota(\theta,\varphi)}\left\lvert\smash{\iota(\theta,\varphi)}\middle\rangle\\!\middle\langle\smash{\iota(\theta,\varphi)}\right\rvert_{I}=\mu_{X}\otimes\mu_{I}.$
(147)

This gives that the bit string $x$ and the subset $\iota$ are both uniformly
random. We also want Bob’s substring of $x$ to be correct. For this, padding
Bob’s space implicitly to keep every term the same dimension,

$\displaystyle\begin{split}\rho_{XI\hat{X}_{I}}&=\underset{x,\varphi,\theta,J}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{\begin{subarray}{c}y_{J}\\\
(y_{J})_{\iota(\theta,\varphi)}=\\\
(x_{J})_{\iota(\theta,\varphi)}\end{subarray}}\frac{1}{2^{|\theta_{J}+\varphi_{J}|}}\vphantom{y_{J}}\left\lvert\smash{y_{J}}\middle\rangle\\!\middle\langle\smash{y_{J}}\right\rvert_{X}\otimes\vphantom{\iota(\theta,\varphi)}\left\lvert\smash{\iota(\theta,\varphi)}\middle\rangle\\!\middle\langle\smash{\iota(\theta,\varphi)}\right\rvert_{I}\otimes\vphantom{(x_{J})_{\iota(\theta,\varphi)}}\left\lvert\smash{(x_{J})_{\iota(\theta,\varphi)}}\middle\rangle\\!\middle\langle\smash{(x_{J})_{\iota(\theta,\varphi)}}\right\rvert_{\hat{X}_{I}}\\\
&=\underset{x,\varphi,\theta,J}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{\begin{subarray}{c}y_{J}\\\
(y_{J})_{\iota(\theta,\varphi)}=\\\
(x_{J})_{\iota(\theta,\varphi)}\end{subarray}}\frac{1}{2^{|\theta_{J}+\varphi_{J}|}}\vphantom{y_{J}}\left\lvert\smash{y_{J}}\middle\rangle\\!\middle\langle\smash{y_{J}}\right\rvert_{X}\otimes\vphantom{\iota(\theta,\varphi)}\left\lvert\smash{\iota(\theta,\varphi)}\middle\rangle\\!\middle\langle\smash{\iota(\theta,\varphi)}\right\rvert_{I}\otimes\vphantom{(y_{J})_{\iota(\theta,\varphi)}}\left\lvert\smash{(y_{J})_{\iota(\theta,\varphi)}}\middle\rangle\\!\middle\langle\smash{(y_{J})_{\iota(\theta,\varphi)}}\right\rvert_{\hat{X}_{I}}\\\
&=\rho_{XIX_{I}}.\qed\end{split}$ (148)

We now show security.

######  Theorem 5.6.

Let $K$ be the constant from Theorem 4.10. For any $N,n\in\mathbb{N}$ and
$\varepsilon,\eta,\delta\in(0,1)$ such that $\eta\varepsilon>\delta$, 5.4 is a
$(n,\lg(\frac{4}{3}),Kn^{3}\sqrt{\varepsilon}+n\eta)$-WSE scheme that fails
with probability $e^{-2N(\eta\varepsilon-\delta)^{2}}$.

For example, taking the parameter values from Example 4.11 gives exponentially
small failure probability, and requires only polynomially many qubits to run.

###### Proof.

First, we show security for Bob. This is essentially because an honest Bob
provides Alice no information about any of his strings on $J$. Bob, as he is
honest, prepares the shared state

$\displaystyle\rho_{ABC}=\underset{x,\varphi\in\mathbb{Z}_{2}^{N}}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}{}^{\otimes
N}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert_{A}{}^{\otimes
N}\otimes\vphantom{x\varphi}\left\lvert\smash{x\varphi}\middle\rangle\\!\middle\langle\smash{x\varphi}\right\rvert_{B}\otimes\vphantom{x\varphi}\left\lvert\smash{x\varphi}\middle\rangle\\!\middle\langle\smash{x\varphi}\right\rvert_{C}.$
(149)

Alice can do anything to her state but she must send Bob and Charlie $J$ and
$\theta$. Note that Bob and Charlie must both receive the same pair by
hypothesis. Therefore, as Alice must get $y,\theta,J$ by some channel
$\Phi:\mathcal{L}(\textsf{A})\rightarrow\mathcal{L}(\textsf{Y}\otimes\textsf{A}^{\prime})$,

$\displaystyle\begin{split}\rho_{YA^{\prime}BC}=\underset{x,\varphi}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{y,\theta,J}&\vphantom{y\theta
J}\left\lvert\smash{y\theta J}\middle\rangle\\!\middle\langle\smash{y\theta
J}\right\rvert_{Y}\otimes\vphantom{y\theta J_{Y}\Phi({}^{\otimes
N}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert_{A}{}^{\otimes
N})_{YA^{\prime}}y\theta J}\left\langle\smash{y\theta
J}\middle\rvert\smash{{}_{Y}\Phi({}^{\otimes
N}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert_{A}{}^{\otimes
N})_{YA^{\prime}}}\middle\rvert\smash{y\theta J}\right\rangle_{Y}\\\
&\otimes\vphantom{x\varphi\theta J}\left\lvert\smash{x\varphi\theta
J}\middle\rangle\\!\middle\langle\smash{x\varphi\theta
J}\right\rvert_{B}\otimes\vphantom{x\varphi\theta
J}\left\lvert\smash{x\varphi\theta
J}\middle\rangle\\!\middle\langle\smash{x\varphi\theta
J}\right\rvert_{C}.\end{split}$ (150)

Since Bob is honest, Alice knows that he must provide her with
$y_{J^{c}}^{B}=x_{J^{c}}+\theta_{J^{c}}\land\varphi_{J^{c}}$ and Charlie
provides her with the same. If Alice chooses not to abort, Bob produces
$\iota(\theta,\varphi)$ so the state becomes

$\displaystyle\begin{split}\rho_{Y^{\prime}A^{\prime}I\hat{X}C}=\underset{x,\varphi}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{y,\theta,J}&\vphantom{y\theta
Jy_{J^{c}}^{B}}\left\lvert\smash{y\theta
Jy_{J^{c}}^{B}}\middle\rangle\\!\middle\langle\smash{y\theta
Jy_{J^{c}}^{B}}\right\rvert_{Y^{\prime}}\otimes\vphantom{y\theta
J_{Y}\Phi({}^{\otimes
N}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert_{A}{}^{\otimes
N})_{YA^{\prime}}y\theta J}\left\langle\smash{y\theta
J}\middle\rvert\smash{{}_{Y}\Phi({}^{\otimes
N}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert_{A}{}^{\otimes
N})_{YA^{\prime}}}\middle\rvert\smash{y\theta J}\right\rangle_{Y}\\\
&\otimes\vphantom{\iota(\theta,\varphi)}\left\lvert\smash{\iota(\theta,\varphi)}\middle\rangle\\!\middle\langle\smash{\iota(\theta,\varphi)}\right\rvert_{I}\otimes\vphantom{x_{J}}\left\lvert\smash{x_{J}}\middle\rangle\\!\middle\langle\smash{x_{J}}\right\rvert_{\hat{X}}\otimes\rho^{x,\varphi,\theta,J}_{C}.\end{split}$
(151)

From this state and the definition of $\iota(\theta,\varphi)$ as the set of
indices where $\theta_{J}$ and $\varphi_{J}$ match for honest Bob, in order
for Alice to guess $\iota$, she needs to guess $\varphi_{J}$. Since she has no
information about $x_{J}$ she may not do better than uniformly random.
Formally,

$\displaystyle\begin{split}\rho_{Y^{\prime}A^{\prime}I}=\underset{x,\varphi}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{y,\theta,J}&\vphantom{y\theta
Jy^{B}_{J^{c}}}\left\lvert\smash{y\theta
Jy^{B}_{J^{c}}}\middle\rangle\\!\middle\langle\smash{y\theta
Jy^{B}_{J^{c}}}\right\rvert_{Y^{\prime}}\otimes\vphantom{y\theta
J_{Y}\Phi({}^{\otimes
N}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert_{A}{}^{\otimes
N})_{YA^{\prime}}y\theta J}\left\langle\smash{y\theta
J}\middle\rvert\smash{{}_{Y}\Phi({}^{\otimes
N}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert_{A}{}^{\otimes
N})_{YA^{\prime}}}\middle\rvert\smash{y\theta J}\right\rangle_{Y}\\\
&\otimes\vphantom{\iota(\theta,\varphi)}\left\lvert\smash{\iota(\theta,\varphi)}\middle\rangle\\!\middle\langle\smash{\iota(\theta,\varphi)}\right\rvert_{I}\\\
=\sum_{y,\theta,J}\underset{x_{J^{c}},\varphi_{J^{c}}}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}&\vphantom{y\theta
Jy^{B}_{J^{c}}}\left\lvert\smash{y\theta
Jy^{B}_{J^{c}}}\middle\rangle\\!\middle\langle\smash{y\theta
Jy^{B}_{J^{c}}}\right\rvert_{Y^{\prime}}\otimes\vphantom{y\theta
J_{Y}\Phi({}^{\otimes|J^{c}|}\vphantom{x_{J^{c}}^{\varphi_{J^{c}}}}\left\lvert\smash{x_{J^{c}}^{\varphi_{J^{c}}}}\middle\rangle\\!\middle\langle\smash{x_{J^{c}}^{\varphi_{J^{c}}}}\right\rvert_{A_{J^{c}}}{}^{\otimes|J^{c}|}\otimes\mu_{A_{J}})_{YA^{\prime}}y\theta
J}\left\langle\smash{y\theta
J}\middle\rvert\smash{{}_{Y}\Phi({}^{\otimes|J^{c}|}\vphantom{x_{J^{c}}^{\varphi_{J^{c}}}}\left\lvert\smash{x_{J^{c}}^{\varphi_{J^{c}}}}\middle\rangle\\!\middle\langle\smash{x_{J^{c}}^{\varphi_{J^{c}}}}\right\rvert_{A_{J^{c}}}{}^{\otimes|J^{c}|}\otimes\mu_{A_{J}})_{YA^{\prime}}}\middle\rvert\smash{y\theta
J}\right\rangle_{Y}\\\
&\otimes\underset{\varphi_{J}}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\vphantom{\iota(\theta,\varphi)}\left\lvert\smash{\iota(\theta,\varphi)}\middle\rangle\\!\middle\langle\smash{\iota(\theta,\varphi)}\right\rvert_{I}\\\
&=\rho_{Y^{\prime}A^{\prime}}\otimes\mu_{I},\end{split}$ (152)

which implies that, since Alice’s actions are local, any action she may do on
her space gives rise to an uncorrelated final state
$\rho_{AI}=\rho_{A}\otimes\mu_{I}$.

Now, we study security for Alice. That is, Alice is honest but Bob and Charlie
are dishonest and colluding. We want to show that
$H^{Kn^{3}\sqrt{\varepsilon}+n\eta}_{\mathrm{min}}(X|B)_{\rho}\geq-\ln\left\lparen\frac{3}{4}\right\rparen
n$. As Bob is dishonest, for the first step of the protocol, he may produce
any shared state $\rho_{ABC}$. The next three steps of the protocol consist of
Alice playing $N-n$ TFKW games in parallel with Bob and Charlie, and verifying
the rigidity condition. Therefore, if Alice does not abort, she knows by Lemma
4.9 that, with probability $1-e^{-2N(\eta\varepsilon-\delta)^{2}}$, there are
at least $(1-\eta)N$ games that win with probability greater than
$\cos^{2}\frac{\pi}{8}-\varepsilon$. We can apply the rigidity from Theorem
4.10 to get that there exists a constant $K\geq 0$, isometries
$V:\textsf{B}\rightarrow\textsf{B}^{\prime}$ and
$W:\textsf{C}\rightarrow\textsf{C}^{\prime}$, an auxiliary register $R$, and a
state $\lvert\phi\rangle=\sum_{x,\varphi\in\mathbb{Z}_{2}^{n}}{}^{\otimes
n}\lvert x^{\varphi}\rangle\otimes\lvert x,\varphi\rangle_{BCR}$ where the
$\lvert
x,\varphi\rangle_{BCR}\in\textsf{B}^{\prime}\otimes\textsf{C}^{\prime}\otimes\textsf{R}$
have orthogonal support on both $\textsf{B}^{\prime}$ and
$\textsf{C}^{\prime}$ such that

$\displaystyle\underset{J}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\left\|(V\otimes
W)\rho_{A_{J}BC}(V\otimes
W)^{\dagger}-\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)\right\|_{\operatorname{Tr}}\leq
Kn^{3}\sqrt{\varepsilon}+n\eta.$ (153)

Let
$\sigma_{A_{J}BC}=\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)$
and we study first what happens if the shared state is $\sigma$. Since Bob and
Charlie may not communicate and Charlie provides no additional information in
the protocol, we may safely trace out Charlie’s state. However, we must
include the copy of $\theta$ that Bob gets during the protocol. By the
orthogonality of Charlie’s state’s support from the rigidity theorem,

$\displaystyle\sigma_{A_{J}\Theta
B}=\underset{\theta}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{x,\varphi}{}^{\otimes
n}\vphantom{x^{\varphi}}\left\lvert\smash{x^{\varphi}}\middle\rangle\\!\middle\langle\smash{x^{\varphi}}\right\rvert{}^{\otimes
n}\otimes\vphantom{\theta}\left\lvert\smash{\theta}\middle\rangle\\!\middle\langle\smash{\theta}\right\rvert_{\Theta}\otimes\operatorname{Tr}_{CR}(\vphantom{x,\varphi}\left\lvert\smash{x,\varphi}\middle\rangle\\!\middle\langle\smash{x,\varphi}\right\rvert)_{B}.$
(154)

Alice’s measurement gives her $X$ and makes the state

$\displaystyle\begin{split}\sigma_{X\Theta
B}&=\underset{\theta}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{x,y,\varphi}\left\lvert\vphantom{yH^{\theta_{J}+\varphi}x}\left\langle\smash{y}\middle\rvert\smash{H^{\theta_{J}+\varphi}}\middle\rvert\smash{x}\right\rangle\right\rvert^{2}\vphantom{y}\left\lvert\smash{y}\middle\rangle\\!\middle\langle\smash{y}\right\rvert_{X}\otimes\vphantom{\theta}\left\lvert\smash{\theta}\middle\rangle\\!\middle\langle\smash{\theta}\right\rvert_{\Theta}\otimes\operatorname{Tr}_{CR}(\vphantom{x,\varphi}\left\lvert\smash{x,\varphi}\middle\rangle\\!\middle\langle\smash{x,\varphi}\right\rvert)_{B}\\\
&=\underset{\theta}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{\begin{subarray}{c}x,y,\varphi\\\
x_{\iota(\theta,\varphi)=y_{\iota(\theta,\varphi)}}\end{subarray}}\frac{1}{2^{|\theta_{J}+\varphi|}}\vphantom{y}\left\lvert\smash{y}\middle\rangle\\!\middle\langle\smash{y}\right\rvert_{X}\otimes\vphantom{\theta}\left\lvert\smash{\theta}\middle\rangle\\!\middle\langle\smash{\theta}\right\rvert_{\Theta}\otimes\operatorname{Tr}_{CR}(\vphantom{x,\varphi}\left\lvert\smash{x,\varphi}\middle\rangle\\!\middle\langle\smash{x,\varphi}\right\rvert)_{B},\end{split}$
(155)

where $\iota(\theta,\varphi)$ is defined as before. Noting that Bob’s register
is uncorrelated with part of Alice’s register $X_{\iota(\theta,\varphi)^{c}}$,
that gives that Bob’s probability of guessing any bit in that register is
$\frac{1}{2}$. So, for fixed $\theta,\varphi$, Bob’s probability of guessing
$X$ is
$\frac{1}{2^{|\iota(\theta,\varphi)^{c}|}}=\frac{1}{2^{|\theta_{J}+\varphi|}}$.
Since $\theta_{J}$ is uniformly random, Bob’s average-case probability of
guessing $X$ for fixed $\varphi$ is,

$\displaystyle\underset{\theta}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\frac{1}{2^{|\theta_{J}+\varphi|}}=\frac{1}{2^{n}}\sum_{k=0}^{n}\binom{n}{k}\frac{1}{2^{k}}=\left\lparen\frac{3}{4}\right\rparen^{n}.$
(156)

Since this has no dependence on $\varphi$, we see that this is Bob’s
probability of guessing $y$, and so the min-entropy is
$H_{\mathrm{min}}(X|B)_{\sigma}\geq-\lg(\frac{3}{4})n$, where we consider
$\Theta$ as part of Bob’s register $B$. Now we relate this to the smoothed
min-entropy of $\rho$. Since $V\otimes W$ is an isometry,
$H^{Kn^{3}\sqrt{\varepsilon}+n\eta}_{\mathrm{min}}(X|B)_{\rho}=H^{Kn^{3}\sqrt{\varepsilon}+n\eta}_{\mathrm{min}}(X|B)_{(V\otimes
W)\rho(V\otimes W)^{\dagger}}$, and $\sigma$ belongs to a
$Kn^{3}\sqrt{\varepsilon}+n\eta$-ball around $(V\otimes W)\rho(V\otimes
W)^{\dagger}$, so

$\displaystyle
H^{Kn^{3}\sqrt{\varepsilon}+n\eta}_{\mathrm{min}}(X|B)_{\rho}\geq
H_{\mathrm{min}}(X|B)_{\sigma}\geq-\lg\left\lparen\frac{3}{4}\right\rparen n.$
(157)

Note that this holds in the same way for Charlie, so he cannot extract any
more information that Bob can if he is dishonest. ∎

###  5.3 Bit Commitment from WSE

Bit commitment (BC) is a cryptographic primitive where a sender, Alice, sends
an encoded bit (or more generally a bit string) to a receiver, Bob, and may
choose to reveal it at a later time. Accordingly, a scheme for BC consists of
a commit protocol and a reveal protocol. Ideally, the scheme should be
_hiding_ — Bob is unable to learn the bit until Alice chooses to reveal it —
and _binding_ — Alice must reveal the same bit that she originally chose. In
[KWW12], they consider a BC scheme where Alice commits to a random bit string
rather then one she chooses freely. We formally define such a scheme in
essentially the same way they do.

######  Definition 5.7.

A _$(\ell,\varepsilon)$ -randomised bit string commitment (RBC) scheme_ is a
pair of protocols between two parties Alice and Bob: a protocol commit that
creates a state $\rho_{YAB}$ and a protocol reveal that creates from this a
state $\rho_{YA^{\prime}\hat{Y}FB^{\prime}}$. Here, $Y=\mathbb{Z}_{2}^{\ell}$
holds Alice’s committed string; $\hat{Y}=\mathbb{Z}_{2}^{\ell}$ holds the
string Alice reveals; $F=\mathbb{Z}_{2}$ indicates whether Bob accepts (1) or
rejects (0) the reveal; and $A,A^{\prime}$ and $B,B^{\prime}$ are additional
quantum registers for Alice and Bob, respectively. The scheme must be
_correct_ , _$\varepsilon$ -hiding_, and _$\varepsilon$ -binding_:

Correctness: If Alice and Bob are honest, for
$\sigma_{YF}=\mu_{Y}\otimes\vphantom{1}\left\lvert\smash{1}\middle\rangle\\!\middle\langle\smash{1}\right\rvert$,
$\|\rho_{Y\hat{Y}F}-\sigma_{YYF}\|_{\operatorname{Tr}}\leq\varepsilon$.

$\varepsilon$-hiding: If Alice is honest,
$\|\rho_{YB}-\mu_{Y}\otimes\rho_{B}\|\leq\varepsilon$.

$\varepsilon$-binding: If Bob is honest, there exists a state $\sigma_{YAB}$
where $\|\rho_{YAB}-\sigma_{YAB}\|_{\operatorname{Tr}}\leq\varepsilon$ such
that, applying reveal to it to get $\sigma_{YA^{\prime}\hat{Y}FB^{\prime}}$,
$\Pr[Y\neq\hat{Y}\land F=1]\leq\varepsilon$.

As for WSE, we say this scheme _fails with probability $p$_ if any one of
these conditions does not hold with probability at most $p$.

In [KWW12], they provide a way to construct an RBC scheme using a weak string
erasure scheme and a linear code. The roles of the sender and the receiver
from the WSE scheme are preserved. In particular, with an
$(n,\lambda,\varepsilon)$-WSE scheme and an $(n,k,d)$-linear code, they
construct a $\left\lparen\lambda
n-(n-k)-d,2\varepsilon+2^{-d/2}\right\rparen$-randomised bit string commitment
scheme. Using this recipe, our WSE scheme 5.4 gives a form of bit commitment
in a model with two receivers. In this model, Alice is a sender who is
required to broadcast, and Bob and Charlie are colluding receivers who are
isolated from each other. Similarly to WSE, we only require that Bob be able
to read the revealed bit string, rather than both receivers. We call this the
_two-receiver model_.

######  Corollary 5.8.

Let $K,N,n,\varepsilon,\eta,\delta$ be constants that satisfy Theorem 5.6, and
let $k,d\in\mathbb{N}$ such that there exists an $(n,k,d)$-linear code. Then,
for $\ell=(\lg\tfrac{4}{3})n-(n-k)-d$ and
$\omega=2Kn^{3}\sqrt{\varepsilon}+2n\eta+2^{-d/2}$, in the two-receiver model,
there exists a $\left\lparen\ell,\omega\right\rparen$-randomised bit string
commitment scheme that fails with probability
$e^{-2N(\eta\varepsilon-\delta)^{2}}$.

Using the construction of [KWW12], the correctness and $\varepsilon$-binding
of the scheme between Alice and Bob follow immediately from the correctness
and security for Bob of WSE. Also, due to the symmetry requirement on security
for Alice in three-party WSE, this construction provides $\varepsilon$-hiding
when Bob and Charlie are dishonest.

As mentioned before, a construction of [BGKW88] provides classical bit
commitment in a model with two senders who may not communicate. We observe
that, in contrast, bit commitment is classically impossible in our two-
receiver model. The first step of a protocol in our model consists of the
preparation of an initial shared state by Bob. If only classical operations
are allowed, Bob is just sampling from a probability distribution and sharing
the result. In particular, he can make sure that all three parties receive the
same classical information. Next, for the remainder of the protocol, Bob and
Charlie may not communicate. However, since Alice must communicate by publicly
broadcasting, Bob and Charlie receive exactly the same information from her,
and may respond to all the same challenges. As such, classically, our model
becomes equivalent to the standard two-party model. In particular, bit
commitment is impossible. The difference with the two-sender model, where bit
commitment does exist classically, arises due to the additional communication
restriction we imposed: the receiver of [BGKW88] may share different
information with each of the senders, rather than broadcasting publicly.

###  5.4 Everlasting Randomness Expansion

The creation of fresh, trusted, uniform randomness is an important part of
many computational and cryptographic tasks. Since quantum mechanics is
inherently probabilistic, it stands to reason that quantum procedures prove
useful for this task. A major theoretical hurdle in achieving this is that it
is difficult to characterise the behaviour of an untrusted quantum device: one
needs to verify that their source of randomness is truly random and not shared
by an eavesdropper. Largely, the methods to bypass this difficulty use a
nonlocal game to verify entanglement between two untrusted provers. However,
this requires, in particular, that the provers are able to produce entangled
states, and keep them from decohering throughout the running time of the
protocol. This can be an impractical requirement.

In our contribution, we remove the need for long-distance entanglement, and
instead make the assumption of a trusted but leaky measurement, as well as a
standard computational assumption. The protocol consists of two steps: first,
Alice samples the output of a pseudorandom generator, allowing her to increase
the size of her random string; then, she uses this as the source of randomness
to play the TFKW game against computationally-bounded and isolated Bob and
Charlie, where the rigidity allows her to extract a string that is uniformly
random and unknown to either Bob or Charlie. First, we need to formalise the
model we are working in, based on the structure of an MoE game.

######  Definition 5.9.

The _MoE model for randomness expansion_ consists of three quantum parties: a
trusted verifier Alice, who interacts with two untrusted provers, Bob and
Charlie. The model satisfies the following:

  * •

Bob and Charlie are able to prepare a tripartite shared state but then are
isolated.

  * •

Alice can make trusted measurements on her register, which are leaky in the
sense that Bob and Charlie can learn the measurement bases.

Now, we can define randomness expanders in this model.

######  Definition 5.10.

A _$(s(n),\varepsilon)$ -local randomness expander_ is a protocol in the MoE
model, where, given a uniformly random seed in $S=\mathbb{Z}_{2}^{s(n)}$,
Alice, Bob, and Charlie construct a quantum state $\rho_{YSBC}$, where
$Y=\mathbb{Z}_{2}^{n}$ and $S$ are classical registers that Alice holds and
$B$ and $C$ are potentially quantum registers that Bob and Charlie hold,
respectively, such that

$\displaystyle\begin{split}&\|\rho_{YSB}-\mu_{Y}\otimes\mu_{S}\otimes\rho_{B}\|_{\operatorname{Tr}}\leq\varepsilon\\\
&\|\rho_{YSC}-\mu_{Y}\otimes\mu_{S}\otimes\rho_{C}\|_{\operatorname{Tr}}\leq\varepsilon,\end{split}$
(158)

if Alice does not abort during the execution. As before, we say this scheme
_fails with probability $p$_ if these conditions do not hold with probability
at most $p$.

The idea of this definition is that Alice’s output needs to be approximately
uniformly random in any case, but we can also get the additional guarantee
that, as long as Bob and Charlie stay isolated, they cannot hold onto side
information that allows them to guess the output. However, we do not constrain
their ability to guess the output if they come back together: for example, the
register $BC$ could be maximally entangled with Alice’s register before she
makes her final measurement, without either $B$ or $C$ being maximally
entangled on their own.

The main computational tool we will be making use of is the idea of a
pseudorandom generator against computationally-bounded adversaries.

######  Definition 5.11.

An algorithm $Q:\mathbb{Z}_{2}^{\ast}\rightarrow\mathbb{Z}_{2}^{\ast}$ is
_quantum polynomial time_ (QPT) if there exists a Turing machine $T$ such
that, for each $n\in\mathbb{N}$, $T(n)$ outputs in polynomial time the
description of a quantum circuit that, on input $x\in\mathbb{Z}_{2}^{n}$,
outputs $Q(x)$. Similarly, we can consider a family of states $\rho_{n}$,
$n\in\mathbb{N}$, QPT if $T(n)$ outputs a quantum circuit that constructs
$\rho_{n}$ from $\lvert 0\rangle$; a family of unitaries $U_{n}$ QPT if $T(n)$
provides a quantum circuit that acts as $U_{n}$; and a family of measurements
$A_{n}$ QPT if the measurement $A_{n}$ can be undertaken by first acting by
some QPT unitary $U_{n}$ and then measuring in the computational basis.

Now, we can introduce pseudorandom generators as functions that take a
uniformly random string to a longer string that no QPT algorithm can
distinguish from uniform.

######  Definition 5.12.

A family of functions
$G_{n}:\mathbb{Z}_{2}^{s(n)}\rightarrow\mathbb{Z}_{2}^{n}$ is a _pseudorandom
generator_ (PRG) if, for uniform random variables $\Gamma$ in
$\mathbb{Z}_{2}^{s(n)}$ and $\Delta$ in $\mathbb{Z}_{2}^{n}$, and for every
QPT algorithm $Q:\mathbb{Z}_{2}^{\ast}\rightarrow\mathbb{Z}_{2}$,

$\displaystyle\Big{\lvert}\Pr\left[Q(G_{n}(\Gamma))=1\right]-\Pr\left[Q(\Delta)=1\right]\Big{\rvert}\in\texttt{negl}(n).$
(159)

The input of $G_{n}$ is called the _seed_ and $s(n)$ is the seed length.

Note that, in our context, the QPT algorithm need only be given classical
access to the random variable, since Alice will be simply providing Bob and
Charlie with strings sampled from this distribution. As such, that probability
of $Q$ outputting $1$ takes its usual meaning as the probability measure of
$Q^{-1}(\\{1\\})$.

Because of brute force attacks against $G_{n}$, $s(n)\in O(\lg n)$ is a strict
lower bound on the seed length. Thus, we cannot hope for exponential
randomness expansion with this method, but we can nevertheless expect large
polynomial or even superpolynomial expansion. Now we can define a variant of
the TFKW game that uses a pseudorandom rather than uniformly random question
distribution.

######  Definition 5.13.

Let $G_{n}:\mathbb{Z}_{2}^{s(n)}\rightarrow\mathbb{Z}_{2}^{n}$ be a PRG and
let $\Gamma$ be the uniform random variable on $\mathbb{Z}_{2}^{s(n)}$. The
_computational TFKW game_ on $n$ qubits is the MoE game
$\texttt{TFKW}^{n}_{G}=\left\lparen\mathbb{Z}_{2}^{n},\mathbb{Z}_{2}^{n},\textsf{Q}^{\otimes
n},\pi_{G},A^{n}\right\rparen$, where
$(A^{n})^{\theta}_{x}=\vphantom{x^{\theta}}\left\lvert\smash{x^{\theta}}\middle\rangle\\!\middle\langle\smash{x^{\theta}}\right\rvert$
as for the usual TFKW game and
$\pi_{G}(\theta)=\Pr\left[G_{n}(\Gamma)=\theta\right]$.

The set of strategies for the computational TFKW game is identical to that for
the usual TFKW game, but where we restrict to families of strategies that can
be modelled by QPT adversaries. As a warm-up to the main result of this
section, we can see that against QPT strategies (shared state and measurements
are all QPT), the usual and computational TFKW games behave essentially the
same.

######  Lemma 5.14.

Let
$n\mapsto\texttt{S}_{n}=\left\lparen\textsf{B}_{n},\textsf{C}_{n},B_{n},C_{n},\rho_{n}\right\rparen$
be a family of strategies with QPT adversaries. Then, assuming the existence
of a PRG $G_{n}:\mathbb{Z}_{2}^{s(n)}\rightarrow\mathbb{Z}_{2}^{n}$, for every
$i\in[n]$,

$\displaystyle\Big{\lvert}\mathfrak{w}^{i}_{\texttt{TFKW}^{n}_{G}}(\texttt{S}_{n})-\mathfrak{w}^{i}_{\texttt{TFKW}^{n}}(\texttt{S}_{n})\Big{\rvert}\in\texttt{negl}(n)$
(160)

###### Proof.

We will use $\texttt{S}_{n}$ to construct a QPT algorithm attempting to
distinguish the variable $G_{n}(\Gamma)$ from uniformly random as follows. To
compute $Q(\theta)$, measure the state $\rho_{n}$ with the POVM
$(A^{n})^{\theta}\otimes(B_{n})^{\theta}\otimes(C_{n})^{\theta}$. Output $1$
if the measurement result is some $(x,x^{B},x^{C})$ with
$x_{i}=x^{B}_{i}=x^{C}_{i}$ and output $0$ otherwise. Then, for uniform random
variables $\Gamma$ in $\mathbb{Z}_{2}^{s(n)}$ and $\Delta$ in
$\mathbb{Z}_{2}^{n}$,

$\displaystyle\begin{split}&\Big{\lvert}\Pr\left[Q(G_{n}(\Gamma))=1\right]-\Pr\left[Q(\Delta)=1\right]\Big{\rvert}\\\
&=\Big{\lvert}\underset{\theta\leftarrow
G_{n}(\Gamma)}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{y\in\mathbb{Z}_{2}}\operatorname{Tr}\left[((A^{n})^{\theta}_{y,i}\otimes(B_{n})^{\theta}_{y,i}\otimes(C_{n})^{\theta}_{y,i})\rho_{n}\right]-\underset{\theta\leftarrow\Delta}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\sum_{y\in\mathbb{Z}_{2}}\operatorname{Tr}\left[((A^{n})^{\theta}_{y,i}\otimes(B_{n})^{\theta}_{y,i}\otimes(C_{n})^{\theta}_{y,i})\rho_{n}\right]\Big{\rvert}\\\
&=\Big{\lvert}\mathfrak{w}^{i}_{\texttt{TFKW}^{n}_{G}}(\texttt{S}_{n})-\mathfrak{w}^{i}_{\texttt{TFKW}^{n}}(\texttt{S}_{n})\Big{\rvert}.\end{split}$
(161)

We may conclude by noting that the left-hand side is contained in
$\texttt{negl}(n)$ by hypothesis. ∎

Now, we can formally present the protocol.

######  Protocol 5.15 (randomness expansion).

1. Alice samples $(t,u)\in\mathbb{Z}_{2}^{s(N)+s\left\lparen\left\lceil\lg\binom{N}{n}\right\rceil\right\rparen}$ uniformly at random. She computes $\theta=G_{N}(t)$ and $J=G_{\left\lceil\lg\binom{N}{n}\right\rceil}(u)$, where she interprets $J$ as a subset of $[N]$ of cardinality $n$. 2. Bob and Charlie prepare a shared state $\rho_{ABC}$ and then are isolated. 3. Alice measures each of her qubits $i\in[N]$ in basis $\\{\lvert 0^{\theta_{i}}\rangle,\lvert 1^{\theta_{i}}\rangle\\}$ if $i\notin J$ and in basis $\\{\lvert 0_{\circlearrowleft}\rangle,\lvert 1_{\circlearrowleft}\rangle\\}$ if $i\in J$. This produces a string $y\in\mathbb{Z}_{2}^{N}$ that she keeps. 4. Alice sends Bob and Charlie the key $\theta$ and $J$. Bob and Charlie each reply with a guess of $y$, $y^{B}$ and $y^{C}$ respectively. 5. Alice verifies that they win the TFKW game $y_{i}=y^{B}_{i}=y^{C}_{i}$ for at least $(\cos^{2}\left\lparen\frac{\pi}{8}\right\rparen-\delta)N$ of the $i\in[N]\backslash J$, and then, if she accepts, takes $y_{J}$ to be her output.

The protocol follows a very similar framework to 5.4, with the main
differences being that Alice chooses her questions and test qubits only
pseudorandomly, and measures always in the same basis to get her output. This
basis is chosen to be mutually unbiased with all of the Breidbart states, and
thus gives a uniformly random measurement result for any optimal strategy.
Note that Bob and Charlie are able to make the protocol accept and provide
randomness without using entanglement simply by preparing the Breidbart state
$\lvert\beta\rangle^{\otimes N}$, sending it to Alice, and guessing $0$ on all
the TFKW game verification rounds.

Also, in this protocol, Alice shares $\theta$ and $J$ with Bob and Charlie
immediately after she measures, so they have full information about her
measurement bases. Thus, it doesn’t affect the protocol if that information is
leaked.

######  Theorem 5.16.

Let $K$ be the constant from Theorem 4.10, $\varepsilon,\eta,\delta\in(0,1)$
such that $\eta\varepsilon>\delta$, and $N\in\texttt{poly}(n)$. Assuming the
existence of a pseudorandom generator,
$G_{n}:\mathbb{Z}_{2}^{s(n)}\rightarrow\mathbb{Z}_{2}^{n}$, 5.15 is a
$(s(N)+s(\lg\binom{N}{n}),2Kn^{3}\sqrt{\varepsilon}+2n\eta+\texttt{negl}(n))$-local
randomness expander in the MoE model with QPT provers, that fails with
probability $e^{-2N(\eta\varepsilon-\delta)^{2}}+\texttt{negl}(n)$.

The scenario in Example 4.11 allows us to take $N=n^{27}$, so provided that
$s(n)\in o(n^{1/27})$ is possible, this yields randomness expansion.

###### Proof.

Write $b=\left\lceil\lg\binom{N}{n}\right\rceil$. Let $U$ be the random
variable representing the number of rounds Bob and Charlie win, let $V$ be the
random variable representing the number of rounds they would have won if Alice
chose $J$ uniformly at random (among the subsets of $[N]$ with cardinality
$n$), and let $W$ be the number of rounds they would have won if Alice chose
both $J$ and $\theta$ uniformly at random.

Take $Q(\theta,J)$ to be the QPT algorithm computed by running steps 2-5 of
the randomness expansion protocol, and outputting $1$ if Alice accepts the
verification of the TFKW games, and $0$ otherwise. Then, taking
$\Gamma_{1},\Gamma_{2},\Delta_{1},\Delta_{2}$ to be random variables in
$\mathbb{Z}_{2}^{s(N)}$, $\mathbb{Z}_{2}^{s(b)}$, $\mathbb{Z}_{2}^{N}$, and
$\mathbb{Z}_{2}^{b}$, respectively, we know that

$\displaystyle\begin{split}&\Pr\left[Q(G_{N}(\Gamma_{1}),G_{b}(\Gamma_{2}))=1\right]=\Pr\left[U\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right],\\\
&\Pr\left[Q(G_{N}(\Gamma_{1}),\Delta_{2})=1\right]=\Pr\left[V\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right],\text{
and}\\\
&\Pr\left[Q(\Delta_{1},\Delta_{2})=1\right]=\Pr\left[W\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right],\end{split}$
(162)

giving

$\displaystyle\begin{split}&\Big{\lvert}\Pr\left[U\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right]-\Pr\left[W\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right]\Big{\rvert}\\\
&\qquad\leq\Big{\lvert}\Pr\left[U\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right]-\Pr\left[V\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right]\Big{\rvert}\\\
&\qquad\qquad+\Big{\lvert}\Pr\left[V\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right]-\Pr\left[W\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right]\Big{\rvert}\\\
&\qquad\in\texttt{negl}(b)+\texttt{negl}(N)\subseteq\texttt{negl}(n),\end{split}$
(163)

as $N\in\texttt{poly}(n)$ and $b\in O(n\lg n)$. Now, using Lemma 4.9 as in
Theorem 5.6, if less than $(1-\eta)N$ of the rounds have winning probability
greater than $\cos^{2}\left\lparen\frac{\pi}{8}\right\rparen-\varepsilon$,
then

$\displaystyle\Pr\left[W\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right]\leq
e^{-2N(\eta\varepsilon-\delta)^{2}}.$ (164)

By the above, then

$\displaystyle\Pr\left[U\geq(\cos^{2}\left\lparen\tfrac{\pi}{8}\right\rparen-\delta)N\right]\in
e^{-2N(\eta\varepsilon-\delta)^{2}}+\texttt{negl}(n).$ (165)

So, other than with negligible failure probability, at least $(1-\eta)N$ of
the rounds have winning probability greater than
$\cos^{2}\left\lparen\frac{\pi}{8}\right\rparen-\varepsilon$.

If we select $n$ rounds uniformly at random, each of the rounds has
probability $1-\eta$ of winning with probability greater than
$\cos^{2}\left\lparen\frac{\pi}{8}\right\rparen-\varepsilon$. Of course, the
rounds are actually selected pseudorandomly: we claim that Bob and Charlie
have a negligible probability of distinguishing the two cases. Let
$E\subseteq[N]$ be the set of rounds that win with probability greater than
$\cos^{2}\left\lparen\frac{\pi}{8}\right\rparen-\varepsilon$, and write
$J=\\{j_{1}(J),\ldots,j_{n}(J)\\}$, where $j_{1}(J)<\ldots<j_{n}(J)$. Then, as
Bob and Charlie’s strategy is QPT, it is possible, for each $i\in[n]$, by
using their strategy to play TFKW a polynomial number of times, to get a QPT
algorithm that, on input $J$, outputs whether $j_{i}(J)\in E$ correctly with
$1-\texttt{negl}(n)$ probability. Thus, using pseudorandomness, we know

$\displaystyle\left\lvert\Pr\left[j_{i}\left\lparen
G_{b}(\Gamma_{2})\right\rparen\in E\right]-\Pr\left[j_{i}(\Delta_{2})\in
E\right]\right\rvert\in\texttt{negl}(n).$ (166)

As $\Pr\left[j_{i}(\Delta_{2})\in E\right]\geq 1-\eta$, each of the rounds
chosen pseudorandomly has probability at least $1-\eta-\texttt{negl}(n)$ of
having winning probability greater than
$\cos^{2}\left\lparen\frac{\pi}{8}\right\rparen-\varepsilon$. So, by Theorem
4.10 there exists a constant $K\geq 0$, isometries
$V:\textsf{B}\rightarrow\textsf{B}^{\prime}$ and
$W:\textsf{C}\rightarrow\textsf{C}^{\prime}$, an auxiliary register $R$, and a
state $\lvert\phi\rangle=\sum_{x,\varphi\in\mathbb{Z}_{2}^{n}}{}^{\otimes
n}\lvert x^{\varphi}\rangle\otimes\lvert x,\varphi\rangle_{BCR}$ where the
$\lvert
x,\varphi\rangle_{BCR}\in\textsf{B}^{\prime}\otimes\textsf{C}^{\prime}\otimes\textsf{R}$
have orthogonal support on both $\textsf{B}^{\prime}$ and
$\textsf{C}^{\prime}$ such that

$\displaystyle\underset{J\leftarrow
G_{b}(\Gamma_{2})}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\left\|(V\otimes
W)\rho_{A_{J}BC}(V\otimes
W)^{\dagger}-\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)\right\|_{\operatorname{Tr}}\leq
Kn^{3}\sqrt{\varepsilon}+n\eta+\texttt{negl}(n).$ (167)

Let
$\sigma_{A_{J}BC}=\operatorname{Tr}_{R}(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)$.
If Alice measures her register in the basis $\vphantom{\lvert
y_{\circlearrowleft}\rangle y\in\mathbb{Z}_{2}^{n}}\left\\{{\lvert
y_{\circlearrowleft}\rangle}\middle|{y\in\mathbb{Z}_{2}^{n}}\right\\}$, she
gets

$\displaystyle\begin{split}\sigma_{YB}&=\sum_{y,x,\varphi\in\mathbb{Z}_{2}^{n}}\left\lvert\vphantom{y_{\circlearrowleft}{}^{\otimes
n}x^{\varphi}}\left\langle\smash{y_{\circlearrowleft}}\middle\rvert\smash{{}^{\otimes
n}}\middle\rvert\smash{x^{\varphi}}\right\rangle\right\rvert^{2}\vphantom{y}\left\lvert\smash{y}\middle\rangle\\!\middle\langle\smash{y}\right\rvert_{Y}\otimes\operatorname{Tr}_{CR}\left\lparen\vphantom{x,\varphi}\left\lvert\smash{x,\varphi}\middle\rangle\\!\middle\langle\smash{x,\varphi}\right\rvert\right\rparen_{B}\\\
&=\sum_{y,x,\varphi\in\mathbb{Z}_{2}^{n}}\frac{1}{2^{n}}\vphantom{y}\left\lvert\smash{y}\middle\rangle\\!\middle\langle\smash{y}\right\rvert_{Y}\otimes\operatorname{Tr}_{CR}\left\lparen\vphantom{x,\varphi}\left\lvert\smash{x,\varphi}\middle\rangle\\!\middle\langle\smash{x,\varphi}\right\rvert\right\rparen_{B}=\mu_{Y}\otimes\sigma_{B}.\end{split}$
(168)

So, following the protocol, Alice measures $A_{J}$ of $\rho$ in this basis,
giving

$\displaystyle\underset{J\leftarrow
G_{b}(\Gamma_{2})}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\|V\rho_{Y_{J}B}V^{\dagger}-\mu_{Y}\otimes\sigma_{B}\|_{\operatorname{Tr}}\leq
Kn^{3}\sqrt{\varepsilon}+n\eta+\texttt{negl}(n).$ (169)

Acting with the trace non-increasing channel $\rho\mapsto V^{\dagger}\rho V$,

$\displaystyle\underset{J\leftarrow
G_{b}(\Gamma_{2})}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\|\rho_{Y_{J}B}-\mu_{Y}\otimes
V^{\dagger}\sigma_{B}V\|_{\operatorname{Tr}}\leq
Kn^{3}\sqrt{\varepsilon}+n\eta+\texttt{negl}(n),$ (170)

where in particular,

$\displaystyle\underset{J\leftarrow
G_{b}(\Gamma_{2})}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\|\rho_{B}-V^{\dagger}\sigma_{B}V\|_{\operatorname{Tr}}\leq
Kn^{3}\sqrt{\varepsilon}+n\eta+\texttt{negl}(n),$ (171)

so, using the triangle inequality,

$\displaystyle\underset{J\leftarrow
G_{b}(\Gamma_{2})}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\|\rho_{Y_{J}B}-\mu_{Y}\otimes\rho_{B}\|_{\operatorname{Tr}}\leq
2Kn^{3}\sqrt{\varepsilon}+2n\eta+\texttt{negl}(n).$ (172)

Let $S$ be a classical register holding the seed, and let $I=G_{b}(S)$ be the
register that holds $J$. Then,

$\displaystyle\begin{split}\|\rho_{YSB}-\mu_{Y}\otimes\mu_{S}\otimes\rho_{B}\|_{\operatorname{Tr}}&\leq\Big{\|}\underset{t\in\mathbb{Z}_{2}^{s(b)}}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\vphantom{t}\left\lvert\smash{t}\middle\rangle\\!\middle\langle\smash{t}\right\rvert_{S}\otimes\vphantom{G_{b}(t)}\left\lvert\smash{G_{b}(t)}\middle\rangle\\!\middle\langle\smash{G_{b}(t)}\right\rvert_{I}\otimes\left\lparen\rho_{Y_{G_{b}(t)}B}-\mu_{Y}\otimes\rho_{B}\right\rparen\Big{\|}_{\operatorname{Tr}}\\\
&=\underset{t\in\mathbb{Z}_{2}^{s(b)}}{\text{\raisebox{-3.0pt}{\scalebox{1.5}{$\mathbb{E}$}}}}\left\|\rho_{Y_{G_{b}(t)}B}-\mu_{Y}\otimes\rho_{B}\right\|_{\operatorname{Tr}}\\\
&\leq 2Kn^{3}\sqrt{\varepsilon}+2n\eta+\texttt{negl}(n)\end{split}$ (173)

The same proof holds for $\rho_{YSC}$. ∎

##  Appendix A Preliminary Lemmas

######  Lemma A.1 (State purification).

Let H be a Hilbert space. For any mixed state
$\rho\in\mathcal{D}(\textsf{H})$, there exists a Hilbert space R and a pure
state $\lvert\psi\rangle\in\textsf{H}\otimes\textsf{R}$ such that
$\rho=\operatorname{Tr}_{R}(\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert)$.

######  Lemma A.2 (Measurement purification).

Let H be a Hilbert space. Any POVM $P:X\rightarrow\mathcal{P}(\textsf{H})$ can
be simulated by a PVM by enlarging the state space.

This lemma appeared in [TFKW13] and was used in the same way as it is here. We
see from the proof below that the enlargement of the state space is an
isometry.

###### Proof.

Consider the linear operator

$\displaystyle\begin{matrix}V:&\textsf{H}&\rightarrow&\textsf{H}\otimes\mathbb{C}^{X}\\\
&\lvert\psi\rangle&\mapsto&\sum_{x}\sqrt{P_{x}}\lvert\psi\rangle\otimes\lvert
x\rangle.\end{matrix}$ (174)

Since $\vphantom{\varphi
V^{\dagger}V\psi}\left\langle\smash{\varphi}\middle\rvert\smash{V^{\dagger}V}\middle\rvert\smash{\psi}\right\rangle=\sum_{x}\vphantom{\varphi
P_{x}\psi}\left\langle\smash{\varphi}\middle\rvert\smash{P_{x}}\middle\rvert\smash{\psi}\right\rangle=\vphantom{\varphi\psi}\left\langle\smash{\varphi}\middle|\smash{\psi}\right\rangle$,
we have that $V$ is an isometry. Fix some $x_{0}\in X$ and, identifying H with
the subspace $\textsf{H}\otimes\lvert x_{0}\rangle$ of
$\textsf{H}\otimes\textsf{X}$, we can extend $V$ to a unitary operator
$U:\textsf{H}\otimes\textsf{X}\rightarrow\textsf{H}\otimes\textsf{X}$. Define
now $\tilde{P}:X\rightarrow\mathcal{P}(\textsf{H}\otimes\textsf{X})$ by
$\tilde{P}_{x}=U^{\dagger}(\mathbb{I}_{H}\otimes\vphantom{x}\left\lvert{x}\middle\rangle\\!\middle\langle{x}\right\rvert)U$.
$\tilde{P}$ is a projective measurement as
$\tilde{P}_{x}\tilde{P}_{y}=\vphantom{xy}\left\langle\smash{x}\middle|\smash{y}\right\rangle
U^{\dagger}(\mathbb{I}_{H}\otimes\vphantom{xy}\left\lvert{x}\middle\rangle\\!\middle\langle{y}\right\rvert)U=\delta_{x,y}\tilde{P}_{x}$,
and
$\sum_{x}\tilde{P}_{x}=U^{\dagger}(\mathbb{I}_{H}\otimes\mathbb{I}_{X})U=\mathbb{I}_{HX}$.
Finally, $\tilde{P}$ acts as $P$ on $\textsf{H}\otimes\lvert x_{0}\rangle$ as

$\displaystyle(\langle\varphi\rvert\otimes\langle
x_{0}\rvert)\tilde{P}_{x}(\lvert\psi\rangle\otimes\lvert
x_{0}\rangle)=\sum_{y,y^{\prime}}\vphantom{\varphi\sqrt{P_{y^{\prime}}}\sqrt{P_{y}}\psi}\left\langle\smash{\varphi}\middle\rvert\smash{\sqrt{P_{y^{\prime}}}\sqrt{P_{y}}}\middle\rvert\smash{\psi}\right\rangle\vphantom{y^{\prime}x}\left\langle{y^{\prime}}\middle|{x}\right\rangle\vphantom{xy}\left\langle{x}\middle|{y}\right\rangle=\vphantom{\varphi
P_{x}\psi}\left\langle\smash{\varphi}\middle\rvert\smash{P_{x}}\middle\rvert\smash{\psi}\right\rangle.$
(175)

∎

######  Lemma A.3 (Properties of the trace distance).

Let H and K be Hilbert spaces.

  * •

$d_{\operatorname{Tr}}:\mathcal{D}(\textsf{H})\times\mathcal{D}(\textsf{H})\rightarrow\mathbb{R}_{+}$
is a metric.

  * •

For $\rho,\sigma\in\mathcal{D}(\textsf{H})$,
$\|\rho-\sigma\|_{\operatorname{Tr}}\leq 1$ with equality iff $\rho$ and
$\sigma$ have orthogonal supports.

  * •

For any quantum channel
$\Phi:\mathcal{L}(\textsf{H})\rightarrow\mathcal{L}(\textsf{K})$,
$\|\Phi(\rho)-\Phi(\sigma)\|_{\operatorname{Tr}}\leq\|\rho-\sigma\|_{\operatorname{Tr}}$.

  * •

For pure states $\lvert\psi\rangle,\lvert\phi\rangle\in\textsf{H}$,
$\|\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert-\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\|_{\operatorname{Tr}}\leq\|\lvert\psi\rangle-\lvert\phi\rangle\|$.

######  Lemma A.4 (Properties of the operator norm).

Let H and K be Hilbert spaces.

  * •

The operator norm is a norm.

  * •

The operator norm of a normal (e.g., Hermitian or unitary) operator is maximum
of the moduli of the eigenvalues.

  * •

For $A\in\mathcal{L}(\textsf{H})$ and $\lvert v\rangle\in\textsf{H}$,
$\|A\lvert v\rangle\|\leq\|A\|\|\lvert v\rangle\|$.

  * •

For $A,B\in\mathcal{L}(\textsf{H})$, $\|AB\|\leq\|A\|\|B\|$.

  * •

For any isometry $V:\textsf{H}\rightarrow\textsf{K}$,
$\|VAV^{\dagger}\|=\|A\|$.

## References

  * [AM16] A. Acín and L. Masanes.  Certified randomness in quantum physics.  Nature, 540: 213–219, 2016.
DOI: 10.1038/nature20119.

  * [BCM+18] Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick.  A cryptographic test of quantumness and certifiable randomness from a single quantum device.  In 59th Annual Symposium on Foundations of Computer Science—FOCS 2018, pages 320–331, 2018.
DOI: 10.1109/FOCS.2018.00038.

  * [BCW+12] C. Branciard, E. G. Cavalcanti, S. P. Walborn, V. Scarani, and H. M. Wiseman.  One-sided device-independent quantum key distribution: Security, feasibility, and the connection with steering.  Phys. Rev. A, 85: 010301, 2012.
DOI: 10.1103/PhysRevA.85.010301.

  * [Bel64] J. S. Bell.  On the Einstein-Podolsky-Rosen paradox.  Physics 1, pages 195–200, 1964.  Online: http://cds.cern.ch/record/111654/files/vol1p195-200_001.pdf.
  * [BGKW88] M. Ben-Or, S. Goldwasser, J. Kilian, and A. Widgerson.  Multi-prover interactive proofs: how to remove intractability assumptions.  In 20th Annual ACM Symposium on Theory of Computing—STOC 1988, pages 113–131, 1988.
DOI: 10.1145/62212.62223.

  * [BL20] A. Broadbent and S. Lord.  Uncloneable quantum encryption via oracles.  In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography—TQC 2020, pages 4:1 – 4:22, 2020.
DOI: 10.4230/LIPIcs.TQC.2020.4.

  * [BP15] C. Bamps and S. Pironio.  Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing.  Physical Review A, 91(5), 2015.
DOI: 10.1103/physreva.91.052111.

  * [BS16] A. Broadbent and C. Schaffner.  Quantum cryptography beyond quantum key distribution.  Designs, Codes and Cryptography, 78(1): 351–382, 2016.
DOI: 10.1007/s10623-015-0157-4.

  * [CHSH69] J. F. Clauser, M. A. Horne., A. Shimony, and R. A. Holt.  Proposed experiment to test local hidden-variable theories.  Physical Review Letters, 23(15): 880–884, 1969.
DOI: 10.1103/PhysRevLett.23.880.

  * [CLLZ21] A. Coladangelo, J. Liu, Q. Liu, and M. Zhandry.  Hidden cosets and applications to unclonable cryptography.  In Advances in Cryptology—CRYPTO 2021, pages 556–584, 2021.
DOI: 10.1007/978-3-030-84242-0_20.

  * [CMMN20] D. Cui, A. Mehta, H. Mousavi, and S. S. Nezhadi.  A generalization of CHSH and the algebraic structure of optimal strategies.  Quantum, 4: 346, 2020.
DOI: 10.22331/q-2020-10-21-346.

  * [Col06] R. Colbeck.  Quantum And Relativistic Protocols For Secure Multi-Party Computation.  PhD thesis, University of Cambridge, UK, 2006.
arXiv: 0911.3814.

  * [Col17] A. Coladangelo.  Parallel self-testing of (tilted) EPR pairs via copies of (tilted) CHSH and the magic square game.  Quantum Information & Computation, 17(9-10): 831–865, 2017.
DOI: 10.5555/3179561.3179567.

  * [CSST11] C. Crépeau, L. Salvail, J.-R. Simard, and A. Tapp.  Two provers in isolation.  In Advances in Cryptology—ASIACRYPT 2011, pages 407–430, 2011\.
DOI: 10.1007/978-3-642-25385-0_22.

  * [CV22] E. Culf and T. Vidick.  A monogamy-of-entanglement game for subspace coset states.  Quantum, 6: 791, 2022.
DOI: 10.22331/q-2022-09-01-791.

  * [CY14] M. Coudron and H. Yuen.  Infinite randomness expansion with a constant number of devices.  In 46th Annual ACM Symposium on Theory of Computing—STOC 2014, page 427–436, 2014.
DOI: 10.1145/2591796.2591873.

  * [DFSS08] I. B. Damgård, S. Fehr, L. Salvail, and C. Schaffner.  Cryptography in the bounded-quantum-storage model.  SIAM Journal on Computing, 37(6): 1865–1890, 2008.
DOI: 10.1137/060651343.

  * [GH17] W. T. Gowers and O. Hatami.  Inverse and stability theorems for approximate representations of finite groups.  Sbornik: Mathematics, 208(12): 1784–1817, 2017.
DOI: 10.1070/sm8872.

  * [HBD+15] B. Hensen, H. Bernien, A. E. Dréau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, and R. Hanson.  Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres.  Nature, 526: 682–686, 2015.
DOI: 10.1038/nature15759.

  * [JMRW16] N. Johnston, R. Mittal, V. Russo, and J. Watrous.  Extended non-local games and monogamy-of-entanglement games.  Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 472(2189): 20160003, 2016.
DOI: 10.1098/rspa.2016.0003.

  * [JNV+21] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen.  $\mathsf{MIP}^{*}=\mathsf{RE}$.  Communications of the ACM, 64(11): 131–138, 2021.
DOI: 10.1145/3485628.

  * [KWW12] R. König, S. Wehner, and J. Wullschleger.  Unconditional security from noisy quantum storage.  IEEE Transactions on Information Theory, 58(3): 1962–1984, 2012\.
DOI: 10.1109/TIT.2011.2177772.

  * [LC97] H.-K. Lo and H. F. Chau.  Is quantum bit commitment really possible?  Physical Review Letters, 78(17): 3410–3413, 1997.
DOI: 10.1103/PhysRevLett.78.3410.

  * [LYW+11] H.-W. Li, Z.-Q. Yin, Y.-C. Wu, X.-B. Zou, S. Wang, W. Chen, G.-C. Guo, and Z.-F. Han.  Semi-device-independent random-number expansion without entanglement.  Phys. Rev. A, 84: 034301, 2011.
DOI: 10.1103/PhysRevA.84.034301.

  * [May96] D. Mayers.  The trouble with quantum bit commitment, 1996.
arXiv: quant-ph/9603015.

  * [MNP21] L. Mančinska, T. G. Nielsen, and J. Prakash.  Glued magic games self-test maximally entangled states, 2021.  Available at https://arxiv.org/abs/2105.10658.
  * [MY04] D. Mayers and A. Yao.  Self testing quantum apparatus.  Quantum Information & Computation, 4(4): 273–286, 2004.  Online: http://dl.acm.org/citation.cfm?id=2011827.2011830.
  * [MYS12] M. McKague, T. H. Yang, and V. Scarani.  Robust self-testing of the singlet.  Journal of Physics A, 45(45): 455304, 2012.
DOI: 10.1088/1751-8113/45/45/455304.

  * [NC00] M. A. Nielsen and I. L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2000.
  * [NPA08] M. Navascués, S. Pironio, and A. Acín.  A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations.  New Journal of Physics, 10(7): 073013, 2008.
DOI: 10.1088/1367-2630/10/7/073013.

  * [NV17] A. Natarajan and T. Vidick.  A quantum linearity test for robustly verifying entanglement.  In 49th Annual ACM Symposium on Theory of Computing—STOC 2017, pages 1003–1015, 2017.
DOI: 10.1145/3055399.3055468.

  * [Oza13] N. Ozawa.  About the Connes Embedding Conjecture—Algebraic approaches—, 2013.  Available at https://arxiv.org/abs/1212.1700.
  * [PB11] M. Pawłowski and N. Brunner.  Semi-device-independent security of one-way quantum key distribution.  Physical Review A, 84: 010302, 2011.
DOI: 10.1103/PhysRevA.84.010302.

  * [RUV13] B. W. Reichardt, F. Unger, and U. Vazirani.  Classical command of quantum systems.  Nature, 496: 456–460, 2013.
DOI: 10.1038/nature12035.

  * [Ser77] J.-P. Serre.  Linear representations of finite groups. Graduate texts in mathematics ; 042. Springer-Verlag, New York, 1977.
  * [SML10] D. Stebila, M. Mosca, and N. Lütkenhaus.  The case for quantum key distribution.  In Quantum Communication and Quantum Networking, volume 36, pages 283–296, 2010.
DOI: 10.1007/978-3-642-11731-2_35.

  * [SZB+21] L. K. Shalm, Y. Zhang, J. C. Bienfang, C. Schlager, M. J. Stevens, M. D. Mazurek, C. Abellán, W. Amaya, M. W. Mitchell, M. A. Alhejji, H. Fu, J. Ornstein, R. P. Mirin, S. W. Nam, and E. Knill.  Device-independent randomness expansion with entangled photons.  Nature Physics, 17: 452–456, 2021.
DOI: 10.1038/s41567-020-01153-4.

  * [TFKW13] M. Tomamichel, S. Fehr, J. Kaniewski, and S. Wehner.  A monogamy-of-entanglement game with applications to device-independent quantum cryptography.  New Journal of Physics, 15(10): 103002, 2013.
DOI: 10.1088/1367-2630/15/10/103002.

  * [Tom16] M. Tomamichel.  Quantum Information Processing with Finite Resources Mathematical Foundations.  SpringerBriefs in Mathematical Physics, 5. Springer International Publishing, Cham, 2016.
  * [Tsi93] B. S. Tsirelson.  Some results and problems on quantum Bell-type inequalities.  Hadronic Journal Supplement, 8: 329–345, 1993.
  * [Unr13] D. Unruh.  Everlasting multi-party computation.  In Advances in Cryptology—CRYPTO 2013, pages 380–397, 2013.
DOI: 10.1007/978-3-642-40084-1_22.

  * [Vid18] T. Vidick.  Expository note based on [NV17], 2018.  Online: http://users.cms.caltech.edu/~vidick/notes/pauli_braiding_1.pdf.
  * [VV12] U. V. Vazirani and T. Vidick.  Certifiable quantum dice: or, true random number generation secure against quantum adversaries.  In 44th Annual ACM Symposium on Theory of Computing—STOC 2012, pages 61–76, 2012.
DOI: 10.1145/2213977.2213984.

  * [Wat18] J. Watrous.  The Theory of Quantum Information.  Cambridge University Press, 1st edition, 2018.
  * [Wei03] S. H. Weintraub.  Representation theory of finite groups : algebra and arithmetic.  Graduate studies in mathematics, v. 59. American Mathematical Society, Providence, R.I, 2003.
  * [YXTZ14] Y.-G. Yang, P. Xu, J. Tian, and H. Zhang.  Quantum oblivious transfer with an untrusted third party.  Optik, 125(18): 5409–5413, 2014.
DOI: 10.1016/j.ijleo.2014.06.023.


HRI

    human-robot interaction
HCI

    human-computer interaction
HCD

    Human-Centered Design
UCD

    User-Centered Design
AI

    artificial intelligence
NDAs

    non-disclosure agreement
EMAR

    Ecological Momentary Assessment Robot

# Participatory Design for Mental Health Data
Visualization on a Social Robot

Raida Karim  University of Washington
Seattle, Washington, United States
<EMAIL_ADDRESS>Edgar Lopez  Elin A. Björling  University of
Washington
Seattle, Washington, United States
<EMAIL_ADDRESS>University of Washington
Seattle, Washington, United States
<EMAIL_ADDRESS>Maya Cakmak  University of Washington
Seattle, Washington, United States
<EMAIL_ADDRESS>
###### Abstract

The intersection of data visualization and human-robot interaction (HRI) is a
burgeoning field. Understanding, communicating, and processing different kinds
of data for creating versatile visualizations can benefit HRI. Conversely,
expressing different kinds of data generated from HRI through effective
visualizations can provide interesting insights. Our work adds to the
literature of this growing domain. In this paper, we present our exploratory
work on visualizing mental health data on a social robot. Particularly, we
discuss development of mental health data visualizations using a participatory
design (PD) approach. As a first step with mental health data visualization on
a social robot, this work paves the way for relevant further work and using
social robots as data visualization tools.

###### Index Terms:

Participatory design, mental health, community, data visualization, social
robots, human-robot interaction

##  I Introduction and Background

Despite many opportunities for collaborative research in data visualization
and HRI, not much work has been contributed to this intersection [6]. Some
existing works of this area include visualizing data of children’s touch
patterns on a social robot [5]. Contributing to this promising domain’s
literature, we worked on developing visualizations of mental health data for a
social robot. Social robots have been used to support mental health in various
ways such as to help children with autism improve on their social skills [1].
They have been used to help older adults by reducing feelings of loneliness
[3], and other populations. However, existing work only shows support for
mental health through social robots by responding interactively to human
activity to help them learn relevant skills. No work has shown the use of
social robots as a means of visualizing mental health data. Therefore, our
work is novel or first of its kind.

Figure 1: A line chart visualizing mood data (left) and a color-coded pie
chart visualizing stress data (right).

##  II A Social Robot & Mental Health Data

We detail here the procedure of collecting and visualizing mental health data
in these two respective stages:

###  II-A Data Collection

We conducted a five-weekdays HRI study in an American university campus with a
total of fifty-five (n=55) participants sharing their in-the-moment mood and
stress levels with a social robot. Our previous work [2] showed using an emoji
likert scale can enhance coherence and accessibility in portraying different
levels of mood or stress data, which is what we used. The users’ shared data
were stored in a secured firebase 111Firebase: https://firebase.google.com/.

###  II-B Data Visualization

We developed data visualization software with the updated static data
visualization template from [2] in our social robot’s software platform. These
visualizations are shown in Fig. 1, and were implemented in JavaScript using
AnyChart library 222AnyChart: https://www.anychart.com/. When the
visualization program is run on the robot, mood/stress data from firebase is
sent to visualization software and data visualizations are created in real-
time.

##  III Discussion

Mental health data visualizations with a social robot can potentially improve
mental health [2]. To the best of our knowledge, this is the first work
rendering mental health data visualizations on a social robot seeking to
alleviate mental health issues among users. Although this work has been
conducted with data collected from people of a university campus, collecting
and visualizing other community’s data can inform about distinct mental health
needs of each community. Moving forward, we plan to expand this work to other
community spaces such as high school, and public library. As mentioned
earlier, PD method was used to finalize design of data visualizations [2]. PD
helped us to get inputs from the community members in designing, developing
and refining the features of the robot-rendered data visualizations for mental
well-being. We have been using PD in our work for more than two years. We
choose to use PD methodology, because PD considers the intended users’ and
stakeholders’ participation throughout the design process and can result in
well-informed and usability-tested features of these data visualizations
rendered by a social robot. This can eventually help ensure the success of
such robotic technologies in supporting mental health. In [2], we used
qualitative analysis method to derive common themes in user feedback in the
initial data visualization templates, which informed Fig. 1 visualizations.

##  IV Conclusion & Future Directions

In this work, mental health data are visualized through the means of three
types of emojis and color codes in the line chart and the pie chart,
respectively (see Fig. 1). However, other types of mental health data might
generate other visualization designs. If a slider scale with a 10-pt likert
was used to collect mental health data in a quantitative measure, we might
have a scatter plot visualization with plotted numerical data points. More
abstract data might be visualized with Parallel Sets [4]. Finding the most
effective visualization to express mental health data collected and rendered
via social robots remains an open challenge. User studies can be conducted in
different community settings to examine human mental models towards these
robot-rendered visualizations. Incorporating feedback from the users might
lead to improved or future iterations of these visualization tools. This
visualization software is open-source 333Visualization software:
https://github.com/mayacakmak/emarsoftware so it can be adapted and used for
other research purposes, such as on robots of various shapes and sizes, and in
robot simulations if a physical robot is not accessible. This work marks a
first step towards collecting and visualizing mental health data on a social
robot at the convergence of HRI and data visualization. In the future, perhaps
more varieties of such data visualizations can be produced with the
applications of data integration and machine learning.

##  V Acknowledgements

This work was funded in part by National Science Foundation: National Robotics
Initiative, SES: Award Abstract 1734100 - Design and Development of a Social
Robot for Gathering Ecological Momentary Stress Data from Teens.

## References

  * [1] Sandra Costa et al.  “Where is your nose? - Developing body awareness skills among Children with Autism using a humanoid robot”, 2013
  * [2] Raida Karim et al.  “Community-Based Data Visualization for Mental Well-Being with a Social Robot”  In _Proceedings of the 2022 ACM/IEEE International Conference on Human-Robot Interaction_ , HRI ’22  Sapporo, Hokkaido, Japan: IEEE Press, 2022, pp. 839–843
  * [3] Ronald Kessler, Ellen Walters and Melinda Forthofer  “The Social Consequences of Psychiatric Disorders, III: Probability of Marital Stability”  In _The American journal of psychiatry_ 155, 1998, pp. 1092–6
  * [4] Robert Kosara, Fabian Bendix and Helwig Hauser  “Parallel Sets: Interactive Exploration and Visual Analysis of Categorical Data”  In _IEEE Transactions on Visualization and Computer Graphics_ 12.4 USA: IEEE Educational Activities Department, 2006, pp. 558–568
  * [5] Kris Rogers et al.  “Discovering patterns of touch: A case study for visualization-driven analysis in Human-Robot Interaction”, 2016, pp. 499–500
  * [6] Daniel Szafir and Danielle Albers Szafir  “Connecting Human-Robot Interaction and Data Visualization”  In _Proceedings of the 2021 ACM/IEEE International Conference on Human-Robot Interaction_ , HRI ’21  Boulder, CO, USA: Association for Computing Machinery, 2021, pp. 281–292