2.9 KiB
2.9 KiB
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
- Alice picks
- 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
- this is close to optimal: the optimal protocol has a successful probability of
- 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
- Bob will measure
- 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]
- we can improve the probability of either party successfully cheating to be only 75%