3
$\begingroup$

For example, let's say I want two cryptographically strong RNGs (R1 and R2). And I want them to have the following property: R1 (resp. R2) will never generate the same random number twice. R1 (resp. R2) will never generate a random number that R2 (resp. R1) can generate.

Is it possible for three RNGs, 4, N ?

Unlike other questions already on the site, I don't need the generated RNGs to be tracked back to their generator.

$\endgroup$
6
  • 1
    $\begingroup$ I don't think it is possible. But it is effectively achieved by generating large numbers (e.g. 128-bit or larger), having a large state space (i.e. >= 128-bit again) and using a TRNG to seed the state. Chances of you seeing repeat values in practice in such a setup may as well be zero. $\endgroup$ Oct 2 '15 at 10:11
  • 3
    $\begingroup$ There have been several near duplicates asked recently. A quick search found these two. Does either answer your question? $\endgroup$
    – otus
    Oct 2 '15 at 10:11
  • $\begingroup$ I can't see a difference with the second question pointed by otus. $\endgroup$
    – fgrieu
    Oct 2 '15 at 10:51
  • $\begingroup$ @otus no: I don't need the generated numbers to be tracked back to their generator. I just want the RNGs to not repeat themselves and to not collide with the others RNGs. $\endgroup$
    – daruma
    Oct 2 '15 at 11:50
  • $\begingroup$ @UnixJunkie, is it a problem if they are? I.e. what additional requirements do you have that require a different answer? $\endgroup$
    – otus
    Oct 2 '15 at 12:01
11
$\begingroup$

Take a block cipher with a random key and for one generator encrypt the even numbers then with the other generator encrypt the odd numbers. Your output blocks will be pseudo-random and distinct. For more than two generators just partition the inputs accordingly.

$\endgroup$
7
  • 1
    $\begingroup$ Correct, but useless. Sadly, the question is generally useless. $\endgroup$
    – Joshua
    Oct 2 '15 at 16:16
  • 1
    $\begingroup$ +1. Also, if you need the outputs to lie in a range that doesn't conveniently match the block size of any standard block cipher, you can use the usual FPE tricks to construct a cipher with a suitable range. $\endgroup$ Oct 3 '15 at 20:57
  • $\begingroup$ Is it possible to preserve non-overlappiness for small ranges? E.g. 2 seeded random number generators that, each, picks a different subset of numbers from 1 to 20? $\endgroup$
    – caveman
    Aug 19 at 9:51
  • $\begingroup$ That was what the FPE comment above sought to address. $\endgroup$ Aug 19 at 18:32
  • $\begingroup$ Does FPE require synchronisation of the generators? E.g. if we have 2 generators each generating a sequence 512 bit blocks off a unique key, then one method in that document is sorting those 512 values in order to reach a global agreement across the generators. This sorting needs synchronisation between the generators. Can we do it without such synchronisation? E.g. can we just initialise the generators differently at start, then somehow have the generators generate non-overlapping random numbers without the generators needing to talk to each other to reach a ordering agreement? $\endgroup$
    – caveman
    Aug 19 at 20:24

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.