0
$\begingroup$

I have a question concerning the paper by Blum, Blum, and Shub introducing the $x^2 \mod N$ Generator. It is clear that the outputs of the generator pass statistical tests for randomness: the larger the $N$ value the more uniform the output looks with more iteration. But it is unclear to me how the authors proved the output of the generator is uniformly random. That is, it is not obvious to me that proving difficulty of, say, determining previous states given a present state implies the output of the generator is uniformly random.

Would anyone be able to walk me through a sketch of the proof showing the output of the generator is uniformly random, and thus that the generator is provably secure?

$\endgroup$
  • 1
    $\begingroup$ The output isn't uniformly random. It is merely computationally indistinguishable from a uniform random distribution. (Under specific hardness assumptions and only in an asymptotic sense.) $\endgroup$ – Maeher Mar 31 at 21:26
  • $\begingroup$ @Maeher I see, then how would you prove it is computationally indistinguishable from a uniform random distribution? $\endgroup$ – GEG Mar 31 at 22:00
0
$\begingroup$

If the primes $p$ and $q$ are:

  1. appropriately chosen (see abstract of original paper here) and
  2. large enough (use NFS factoring complexity to determine how large they should be)

then to distinguish non uniformity one basically has to factor $N=pq.$ However, as stated by @Maeher in the comments this holds only asymptotically.

| 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.