7 ms·

> We show that if you have two low-quality random sources—lower quality sources are much easier to come by—two sources that are independent and have no correlat

> We show that if you have two low-quality random sources—lower quality sources are much easier to come by—two sources that are independent and have no correlations between them, you can combine them in a way to produce a high-quality random number "Independent and no correlations" sounds like a crippling assumption if you want to use any two deterministic PSRNGs. How can you possibly guarantee they're completely un-correlated and independent without seeding them with collectively more bits of entropy than you can get out of the combined system? I'm not sure what "independent" is even supposed to mean for a deterministic sequence, which by definition is recursively dependent.

deleted 10y ago
[deleted]
Aelinsaar 10y ago
So... this is a bit like the XKCD comic, killing cancer cells in a petri dish, with a handgun? That is to say, what a nice theory, but in practice you'll rarely if ever find the conditions are met for it to work?
- coldtea 10y ago
  No, it's just a misunderstanding of the paper.
  - Aelinsaar 10y ago
    Fair enough.
njohnson41 10y ago
That's because this result is not about combining weak deterministic PRNGs, it's about combining entropy sources (like two hardware random number generators). This has always been possible, but it sounds like they've lowered the minimum entropy needed in the source streams to produce a high-quality output.
- electrograv 10y ago
  Thanks for the explanation, that makes sense. I think this quote threw me off: > The academics’ latest work hurdles those restrictions allowing the use of sequences that are only weakly random What does "weakly random" mean, if not a PRNG? Just low pure entropy per bit of sequence data? What's the threshold then between strong random and weak random -- wouldn't it be a continuum of entropy? Minor nitpick: Also, how can a deterministic PRNG have less entropy (0) than that of its seed?
  - njohnson41 10y ago
    Right, the amount of entropy per bit of sequence is always between 0 (deterministic) and 1 (every bit is independent and 50/50) (... or between 0 and log2(k) in general if the element varies over a set of k things). These "weak" sources just have low entropy per bit. They could be biased (more 0s than 1s) or correlated (long runs of 0s/1s or periodicity), or just have some other pattern that sometimes holds. A deterministic PRNG's sequence has exactly the entropy of it's seed, actually, but it has 0 bits of entropy per symbol, because its sequence is infinite. The thing most people get confused about with entropy is in thinking that entropy is a property of some single object, like a bit string. Really, entropy is always a measurement about a probability distribution, just like mean or variance is. In the usual case with random streams, the distribution is P(x_i | x_i-1 ... x_0) for bits x_i in the stream, i.e. the distribution remaining for the current bit even if we know all previous bits. For a deterministic PRNG, once we can extract the key from the history (given unlimited compute power) that distribution becomes deterministic, so the entropy is 0.
    - dietrichepp 10y ago
      The entropy of a single object is a meaningful concept. It is usually called Kolmogorov complexity.
      - njohnson41 10y ago
        Kolmogorov complexity is definitely meaningful, but it's not (Shannon) entropy, just conceptually similar. Many people think of something like Kolmogorov-complex sequences when they think of "random" sequences, which is (IMO) why they have trouble thinking of entropy as being about a probability distribution. The one case where they coincide (sort of) is if you believe your random sequence is generated by a randomly chosen Turing machine, which I've only really seen in philosophical settings. A uniformly chosen 64-bit integer still has exactly 64 bits of entropy, regardless of how much Kolmogorov complexity the actual bits you generate have.
gizmo686 10y ago
A deterministic PSRNG has (by definition) 0 entropy, making them unfit for use as a source. The point of an extractor (such as the one being presented here) is to take two (or more) sources of low quality true randomness, and produce a high quality random output.
- garrettgrimsley 10y ago
  Isn't it the security of the seed that determines whether a CSPRNG is an appropriate source of entropy? I was under the impression that if your seed is secure and you're using a CSPRNG then there isn't a problem with using that generator as an entropy source.
  - dgacmu 10y ago
    No - you're mixing the terms "entropy" and "(pseudo)random bits". A CSPRNG can't be a source of entropy, period -- as noted above, it's always a deterministic function of its inputs. Entropy comes from truly unpredictable events, such as thermal noise, radioactive decay or cosmic radiation, etc. One uses a CSPRNG to generate a sequence of pseudorandom bits, wherein the sequence can only be predicted if the initial input to the CSPRNG is known (the "seed"). If you want a really "random" key, the usual trick is to "harvest" some entropy from the system (e.g., from hardware sources, such as mouse timings, or dedicated hardware random generators based upon things believed to be physically random), condition it (make it uniformly distributed, unbiased, etc.), and then use those harvested "truly random" bits to seed your CSPRNG.
    - garrettgrimsley 10y ago
      Got it, thanks!
    - tptacek 10y ago
      Real, sound cryptosystems routinely --- in fact, almost invariably --- source their keys from CSPRNGs. CSPRNGs can't source entropy, as you say, but in cryptography we're not looking for entropy. We're looking for unpredictability. What confuses people is that cryptography usually jumpstarts itself with a small amount of entropy (or something close enough to entropy to count). That small seed of entropy gives us unpredictability for the life of the system, even though the bits we actually use will come from deterministic processes.

