2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ That is not a standard definition of PRGs. $\endgroup$ – Maeher Mar 12 at 10:39
  • 1
    $\begingroup$ In particular the distribution for "random" is "uniformly at random" IE the uniform distribution. Wikipedia is decent for this right now: en.wikipedia.org/wiki/… $\endgroup$ – SAI Peregrinus Mar 12 at 14:55
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.