0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\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 '20 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 '20 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 '20 at 0:27
  • $\begingroup$ @MaartenBodewes I edited the question, hopefully that helps $\endgroup$ – GEG May 24 '20 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 '20 at 10:54
2
$\begingroup$

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
$\endgroup$
1
$\begingroup$

I am assuming you mean to use $n$ and $k$ in each round to compute this sequence. If so, if your each round function is a pseudo random function indexed by $n$, then the sequence generated is pseudo random. It can be trivially proven because if the sequence could be distinguished from a random sequence after some rounds, we could use that to tell whether we were given this function or a random oracle in a distinguishing game. This is what block ciphers in CTR or GCM modes are , the generated sequence is pseudo-random if single block encryption is a pseudo-random permutation. Although it would not be a secure pseudo random generator for it provides no forward security. Here state compromise at any point would mean compromising $n$ and hence would reveal all the sequence prior to the compromise.

Improve this answer
$\endgroup$
0
$\begingroup$

At some level all randomness has to end I think, but if I'd try to develop a good random generator, I'd use a lot of noisy mechanisms.

You could for example use a maximally distributed parallel algorithm and let as many different processes as possible compete against each other to calculate some long sequences of prime numbers withs some specific properties, and especially by using as many recursions as possible and maybe using some noisy streamdata and some webcam access for additional noise generators.

At some point however, all randomness has to end.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This does not answer the question at all. $\endgroup$ – Maeher Mar 4 at 17:25

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.