40 lines
2.9 KiB
Markdown
40 lines
2.9 KiB
Markdown
# Strong Coin Flipping
|
|
|
|
- [[quantum-computing]]
|
|
- [[cryptography]]
|
|
- problem: Alice and Bob spatially separated & want to jointly agree on a coin flip result
|
|
- Alice flips coin and tells Bob: Alice cheats probability 1
|
|
- Alice and Bob both flip a coin and take the XOR: whoever communicates last cheats probability 1
|
|
- bad quantum protocol
|
|
- Alice picks $`\ket{\psi}`$ as either $`\ket{b=0} = \ket{0} + \ket{1}`$ or $`\ket{b=1} = \ket{0} + \ket{2}`$ and sends $`\ket{\psi}`$ to Bob
|
|
- $`\left(\bra{0}+\bra{2}\right)\left(\ket{0}+\ket{1}\right) = \frac{1}{2}`$
|
|
- Bob picks a random bit $`b' \in_\mathbb{R} \left\{0,1\right\}`$
|
|
- Alice decides the coin flip $`C = b \oplus b'`$ and sets $`b`$ to Bob
|
|
- because Bob has $`\ket{\psi}`$, Bob can verify Alice's commitment to $`b`$, but because he doesn't have $`b'`$ until receiving $`\ket{\psi}`$ he cannot choose an advantageous $`b'`$
|
|
- Alice can cheat with success probability $`\left(\cos\left(30\deg\right)\right)^2=\frac{3}{4}`$ by sending $`2\ket{0} + \ket{1} + \ket{2}`$ and picking a $`b`$
|
|
- Bob can cheat with success probability $`\left(\cos\left(15\deg\right)\right)^2 \approx 93.3\%`$ by measuring $`\ket{\psi}`$ early, assuming Alice will be honest, and sending a $`b'`$ he chooses with the information from the measurement
|
|
- okay quantum protocol
|
|
- in the above protocol, Bob is more likely to cheat than Alice
|
|
- we can balance these two things by moving the $`15\deg`$ and $`30\deg`$ angles both to $`22.5\deg`$
|
|
- that is, $`\braket{b=0|b=1} = \cos\left(22.5\deg\right)`$, so the probability of either party successfully cheating is $`\left(\cos\left(22.5\deg\right)\right)^2 \approx 85.4\%`$
|
|
- good quantum protocol
|
|
- we can improve the probability of either party successfully cheating to be only 75%
|
|
- this is close to optimal: the optimal protocol has a successful probability of $`\frac{1}{\sqrt{2}}`$
|
|
- this lower bound is hard to prove and out of scope for the course
|
|
- Alice picks a $`b \in_\mathbb{R} \left\{0,1\right\}`$ and an $`x \in_\mathbb{R} \left\{0,1\right\}`$
|
|
- Alice sends $`\ket{\psi} = \ket{b,x}`$ to Bob
|
|
- $`\ket{b=0,x=0} = \ket{0} + \ket{1}`$
|
|
- $`\ket{b=0,x=1} = \ket{0} - \ket{1}`$
|
|
- $`\ket{b=1,x=0} = \ket{0} + \ket{2}`$
|
|
- $`\ket{b=1,x=1} = \ket{0} - \ket{2}`$
|
|
- Bob responds with $`b'`$
|
|
- Alice responds with $`b, x`$ and $`C = b \oplus b'`$
|
|
- Bob can cheat by measuring in the computational basis
|
|
- Bob will measure $`\ket{0}`$, $`\ket{1}`$, or $`\ket{2}`$
|
|
- Bob will, with probability $`\frac{1}{2}`$, get $`\ket{0}`$, which allows him to cheat with $`50\%`$ accuracy, or with probability $`\frac{1}{2}`$ learn $`b`$ which guarantees him a successful cheating opportunity
|
|
- this is a $`75\%`$ success rate
|
|
- Consider Alice sending pure states with probability
|
|
- $`\ket{0}`$, probability 2/3
|
|
- $`\ket{1}`$, probability 1/6
|
|
- $`\ket{2}`$, probability 1/6
|
|
- [proof didn't make it into today's lecture in time]
|