# 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]