Coin Flipping

参考：Weak coin flipping with small bias, Iordanis Kerenidis and Ashwin Nayak

我们考虑要做这样一件事情：Alice 和 Bob 要通过一个 two-party communication protocol，分别算出自己的 output bit $c_A,c_B\in\{0,1\}$。如果输出满足$c_A=c_B$，那么我们说这个 protocol 是 successful 的。
在 successful 的前提下，如果$c_A=c_B=0$，那么认为 Alice 赢，如果$c_A=c_B=1$，那么认为 Bob 赢。

一个 weak coin flipping protocol 需要满足以下两个性质：

1. Fairness：如果双方都是 honest（遵守 protocol），那么$\Pr(c_A=c_B=0)=\Pr(c_A=c_B=1)=\frac{1}{2}$;
2. Small bias：如果 Alice 不是 honest 的，那么她获胜的概率将$\Pr(c_A=c_B=0)\leq\frac{1}{2}+\epsilon$；同理如果 Bob 不是 honest 的，那么他获胜的概率将$\Pr(c_A=c_B=1)\leq\frac{1}{2}+\epsilon$。这里的$\epsilon$ 称为 bias。

类似地有 strong coin flipping protocol，区别在于此时 Alice 和 Bob 不再分别偏向一个 bit 来决定胜负，而是要求：

1. 如果双方都 honest，那么 output bit 仍然$\Pr(c_A=c_B=0)=\Pr(c_A=c_B=1)=\frac{1}{2}$（和 weak 情形一样）；
2. 如果某一方 dishonest，那么结果偏向任何一个值（0 或 1）的概率都不会超过$\Pr(c_A=c_B=0/1)\leq \frac{1}{2}+\epsilon$。

很显然如果我们有一个 strong coin flipping protocol，那么可以直接自然诱导出一个 weak coin flipping protocol。
这只需要运行 strong coin flipping protocol，然后直接输出 output bit。
如果双方都 honest，那么显然输出的 bit 以$1/2$ 的概率为 0 或 1，满足 fairness；如果一方 dishoest，那么由于 strong coin flipping protocol 的性质，输出偏向 0 或 1 的概率都不会超过$1/2+\epsilon$，所以他获胜的概率也不会超过$1/2+\epsilon$，满足 small bias。

如果有一个 weak coin flipping protocol，我们也能构造出一个 strong coin flipping protocol，但是会导致 bias 变大。
具体地，考虑这样一个 protocol：先运行 weak coin flipping protocol，然后令赢家均匀随机选择输出 0 或 1 并发送给输方作为最终 output bit。
如果双方都 honest，显然最终 output bit 仍然是均匀分布的，满足 fairness。否则如果一方不 honest，譬如 Alice 不 honest，那么她在 weak coin flipping protocol 中获胜的概率为$p_w\leq\frac{1}{2}+\epsilon$（由 weak coin flipping protocol 要求），那么她完全可以不均匀随机掷硬币，而是直接输出 0。假设 Bob 获胜的概率是$p_l$（不一定等于$1-p_w$，因为 dishonest 可能导致 protocol 失败），Bob 获胜时还是会老老实实地均匀随机选择输出 0 或 1。那么最终 output bit 为 0 的概率为$p_w+\frac{1}{2}p_l$, 即此时 bias 为$p_w+\frac{1}{2}p_l-\frac{1}{2}=p_w+\frac{p_l-1}{2}\leq \epsilon+p_l/2$。

---

接下来我们考虑一个 weak coin flipping protocol with bias $<1/4$。
这个 protocol 先依赖于一个参数$\alpha\in[0,1]$，后面我们会对其进行最优化。
对于$x,s\in \{0,1\}$，定义$\mathcal{H}_s\otimes\mathcal{H}_t\cong \mathbb{C}^2\otimes \mathbb{C}^3$ 上的状态

$$\begin{aligned} & |\psi_{x,s}\rangle=\cos\frac{\alpha}{2}|0\rangle+(-1)^s\sin\frac{\alpha}{2}|x+1\rangle,\\ & |\psi_x\rangle=\frac{1}{\sqrt{2}}(|0\rangle|\psi_{x,0}\rangle+|1\rangle|\psi_{x,1}\rangle). \end{aligned}$$

Protocol 如下进行：

1. Alice 均匀随机选取一个$a\in\{0,1\}$，然后制备状态$|\psi_a\rangle$，并把第二个 qutrit 发送给 Bob；
2. Bob 均匀随机选取一个$b\in\{0,1\}$，然后发送给 Alice；
3. Alice 然后把$a$ 发送给 Bob，令$c=a\oplus b$。
4. 如果$c=0$，那么 Alice 输出$c_A=0$ 并且把第一个 qubit 也发送给 Bob。然后 Bob 可以直接测量手中的 qubit-qutrit pair 以 check 它在 pure state $|\psi_a\rangle$，如果是的那么也输出$c_B=0$ 此时 Alice 赢；否则 Bob 认为 Alice 作弊。
5. 如果$c=1$，那么 Bob 输出$c_B=1$ 并且把手中的 qutrit 还给 Alice。然后 Alice 可以直接测量手中的 qubit-qutrit pair 以 check 它在 pure state $|\psi_a\rangle$，如果是的那么也输出$c_A=1$ 此时 Bob 赢；否则 Alice 认为 Bob 作弊。

接下来我们分析这个 protocol。

Proof: 不失一般性地我们认为 Alice 尽可能地想获胜。
Alice 最一般的作弊策略如下：Alice 引入一个 auxiliary space $\mathcal{H}$，并制备一个状态$|\psi\rangle\in \mathcal{H}\otimes \mathcal{H}_s\otimes\mathcal{H}_t$，然后她在第一步把$\mathcal{H}_t$ 部分发送给 Bob。此时我们记 Bob 手中的状态为$\sigma=\mathrm{Tr}_{\mathcal{H}\otimes\mathcal{H}_s}(|\psi\rangle\langle\psi|)$。

然后在第 3 步中，为了让自己能赢，Alice 会无脑地发送$a=b$ 给 Bob 来确保$c=0$，然后通过操纵手中的状态使得尽量通过 Bob 的 check。Alice 需要根据 Bob 发来的$b$ 操作一个 unitary 得到状态

$$|\tilde{\psi}_b\rangle=(U_b\otimes I_{\mathcal{H}_t})|\psi\rangle=\sum_i \sqrt{p_i}|i\rangle|\tilde{\psi}_{i,b}\rangle,$$

那么此时 Alice 通过 Bob 的 check 的概率就是 Bob measure 得到$|\psi_b\rangle$（因为 Alice 发给 Bob 的是$a=b$），即

$$\begin{aligned} \Pr[\text{Alice wins}\mid \text{Bob sends }b]&=\sum_i p_i|\langle\psi_b|\tilde{\psi}_{i,b}\rangle|^2\\ &=F(\sigma_b,|\psi_b\rangle\langle\psi_b|)\\ &\leq F(\mathrm{Tr}_{\mathcal{H}_s}(\sigma_b),\mathrm{Tr}_{\mathcal{H}_s}(|\psi_b\rangle\langle\psi_b|))\\ &=F(\sigma,\rho_b), \end{aligned}$$

其中$F$ 是 fidelity，$\sigma_b=\sum_i p_i |\tilde{\psi}_{i,b}\rangle\langle\tilde{\psi}_{i,b}|$。注意到 Alice 只能作用$U_b\otimes I$，因此在 trace out 掉$\mathcal{H}_s$ 后，剩下的就是 Bob 在第 1 轮就拿在手里的状态$\sigma$。而且

$$\rho_b=\mathrm{Tr}_{\mathcal{H}_s}(|\psi_b\rangle\langle\psi_b|)=\cos^2\frac{\alpha}{2}|0\rangle\langle 0|+\sin^2\frac{\alpha}{2}|b+1\rangle\langle b+1|.$$

因此 Alice 最终获胜的概率为

$$\begin{aligned} \Pr[\text{Alice wins}]&=\frac{1}{2}(\Pr[\text{Alice wins}\mid \text{Bob sends }0]+\Pr[\text{Alice wins}\mid \text{Bob sends }1])\\ &=\frac{1}{2}(F(\sigma,\rho_0)+F(\sigma,\rho_1))\\ &\leq \frac{1}{2}\left(1+\sqrt{F(\rho_0,\rho_1)}\right)\\ &=\frac{1}{2}\left (1+\cos^2\frac{\alpha}{2}\right ), \end{aligned}$$

其中$F(\rho_0,\rho_1)=\|\sqrt{\rho_0}\sqrt{\rho_1}\|_{\mathrm{Tr}}^2$。
这个界是紧的，因为 Alice 之需要制备$|\psi_0\rangle+|\psi_1\rangle$ 的归一化态，然后把第二个 qutrit 发给 Bob 即可。
$\square$

Proof: Bob 如果作弊，那么他在第一轮得到$|\psi_a\rangle$ 的第二个 qutrit 后，就要尝试去猜测$a$ 的值以便在第 2 轮发送$b=a\oplus 1$ 来确保$c=1$ 从而获胜。但是这个猜测过程还要对 qutrit 进行尽量小的扰动，否则 Alice 在最后的 check 中会发现异常从而判定 Bob 作弊。

Bob 这样做：他也引入 auxiliary space $\mathcal{H}\otimes \mathbb{C}^2$，然后作用一个 unitary $U$，在基态上如此定义（下面$|i\rangle$ 是$\mathcal{H}_t$ 的一个 basis）：

$$U:|i\rangle|0\rangle|0\rangle\mapsto |\phi_{i,0}\rangle|0\rangle+|\phi_{i,1}\rangle|1\rangle.$$

然后 Bob 测量最后一个 qubit，并把它的值还给 Alice。如果碰巧$c=1$，那么就把对应的 qutrit 部分发送给 Alice。
假设 Alice 选了$a$, 那么 Bob 获胜的概率为（相当于只算了$U$ 作用在$|\psi_a\rangle$ 上时，对应的$|\phi_{i,\bar{a}}\rangle$ 部分的 norm 平方和）：

$$\begin{aligned} &\left \| (\langle\psi_a|\otimes I_{\mathcal{H}})\cdot \frac{1}{\sqrt{2}}\left (|0\rangle\left (\cos\frac{\alpha}{2}|\phi_{0,\bar{a}}\rangle+\sin\frac{\alpha}{2}|\phi_{a+1,\bar{a}}\rangle\right ) + |1\rangle\left (\cos\frac{\alpha}{2}|\phi_{0,\bar{a}}\rangle-\sin\frac{\alpha}{2}|\phi_{a+1,\bar{a}}\rangle\right )\right )\right \|^2\\ =&\frac{1}{4}\left \| (\langle\psi_{a,0}|\otimes I_{\mathcal{H}})\cdot \left (\cos\frac{\alpha}{2}|\phi_{0,\bar{a}}\rangle+\sin\frac{\alpha}{2}|\phi_{a+1,\bar{a}}\rangle\right ) + (\langle\psi_{a,0}|\otimes I_{\mathcal{H}})\cdot\left (\cos\frac{\alpha}{2}|\phi_{0,\bar{a}}\rangle-\sin\frac{\alpha}{2}|\phi_{a+1,\bar{a}}\rangle\right )\right \|^2\\ =&\left \| \cos^2\frac{\alpha}{2}(\langle 0|\otimes I)|\phi_{0,\bar{a}}\rangle+\sin^2\frac{\alpha}{2}(\langle a+1|\otimes I)|\phi_{a+1,\bar{a}}\rangle\right \|^2\\ \leq& \left (\cos^2\frac{\alpha}{2}\|(\langle 0|\otimes I)|\phi_{0,\bar{a}}\rangle\|+\sin^2\frac{\alpha}{2}\|(\langle a+1|\otimes I)|\phi_{a+1,\bar{a}}\rangle\|\right )^2\\ \leq&\left (\cos^2\frac{\alpha}{2}\||\phi_{0,\bar{a}}\rangle\|+\sin^2\frac{\alpha}{2}\||\phi_{a+1,\bar{a}}\rangle\|\right )^2\\ \leq& \left (\cos^2\frac{\alpha}{2}\||\phi_{0,\bar{a}}\rangle\|+\sin^2\frac{\alpha}{2}\right )^2.\\ \end{aligned}$$

现在回看 Bob 获胜的概率，实际上是$a=0$ 和$a=1$ 时上式子的平均值。此外根据定义，我们知道$\|\phi_{0,0}\|^2+\|\phi_{0,1}\rangle\|^2=1$，因此最大值取在$\|\phi_{0,0}\rangle\|=\|\phi_{0,1}\rangle\|=1/\sqrt{2}$ 上。此时获胜概率为

$$\left (\frac{1}{\sqrt{2}}\cos^2\frac{\alpha}{2}+\sin^2\frac{\alpha}{2}\right )^2.$$

$\square$

同样 Bob 也有一个作弊策略达到这个获胜概率。Bob 在第一轮获得 qutrit 后，可以引入一个 auxiliary qubit 并进行如下一个变换：

$$\begin{aligned} & |0\rangle|0\rangle\mapsto |0\rangle\otimes\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle),\\ & |x+1\rangle|0\rangle\mapsto |x+1\rangle|x\rangle,\quad x\in\{0,1\}. \end{aligned}$$

然后他 measure 最后一个 qubit 作为$b$ 发送给 Alice。

综上所述，我们知道$\alpha$ 从$0$ 到$\pi$ 变化时，Alice 和 Bob 的获胜概率分别减小和增大。当

$$\frac{1}{2}+\frac{1}{2}\cos^2\frac{\alpha}{2}=\left (\frac{1}{\sqrt{2}}\cos^2\frac{\alpha}{2}+\sin^2\frac{\alpha}{2}\right )^2$$

时，Alice 和 Bob 的获胜概率都是 0.739 左右，此时 bias 为 0.239 小于$1/4$。