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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI 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?
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).
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.