4 ms·

The title should be changed to say, generating cryptographically insecure random numbers with coins and a cup. Apply the von Neumann trick on top of the result

The title should be changed to say, generating cryptographically insecure random numbers with coins and a cup. Apply the von Neumann trick on top of the results and now we're talking. The real benefit here is the cup-based flipping technique creating independent trials.

Taek 6y ago
I'm guessing you didn't read the post? It covers the Von Neumann trick, why that doesn't work in practice, and then it also explains why using biased coins to generate random numbers results in real security when done correctly.
- SamReidHughes 6y ago
  I did read the post. A 5-coin Taek's Tornado is simply an insecure RNG if given biased coins. A one-time pad generated with it would not suffice. Not even if it has 127.6 bits of entropy in every 128 bits. If you take the 128-bit chunks they reference, and throw that through a cryptographic hash function, then you'd be safe (don't ask me to prove it). But they don't quite get there. They talk about using one as a way to avoid throwing away entropy, but not as a means of scrambling up the 128 biased bits into a suitable PRNG.
- JoshuaDavid 6y ago
  The tornado trick doesn't work if you don't combine it with the Von Neumann trick, though. > What we’re going to do is take 5 coins, ideally all of different shapes and sizes, and put them into a large cup. You want the cup to be large so that as you shake the coins around, the coins get jumbled in a highly random way. Give the cup 5 good shakes where the coins are tumbling around, and then dump the coins out and count the number of heads. If there are an even number of heads, record a ‘0’ for the random bit. If there are an odd number of heads, record a ‘1’ for the random bit. Consider the extreme case where all of the coins have a 0.1% chance of coming up heads: you have a 99.501% chance of getting 5 heads (odd), 0.498% chance of getting 4 heads and 1 tails (even), a 0.001% chance of getting 3 heads and 2 tails (odd), and a vanishingly small chance of getting 3 or more tails. So if you use the tornado trick with 5 coins that biased, your "random" bitstring is going to look something like "11111111111111...".
  - Taek 6y ago
    If your coins are 99.9% biased it means you are going to need more than 5 coins. Bias approaches zero exponentially fast as you add more coins, and in this case it means you'd need 1151 coins at 99.9% bias per coin to have a simulated coin with a bias of less than 55%. At 99% bias per coin you only need 114 coins, and at 90% bias you only need 11 coins. The main difference between the tornado trick and the von Neumann trick is how well they work in practice. In practice, coin tosses have at least a small amount of correlation, which breaks the von Neumann trick and gives you sloppy entropy. In the degenerate case, you might end up with almost no randomness despite using the von Neumann trick. In practice, coin flips in the tornado have a bias that is around 55% per coin, which means that 5 coins is more than enough to give you reliable entropy. The tornado trick is about trying to fit into the real world well, which means discarding fears of using coins that are 99.9% biased towards a particular outcome, since coins like that don't exist in common contexts.

Taek 6y ago

I'm guessing you didn't read the post? It covers the Von Neumann trick, why that doesn't work in practice, and then it also explains why using biased coins to generate random numbers results in real security when done correctly.

SamReidHughes 6y ago
I did read the post. A 5-coin Taek's Tornado is simply an insecure RNG if given biased coins. A one-time pad generated with it would not suffice. Not even if it has 127.6 bits of entropy in every 128 bits. If you take the 128-bit chunks they reference, and throw that through a cryptographic hash function, then you'd be safe (don't ask me to prove it). But they don't quite get there. They talk about using one as a way to avoid throwing away entropy, but not as a means of scrambling up the 128 biased bits into a suitable PRNG.
JoshuaDavid 6y ago
The tornado trick doesn't work if you don't combine it with the Von Neumann trick, though. > What we’re going to do is take 5 coins, ideally all of different shapes and sizes, and put them into a large cup. You want the cup to be large so that as you shake the coins around, the coins get jumbled in a highly random way. Give the cup 5 good shakes where the coins are tumbling around, and then dump the coins out and count the number of heads. If there are an even number of heads, record a ‘0’ for the random bit. If there are an odd number of heads, record a ‘1’ for the random bit. Consider the extreme case where all of the coins have a 0.1% chance of coming up heads: you have a 99.501% chance of getting 5 heads (odd), 0.498% chance of getting 4 heads and 1 tails (even), a 0.001% chance of getting 3 heads and 2 tails (odd), and a vanishingly small chance of getting 3 or more tails. So if you use the tornado trick with 5 coins that biased, your "random" bitstring is going to look something like "11111111111111...".
- Taek 6y ago
  If your coins are 99.9% biased it means you are going to need more than 5 coins. Bias approaches zero exponentially fast as you add more coins, and in this case it means you'd need 1151 coins at 99.9% bias per coin to have a simulated coin with a bias of less than 55%. At 99% bias per coin you only need 114 coins, and at 90% bias you only need 11 coins. The main difference between the tornado trick and the von Neumann trick is how well they work in practice. In practice, coin tosses have at least a small amount of correlation, which breaks the von Neumann trick and gives you sloppy entropy. In the degenerate case, you might end up with almost no randomness despite using the von Neumann trick. In practice, coin flips in the tornado have a bias that is around 55% per coin, which means that 5 coins is more than enough to give you reliable entropy. The tornado trick is about trying to fit into the real world well, which means discarding fears of using coins that are 99.9% biased towards a particular outcome, since coins like that don't exist in common contexts.