I have two related questions concerning cryptographically secure pseudo random number generators.

My first question is as follows: are there conditions on the definition of cryptographically secure pseudo random number generators that require distinct seeds to generate distinct (periodic) sequences? What if a generator has the property that two distinct seeds generate the same sequence, but the generator is provably secure? Can this property be ignored then or is it a requirement that distinct seeds generate distinct pseudo random sequences?

My next question concerns the paper by Blum, Blum, and Shub introducing the $x^2 \mod N$ Generator. After reading the paper and learning about the generator, it is clear that the outputs of the generator pass statistical tests for randomness, but it is unclear to me how the authors proved 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 (backwards secure)?

  • 1
    $\begingroup$ Unless questions are tightly related, write separate posts for different questions. (Not that the other kind of posts - where people dump around eight related questions in one post because they misunderstand something fundamental or don't yet know which questions they should be asking - are without their own issues.) $\endgroup$ – Future Security Mar 30 at 15:42
  • $\begingroup$ Please split the question as suggested. I propose a different post for Blum Blum Shub given the title. $\endgroup$ – Maarten Bodewes Mar 31 at 13:07
  • $\begingroup$ Thanks I just added two new questions. $\endgroup$ – GEG Mar 31 at 14:35