Understanding definition of secure pseudo random number generator

Question

From my reading, a secure pseudo random number generator is called secure if, given a sequence of numbers generated by the PRNG, then if any one of those numbers from the sequence is removed an adversary could not determine the removed number via any method better than guessing. Of course the existence of such secure PRNG's is unknown.

Reading such a definition however, I am unclear on a couple of things. Assume $G$ is a pseudo random number generator so that an adversary could not determine the missing value in a sequence by any more efficient method other than guessing. But also assume the output of $G$ is normally distributed: Then the adversary may still have to guess to determine the missing value, but with high probability the missing value will be in a particular interval. Would such a PRNG still be called secure?

Answer 1

You'd do well to review your readings to see if they stipulate somewhere earlier that when they say "random" they mean uniform random (equiprobable).

But even without such a stipulation that I'd say the definition as you've loosely formulated it and are interpreting it seems to imply equiprobability. If we follow your logic strictly, then we have to conclude that your proposed attack on the normally-distributed output of $G$ would imply that $G$ is not in fact a secure PRNG by your definition and application thereof. And in fact you should be able to conclude that your definition and interpretation implies that the output of a secure PRNG must be uniform.

But the definitions used in theoretical cryptography are much more precise than this. For example in Katz & Lindell's textbook (2nd edition), Definition 3.14 (p. 62):

DEFINITION 3.14. Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithms such that for any $n$ and any input $ \in \{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a pseudorandom generator if the following conditions hold:

1. (Expansion:) For every $n$ it holds that $\ell(n) > n$.
2. (Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that $$\bigg|\mathrm{Pr}\big[D(G(s)) = 1\big] - \mathrm{Pr}\big[D(r) = 1\big]\bigg| ≤ \mathsf{negl}(n)$$ where thre first probability is taken over uniform choice of $s \in \{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$ and the randomness of $D$.

I'll repeat this bit that I boldfaced at the end:

the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$

If your reading materials are leaving you with questions like these, maybe have a look at something more rigorous.

Answer 2

If you have a non-uniform distribution the adversary will have an advantage when guessing. In your example of a normal distribution the adversary gets that advantage by picking values near the mode. Even if they aren’t told up front that the distribution is normal, after enough input they will be able to compute good estimates of the distribution and its parameters.

I think that the question is the result of the collision and overlap of three different areas of mathematics. The definition you quote is the “axiomatic unpredictability” one from Information Theory. In Statistics you can talk about random variables of different distributions. (Indeed, estimating distributions and parameters from a sample is a huge part of Statistics.) Underlyingly, Statistics uses definitions based on measure theory so that they work over real numbers. In Cryptography, we are back to unpredictability, but it is defined slightly differently. In Cryptography it is defined in terms of an adversary not being able to distinguish output of the RNG from what they would get from a truly uniform distribution.

In all three cases, it is fine to use the word “random” and people will know what you mean from the context, but when it comes to making inferences from the underlying definitions, it is important to be clear. The axiomatic unpredictability definition and the cryptographically secure definition will not hold for anything other than a uniform distribution.