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:

Post a Comment