I am wondering if someone can say if the following qualifies as a PRNG. Input a random bit seed of length $n$ into the generator, and over $k$ steps the generator uses $k$ publicly known integers to compute the pseudo random bit sequence, outputting a stream of $kn$ pseudo random bits.

I am wondering if the use of the $k$ (predefined) integers in computation still qualifies as a pseudo random number generator; if the integers need not be private, and need not be determined by the user do they count as part of the seed?

  • $\begingroup$ What is "publicly known randomness"? If it is known it is not really random, right? What do you mean with "injects ... into the random bit stream"? $\endgroup$ – Maarten Bodewes May 24 at 0:18
  • $\begingroup$ @MaartenBodewes I see how this makes no sense, what I mean to say is a set of $k$ numbers that were drawn from a random source, and this set can be publicly seen. $\endgroup$ – GEG May 24 at 0:22
  • $\begingroup$ I still don't get the "inject" part and why the stream would output $kn$ bits. $\endgroup$ – Maarten Bodewes May 24 at 0:27
  • $\begingroup$ @MaartenBodewes I edited the question, hopefully that helps $\endgroup$ – GEG May 24 at 0:31
  • 2
    $\begingroup$ This can yield a secure PRG, e.g. AES-CTR (input the seed as key, IV as 0) uses "publicly known numbers" to expand the seed (the IV increments). But obviously there are also constructions that use public numbers and are trivially insecure. $\endgroup$ – SEJPM May 24 at 10:54

The PRNG definition is quite simple. The following two distributions should be indistinguishable

$D_1() : Y \leftarrow \{0,1\}^m$; Return $Y;$

$D_2() : K\leftarrow \{0,1\}^\kappa$; Return $G(K)$;

Here, $G:\{0,1\}^\kappa \rightarrow \{0,1\}^m $is your PRNG function. It is required that the adversary knows everything about G, including the values you refer to. The only thing the adversary does not know is K.

A function is a PRNG if an (polynomial time) adversary who has oracle access to $D_i()$ can not tell if they are interacting with $D_1$ or $D_2$.

So yes, it's OK to have your numbers. They are simply part of the description of the PRNG.

| improve this answer | |

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.