3 ms·
About 3/4 of the way down, in response to: "The central idea in all of these protocols is simply to be stingy with the use of randomness. We ask Alice and Bob t
by dj-wonk 12y ago
About 3/4 of the way down, in response to: "The central idea in all of these protocols is simply to be stingy with the use of randomness. We ask Alice and Bob to play the CHSH game over and over again. However, in almost all of the plays, they simply both receive red cards—leading to a boring but also “cheap” (in terms of randomness) game. Only for a few randomly chosen plays does one of them receive a blue card."
If this is true, then these "clever" protocols are breaking the 50/50 rule of the CHSH game. Right?
- greeneggs 12y agoYes. In the normal CHSH game, the questions to the players Alice and Bob are independent random bits (50/50, as you say). That's a problem, though, if you want to create new randomness, because you put into the game two random bits and you get out less than two random bits! If you want to get out more randomness than you put in, you need to be a little more clever and more stingy with using random bits. (If the players are honest, the first player's output is uniformly random, but the second player's output is ~85% predictable given the first player's output. Measured in terms of entropy, this means you are getting a fraction more than 1 bit out.) The standard 50/50 CHSH is still useful for generating randomness, though. Even though it uses up more randomness than it creates, the output randomness can be of higher quality than the input randomness. More precisely, if the input bits are independent to the players Alice and Bob, but perhaps are known to an outside adversary, the game's output bits will be unknown to the adversary.