deleted 10y ago

[deleted]

Aelinsaar 10y ago

So... this is a bit like the XKCD comic, killing cancer cells in a petri dish, with a handgun? That is to say, what a nice theory, but in practice you'll rarely if ever find the conditions are met for it to work?

coldtea 10y ago
No, it's just a misunderstanding of the paper.
- Aelinsaar 10y ago
  Fair enough.

njohnson41 10y ago

That's because this result is not about combining weak deterministic PRNGs, it's about combining entropy sources (like two hardware random number generators). This has always been possible, but it sounds like they've lowered the minimum entropy needed in the source streams to produce a high-quality output.

electrograv 10y ago
Thanks for the explanation, that makes sense. I think this quote threw me off: > The academics’ latest work hurdles those restrictions allowing the use of sequences that are only weakly random What does "weakly random" mean, if not a PRNG? Just low pure entropy per bit of sequence data? What's the threshold then between strong random and weak random -- wouldn't it be a continuum of entropy? Minor nitpick: Also, how can a deterministic PRNG have less entropy (0) than that of its seed?
- njohnson41 10y ago
  Right, the amount of entropy per bit of sequence is always between 0 (deterministic) and 1 (every bit is independent and 50/50) (... or between 0 and log2(k) in general if the element varies over a set of k things). These "weak" sources just have low entropy per bit. They could be biased (more 0s than 1s) or correlated (long runs of 0s/1s or periodicity), or just have some other pattern that sometimes holds. A deterministic PRNG's sequence has exactly the entropy of it's seed, actually, but it has 0 bits of entropy per symbol, because its sequence is infinite. The thing most people get confused about with entropy is in thinking that entropy is a property of some single object, like a bit string. Really, entropy is always a measurement about a probability distribution, just like mean or variance is. In the usual case with random streams, the distribution is P(x_i | x_i-1 ... x_0) for bits x_i in the stream, i.e. the distribution remaining for the current bit even if we know all previous bits. For a deterministic PRNG, once we can extract the key from the history (given unlimited compute power) that distribution becomes deterministic, so the entropy is 0.
  - dietrichepp 10y ago
    The entropy of a single object is a meaningful concept. It is usually called Kolmogorov complexity.
    - njohnson41 10y ago
      Kolmogorov complexity is definitely meaningful, but it's not (Shannon) entropy, just conceptually similar. Many people think of something like Kolmogorov-complex sequences when they think of "random" sequences, which is (IMO) why they have trouble thinking of entropy as being about a probability distribution. The one case where they coincide (sort of) is if you believe your random sequence is generated by a randomly chosen Turing machine, which I've only really seen in philosophical settings. A uniformly chosen 64-bit integer still has exactly 64 bits of entropy, regardless of how much Kolmogorov complexity the actual bits you generate have.

gizmo686 10y ago

A deterministic PSRNG has (by definition) 0 entropy, making them unfit for use as a source. The point of an extractor (such as the one being presented here) is to take two (or more) sources of low quality true randomness, and produce a high quality random output.

garrettgrimsley 10y ago
Isn't it the security of the seed that determines whether a CSPRNG is an appropriate source of entropy? I was under the impression that if your seed is secure and you're using a CSPRNG then there isn't a problem with using that generator as an entropy source.
- dgacmu 10y ago
  No - you're mixing the terms "entropy" and "(pseudo)random bits". A CSPRNG can't be a source of entropy, period -- as noted above, it's always a deterministic function of its inputs. Entropy comes from truly unpredictable events, such as thermal noise, radioactive decay or cosmic radiation, etc. One uses a CSPRNG to generate a sequence of pseudorandom bits, wherein the sequence can only be predicted if the initial input to the CSPRNG is known (the "seed"). If you want a really "random" key, the usual trick is to "harvest" some entropy from the system (e.g., from hardware sources, such as mouse timings, or dedicated hardware random generators based upon things believed to be physically random), condition it (make it uniformly distributed, unbiased, etc.), and then use those harvested "truly random" bits to seed your CSPRNG.
  - garrettgrimsley 10y ago
    Got it, thanks!
  - tptacek 10y ago
    Real, sound cryptosystems routinely --- in fact, almost invariably --- source their keys from CSPRNGs. CSPRNGs can't source entropy, as you say, but in cryptography we're not looking for entropy. We're looking for unpredictability. What confuses people is that cryptography usually jumpstarts itself with a small amount of entropy (or something close enough to entropy to count). That small seed of entropy gives us unpredictability for the life of the system, even though the bits we actually use will come from deterministic processes.