1
$\begingroup$

As an example, if a PRNG passes the BigCrush test suite, and has a period of 2^1024, can it be used on its own to make a secure stream cipher?

What are the required properties, and similarly, what are the bad properties that the PRNG must not have?

$\endgroup$
6
$\begingroup$

The best known algorithm to guess the next bit with probability near 1, without knowing the $n$-bit seed, has to cost approximately $2^\lambda$ bit operations, where $\lambda \leq n$ is the security parameter.

You can't determine this by feeding the output of the PRNG to a generic statistical hypothesis test, because by its very nature that statistical hypothesis test has only very limited hypotheses about how the PRNG might differ from a uniform random string of bits. These generic statistical hypothesis tests are designed without particular knowledge of the PRNG.

You can really determine this only by feeding it to a swarm of cryptographers, but that works only if it appears as tasty to cryptographers as a bleeding hand to a piranha.

Cryptographers are a picky bunch that aren't much interested in spending their time on designs that aren't really interesting for some reason, like protecting trillions of euros of financial transactions, or performing better than modern standard stream ciphers today (like ChaCha, or AES-CTR with hardware acceleration) at the same conjectured security level.

And they don't usually want to spend time on designs whose designers haven't already studied and demonstrated to resist a litany of standard attack strategies.

$\endgroup$
3
  • $\begingroup$ Shouldn't it be 2^(security parameter)? Some PRNG require large seed (more than 1000 bits) to reach, say, 128 bits of security, but from a theoretical point of view they should still be fine to build a stream cipher $\endgroup$ – Geoffroy Couteau Dec 25 '17 at 11:38
  • $\begingroup$ Yes…but why would you bother with a stream cipher that requires such a large key? $\endgroup$ – Squeamish Ossifrage Dec 26 '17 at 1:49
  • $\begingroup$ Because it can have other nice properties in exchange for this large key. The one I was thinking about is Goldreich's PRG (and its many variants, the original one being too extreme to build a stream cipher), which is local (every output bit depends on a constant number of input bits), hence highly parallelizable. Such PRNG have many applications in theoretical crypto; in particular they lead to MPC- and FHE-friendly stream ciphers. $\endgroup$ – Geoffroy Couteau Dec 26 '17 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.