Skip to main content
added 763 characters in body
Source Link
D.W.
  • 36.7k
  • 13
  • 105
  • 193

There is some relationship between the two notions, but a CSPRNG is designed to be computationally secure (secure against adversaries with bounded computation time), whereas a randomness extractor is required to be information-theoretically secure (unconditionally secure against adversaries with unbounded computation time). So, they're different primitives.

I would not expect a typical CSPRNG to be a secure randomness extractor. Typically CSPRNGs use computationally secure primitives, like AES etc.; they don't providemake any attempt or claims of providing security against adversaries with unlimited computing power.

Also, CSPRNGs are often designed to address other issues as well, such as recovery from state compromise (robustness against state compromise extension attacks), efficient use of the available entropy, and ability to stretch a finite amount of entropy into an unlimited stream of pseudorandom bits (e.g., using a PRG).

CSPRNGs are practical primitives, intended for applied cryptography, and were invented by applied cryptographers. Randomness extractors have typically been studied in the theoretical literature and are rarely (if ever) used in practice, for a variety of reasons, and were invented by theoreticians for studying fundamental theoretical questions. These differences reflect differences in the goals and values of those two communities.


We can also compare randomness extractors to pseudorandom generators (PRGs), but again, they're very different. PRG's are not designed to act as a randomness extractor, so there is no reason whatsoever to expect any particular PRG to do a good job at randomness extraction. Indeed, I'd expect that many secure PRG's might be perfectly good as a PRG but no good at all as a randomness extractor. The purpose of a randomness extractor is designed to take a non-uniformly distributed seed and turn it into a uniformly distributed output. That's very different from the task that PRG's are designed for. PRG's are designed to be secure if their seed is distributed uniformly at random. There is no guarantee whatsoever that they will be secure if the seed is distributed non-uniformly, and indeed, for some secure PRGPRGs, they might be insecure when used with a non-uniformly distributed CSPRNGseed.


In short, if you take a CSPRNG or a PRG, I would not expect it to necessarily act as a secure randomness extractor. They're just different things.

There is some relationship between the two notions, but a CSPRNG is designed to be computationally secure (secure against adversaries with bounded computation time), whereas a randomness extractor is required to be information-theoretically secure (unconditionally secure against adversaries with unbounded computation time). So, they're different primitives.

I would not expect a typical CSPRNG to be a secure randomness extractor. Typically CSPRNGs use computationally secure primitives, like AES etc.; they don't provide security against adversaries with unlimited computing power.


We can also compare randomness extractors to pseudorandom generators (PRGs), but again, they're very different. PRG's are not designed to act as a randomness extractor, so there is no reason whatsoever to expect any particular PRG to do a good job at randomness extraction. Indeed, I'd expect that many secure PRG's might be perfectly good as a PRG but no good at all as a randomness extractor. The purpose of a randomness extractor is designed to take a non-uniformly distributed seed and turn it into a uniformly distributed output. That's very different from the task that PRG's are designed for. PRG's are designed to be secure if their seed is distributed uniformly at random. There is no guarantee whatsoever that they will be secure if the seed is distributed non-uniformly, and indeed, for some secure PRG, they might be insecure when used with a non-uniformly distributed CSPRNG.


In short, if you take a CSPRNG or a PRG, I would not expect it to necessarily act as a secure randomness extractor. They're just different things.

There is some relationship between the two notions, but a CSPRNG is designed to be computationally secure (secure against adversaries with bounded computation time), whereas a randomness extractor is required to be information-theoretically secure (unconditionally secure against adversaries with unbounded computation time). So, they're different primitives.

I would not expect a typical CSPRNG to be a secure randomness extractor. Typically CSPRNGs use computationally secure primitives, like AES etc.; they don't make any attempt or claims of providing security against adversaries with unlimited computing power.

Also, CSPRNGs are often designed to address other issues as well, such as recovery from state compromise (robustness against state compromise extension attacks), efficient use of the available entropy, and ability to stretch a finite amount of entropy into an unlimited stream of pseudorandom bits (e.g., using a PRG).

CSPRNGs are practical primitives, intended for applied cryptography, and were invented by applied cryptographers. Randomness extractors have typically been studied in the theoretical literature and are rarely (if ever) used in practice, for a variety of reasons, and were invented by theoreticians for studying fundamental theoretical questions. These differences reflect differences in the goals and values of those two communities.


We can also compare randomness extractors to pseudorandom generators (PRGs), but again, they're very different. PRG's are not designed to act as a randomness extractor, so there is no reason whatsoever to expect any particular PRG to do a good job at randomness extraction. Indeed, I'd expect that many secure PRG's might be perfectly good as a PRG but no good at all as a randomness extractor. The purpose of a randomness extractor is designed to take a non-uniformly distributed seed and turn it into a uniformly distributed output. That's very different from the task that PRG's are designed for. PRG's are designed to be secure if their seed is distributed uniformly at random. There is no guarantee whatsoever that they will be secure if the seed is distributed non-uniformly, and indeed, for some secure PRGs, they might be insecure when used with a non-uniformly distributed seed.


In short, if you take a CSPRNG or a PRG, I would not expect it to necessarily act as a secure randomness extractor. They're just different things.

Source Link
D.W.
  • 36.7k
  • 13
  • 105
  • 193

There is some relationship between the two notions, but a CSPRNG is designed to be computationally secure (secure against adversaries with bounded computation time), whereas a randomness extractor is required to be information-theoretically secure (unconditionally secure against adversaries with unbounded computation time). So, they're different primitives.

I would not expect a typical CSPRNG to be a secure randomness extractor. Typically CSPRNGs use computationally secure primitives, like AES etc.; they don't provide security against adversaries with unlimited computing power.


We can also compare randomness extractors to pseudorandom generators (PRGs), but again, they're very different. PRG's are not designed to act as a randomness extractor, so there is no reason whatsoever to expect any particular PRG to do a good job at randomness extraction. Indeed, I'd expect that many secure PRG's might be perfectly good as a PRG but no good at all as a randomness extractor. The purpose of a randomness extractor is designed to take a non-uniformly distributed seed and turn it into a uniformly distributed output. That's very different from the task that PRG's are designed for. PRG's are designed to be secure if their seed is distributed uniformly at random. There is no guarantee whatsoever that they will be secure if the seed is distributed non-uniformly, and indeed, for some secure PRG, they might be insecure when used with a non-uniformly distributed CSPRNG.


In short, if you take a CSPRNG or a PRG, I would not expect it to necessarily act as a secure randomness extractor. They're just different things.