4 ms·

Can you explain what you mean by uniformity? I am having a hard time understanding your point; a long random bit string which is sampled from a uniform distribu

Can you explain what you mean by uniformity? I am having a hard time understanding your point; a long random bit string which is sampled from a uniform distribution will, indeed, have a pretty high likelihood of a short run of zeros or ones. You could reject runs (not sure why), but that would make the distribution less uniform, right?

john_alan 6y ago
I’m not saying short runs of 1 or 0 is not suitable for cryptographic use. I’m saying we always strive to remove any non-uniformity. Ie. Output of good CSPRNG will not have runs of one or the other. True hardware random generators regularly have runs or non-uniformity. That’s why we use them to seed a CSPRNG not use the output directly. Example https://crypto.stackexchange.com/questions/38053/what-should-be-used-as-a-source-for-entropy https://crypto.stackexchange.com/questions/38053/what-should...
- deleted 6y ago
  [deleted]
rurban 6y ago
An analogy: True randomness is uncompressable. If there are patterns, which could lead to compression tricks, it's not random anymore. Primitive runs like 0000000 are compressible patterns. Other patterns similarly, like 01010101, or 00110001110011. That's why you check generators visually by printing out bitmaps, and ideally by running it through a couple of compressors. Afaik this is not yet done by the 4 most common PRNG testsuites yet, but I'm working on it.
- john_alan 6y ago
  So you agree with me, uniformity is important?
  - rurban 6y ago
    Yes, but I don't like the abbrevated term that much. I prefer the Kolmogorov complexity, precisely a discrete uniform distribution. It's not only important, it's the only factor.
- Taek 6y ago
  A run like 0000000 is only compressible if it appears more often than it would in a fully random output. And in a fully random output, we would expect the run '0000000' to appear about once every 16 bytes. When you compress 0000000 to something smaller, you have to replace '0000000' in the plaintext with a smaller symbol in the squash text. Which means if that smaller symbol appears in the plaintext, you have to replace it with a larger symbol in the squash text. And if your smaller symbol appears more frequently than '0000000', you are going to end up with a "squash" text that is larger than the plaintext.

john_alan 6y ago

I’m not saying short runs of 1 or 0 is not suitable for cryptographic use. I’m saying we always strive to remove any non-uniformity. Ie. Output of good CSPRNG will not have runs of one or the other. True hardware random generators regularly have runs or non-uniformity. That’s why we use them to seed a CSPRNG not use the output directly. Example https://crypto.stackexchange.com/questions/38053/what-should-be-used-as-a-source-for-entropy https://crypto.stackexchange.com/questions/38053/what-should...

deleted 6y ago
[deleted]

rurban 6y ago

An analogy: True randomness is uncompressable. If there are patterns, which could lead to compression tricks, it's not random anymore. Primitive runs like 0000000 are compressible patterns. Other patterns similarly, like 01010101, or 00110001110011. That's why you check generators visually by printing out bitmaps, and ideally by running it through a couple of compressors. Afaik this is not yet done by the 4 most common PRNG testsuites yet, but I'm working on it.

john_alan 6y ago
So you agree with me, uniformity is important?
- rurban 6y ago
  Yes, but I don't like the abbrevated term that much. I prefer the Kolmogorov complexity, precisely a discrete uniform distribution. It's not only important, it's the only factor.
Taek 6y ago
A run like 0000000 is only compressible if it appears more often than it would in a fully random output. And in a fully random output, we would expect the run '0000000' to appear about once every 16 bytes. When you compress 0000000 to something smaller, you have to replace '0000000' in the plaintext with a smaller symbol in the squash text. Which means if that smaller symbol appears in the plaintext, you have to replace it with a larger symbol in the squash text. And if your smaller symbol appears more frequently than '0000000', you are going to end up with a "squash" text that is larger than the plaintext.