I have read about cryptography prgs. If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not?
Is there some principles I have to be based on while proving prgs?
$\begingroup$
$\endgroup$
-
$\begingroup$ Very, very closely related question. Duplicate? $\endgroup$ – Raphael♦ Jan 29 '17 at 16:45
-
1$\begingroup$ I can recommend reading the relevant chapters in Knuth's TAoCP. He discusses how we can define "randomness" in a useful way in quite some detail. (Arguably, every sequence of numbers is pseudo-random. Definining "randomness" is far from trivial!) $\endgroup$ – Raphael♦ Jan 29 '17 at 16:45
$\begingroup$
$\endgroup$
We don't know how to prove that a cryptographic PRNG exists. There are some candidate constructions, but they have not been proved to work. There are some results of the form "if X exists then so does a cryptographic PRNG", where X is some other cryptographic primitive, and the PRNG can be constructed explicitly from X. However, none of these other cryptographic primitives are known to exist. A particularly intriguing open question is to construct such a primitive which works merely under the assumption that P differs from NP.
On the other hand, proving that a generator is not a PRNG is much easier. You just need to give a distinguisher which has a non-negligible advantage in comparing the output of the generator to truly random output (as in the definition of a cryptographic PRNG).
answered Jan 29 '17 at 22:14
-
$\begingroup$ So let's consider the example I gave in the question, how would you prove it is not a prg? $\endgroup$ – Adi Ml Jan 29 '17 at 22:36
-
$\begingroup$ I would spend a few hours on it, and come up with an answer. $\endgroup$ – Yuval Filmus Jan 29 '17 at 22:38
$\begingroup$
$\endgroup$
You look for published tests that true random numbers pass, and check whether your generator passes those tests.
For example, if your generator produces real numbers in [0, 1), and you generate 1,000,000 numbers, then for every interval [0, 0.01), [0.01, 0.02) etc. there should be about 10,000 numbers in that interval. But not exactly, someone good at statistics will be able to tell you how far random numbers would deviate from "exactly 10,000 in each interval". So you would take the numbers produced by your generator and check them against that statistics.
That's a simple test. A good pseudo-random number generator would have consecutive numbers generated be independent of each other. Take three consecutive random numbers. They will be arranged in one of six possible numerical orders (a < b < c, a < c < b etc. ). Generate a 1,000,000 random numbers, with 999,998 triples, so each numerical order should be present about 166,666 times (again with some reasonable deviation). Check your generator against that.
PS. Yuval Films mentioned "cryptographic PRNG"s. That's a whole different beast. Usually random number generators are used for example for simulations; say to simulate a million cars driving through Los Angeles and what happens if we change traffic lights. If you use a PRNG to draw lotto numbers for real, then you need a PRNG that cannot be predicted, even if an attacker knows exactly how the random number generator is implemented, and has gazillions of previous numbers produced by the generator - you wouldn't want anyone to be able to predict the next lottery numbers. Depending on the application, being a cryptographic PRNG is either absolutely essential or of no value whatsoever.
-
$\begingroup$ You can view gnasher729's answer as one of the many definitions as Yuval suggested $\endgroup$ – Apiwat Chantawibul Jan 29 '17 at 20:24
-
$\begingroup$ Show me a definition. One that is better than "calculates a sequence of numbers that behave more or less as if they were random. " $\endgroup$ – gnasher729 Jan 29 '17 at 22:15
-
$\begingroup$ If you take this route, there is extensive literature on the topic, for example diehard. $\endgroup$ – Yuval Filmus Jan 29 '17 at 22:15
-
$\begingroup$ @gnasher729 You may want to check out TAoCP. It's not about CSPRNGs but you can find rigorous definitions for "behaves more or less as if they were random". $\endgroup$ – Raphael♦ Jan 29 '17 at 23:26
