Follow by Email

Sunday, April 10, 2011

The shortest sequence of bits that deterministically reveal the full state of a pseudo-random number generator

A pseudo-random number generator (PRNG) is a deterministic object, with a finite internal state, usually initialized by some short seed. The seed may be truly random. However since the PRNG has a finite state, then it will eventually start repeating the entire sequence again. A computationally limited adversary may not be able to compute the entire sequence for a given seed. However it interests me to consider the case of an all-powerful probabilistic adversary (call that adversary Eve) that is able to compute the all the possible sequences for all the possible seeds (since seeds are finite as well).

Eve has a black-box access to a PRNG, and is able to initialize it with any seed and recover the whole sequence. It doesn't know a priori the length of the sequence but lets arguably assume the existence of a method to deterministically know the sequence length given only the black-box access to the PRNG.

Then consider this following game between Alice and Eve. Alice, a computationally limited Turing machine, also has a black-box access to the same PRNG as Eve, and also has a truly random short seed (S) as input. Alice initializes the PRNG with S and then generates a sequence of bits from the PRNG, of length $\ell$. Alice then chooses any sub-sequence of length $\ell^{\prime}$ and sends it to Eve. Eve should then, using her knowledge of the PRNG, and some random coin tosses, output $S^{\prime}$, her guess of the random input of Alice. There is some probability of getting it right, over the random input of Alice, the coin tosses of Eve, given a certain PRNG and a certain $\ell^{\prime}$. Call that probability $P(S^{\prime} = S)$.

The question is then, given a certain PRNG, what is the least $\ell^{\prime}$ such that $P(S^{\prime} = S)=1$.

I don't know if this has been researched before but I am just recording the question here for me to investigate later. If you have any references if this problem has been tackled before, please share it in the comments :) Thanks.

No comments: