Algorithmic distinctions between random and pseudorandom.

Question

Given a specific pseudo random number generator (e.g. Mersenne twister) $r()$ and a true random number generator $q()$ is there an algorithm $f(x,y)$ such that:

• $f(r(),r()) = 1$ almost always.
• $f(q(),q()) = 0$ almost always.

It should be noted that $f()$ stores no state, it only takes the return values of two consecutive calls as its parameter: we can also consider the case of a vector of $n$ calls as input.

"almost always" may be interpreted quite liberally, it could return this result with $> 2/3$ probability or the long term average could tend towards this limit.

I would also appreciate any insight on the same question for an unknown pseudo-random number generator (i.e. an arbitrary Turing machine) as $r()$. Thanks very much!

Answer 1

If you just consider consecutive samples then, for most kinds of PRNGs the answer is that you can't distinguish them from true RNGs.

If you consider large input samples, then, in principle (if you don't take complexity issues into account), you can always distinguish a PRNG from true randomness:

For each PRNG $r$, seed length $L$ and starting point $x$ there exist a sample sequence length $k$ such that $f([r(seed, x),\ r(seed, x+1),\ \dots,\ r(seed, x+k-1)])\ =\ 1$ with certainty, and $f(\dots)\ =\ 0$ for any other sequence, where $r(seed, n)$ is the n-th sample generated by the PRNG initialized with $seed$.

If the PRNG has finitely many states, as it is the case with all the PRNGs commonly in use, then the sample sequence length $k$ is independent of the seed length and starting point.

The distinguishing algorithm $f(\cdot,\ \cdot)$ can be just a brute-force search that tries in order all possible initial states to check whether they produce the sample sequence. Of course, for large state spaces, this is unpractical. Moreover, the output sequence of a finite-state PRNG is periodic or eventually becomes periodic, although the period can be very large.

The design goal of cryptographically-secure PRNGs is to ensure that no method substantially faster than brute-force search can be used to distinguish them from true RNGs. Currently, various PRNGs are believed to be cryptographically-secure, though no mathematical proof exists.

Cryptographically-insecure PRNGs like the Mersenne Twister can be easily distinguished from true RNGs by observing a relatively short sample sequence.

Answer 2

Perhaps I misunderstand what you mean to ask here, but the answer seems to be trivial for the case of $f()$ with only two inputs consisting of consecutive calls to the random number generator, as described in the question. The answer depends purely on whether or not the function can be defined recursively. This is because the distribution of outputs of $f$ depends only on the coincidence probability of two numbers produced by the generator. In the case where $q(n) = g(q(n-1))$ for some function $g$, then trivially, the boolean function $f(v_1,v_2) = (v_2==g(v_1))$ returns 1 with unit probability when $v_1$ and $v_2$ are sequential calls to the PRNG. However, if these are chosen uniformly at random, then the function will only return 1 probability $1/N$, where $N$ is the number of possible choices for each number $v_i$.

Trivially, you can extend this to non-uniform distributions. The probability of $f$ returning 1 for $v_1 = r(), v_2 = r()$ then is $\sum_{i=1}^{N} P(i) P(g(i)|i)$, where $P(i)$ is the probability of picking element $i$ in the distribution, and $P(j|i)$ is the probability of picking $j$ conditioned on the previous choice being $i$.

In general (for potentially non-uniform distributions and non-recursively defined functions), the ability produce a function satisfying your requirements simply depends on whether or not $P_q(i) P_q(j|i) = P_r(i)P_r(j|i) \forall i,j$, where the the subscript denotes the function $r()$ or $q()$ used to generate the numbers when averaged over all time. You can easily use this to calculate the maximum probability of correctly identifying the function used.

Lastly, you mention extending beyond two calls of the function. This is essentially the same problem, except now you need to consider whether $P_q(i) P_q(j|i)...P_q(z|...|j|i) = P_r(i)P_r(j|i)...P_r(z|...|j|i)$. Here again taking the equality function will work for any PRNG for which $q(i+n) = g(q(i+1),...,q(i+n-1))$.

Of course, if you allow a memory, then you can use preprocessing to determine the parameters of the PRNG, which changes the situation drastically. Whether the PRNG is known or unknown doesn't change whether or not f() exists, but simply how easy it is to infer it.

Answer 3

If $f$ stores no state, then I think the answer will be "no". In that case, $f$ is just a function mapping $f: \{0,1\}^2 \rightarrow \{0,1\}$. If $f$ can be randomized, then you can just view it as a function $f: \{0,1\}^2 \rightarrow [0,1]$, mapping its input to its expected value.

In this case, if $r_1,\ldots,r_n$ are uniformly random bits, then: $$E[\sum_{i=1}^nf[r_{2i-1},r_{2i}] = \frac{n}{4}E[f(0,0) + f(1,0) + f(0,1) + f(1,1)]$$

But if I just have the very simple (non-random) sequence $x_1,\ldots,x_n$ defined to take values $0, 0, 0, 1, 1, 0, 1, 1, \ldots$ forever repeating, then: $$E[\sum_{i=1}^nf[x_{2i-1},x_{2i}] = \frac{n}{4}E[f(0,0) + f(1,0) + f(0,1) + f(1,1)]$$

That is the long term average will be the same. Of course there is an obvious repeating pattern in the sequence of $x$s, but you can't detect it without state.

Answer 4

From my understanding in the first part of the question we bound the algorithm $ f(x,y) $ to a specific pseudorandom number generator $ r() $. In this case the answer depends on the PRNG used.

Consider that $ r() $ is a Linear Congruential Generator (LCG) with known parameters. Then $ f(x,y) $ could simply test if

$ y \equiv (a \cdot x + c) \mod{M} $

and output "pseudorandom" if the equality holds.

This algorithm would always be correct if the input comes from $ r() $ and will fail to produce a correct result in case the input comes from $ q() $, if the two random numbers form a correct sequence for the LCG. If we consider 32 bit numbers then, because we have exactly one correct $y$ for each $x$, there are $ 2 ^{32} $ inputs for which the algorithm will output an incorrect result out of $ 2 ^{64} $ total possible inputs. So the error probability of the algorithm is $ 1 / 2^{32} $.

A similar algorithm could be used in the case of Mersenne twister. However because of the larger state of the generator, two consecutive outputs will not give any information, so a larger vector is needed ($n=625$ is enough). Note that this technique will fail if the output of the generator hides its internal state (ex. with a cryptographically strong hash function).