7
$\begingroup$

I have a cryptographically secured RNG that uses a recommended block cipher to generate the random number. As its output, I receive the random number which is very large, but the application requires the usage of two random numbers, and both of them with smaller bit-size of the RNG output.

Can I split the random number into two smaller vectors and consider them as two random numbers? Is this a recommended practice?

$\endgroup$
  • 1
    $\begingroup$ Yes you can and yes this is commonly done. $\endgroup$ – SEJPM Jan 16 '17 at 17:43
  • 1
    $\begingroup$ ... you should however make sure that the bits of the two numbers you take from the larger number do not overlap. $\endgroup$ – Maarten - reinstate Monica Jan 16 '17 at 18:03
9
$\begingroup$

Yes you can.

Suppose that you have a pseudorandom generator that, on some seed $s$, outputs $n$ pseudorandom bits, where $n$ is even. Then on a uniformly random input seed $s$, prg$(s) = r$ can be written $r_1 + 2^{n/2}r_2$, with $(r_1,r_2) \in (\{0,1\}^{n/2})^2$. I claim that both $r_1$ and $r_2$ are computationally indistinguishable from uniformly random elements from $\{0,1\}^{n/2}$.

The intuition behind this is as follows: suppose toward contradiction that some polynomial size algorithm can distinguish $r_1$ from random, when $r_1$ is computed as the $n/2$ least significant bits of prg$(s) = r$, for a uniformly random $s$. Now, you are given an $n$-bit string $r$ and must tell whether it is random or it is the output of the PRG. Just decompose $r = r_1 + 2^{n/2}r_2$, and run your distinguisher on input $r_1$: if it tells you that $r_1$ is non-random, then $r$ is non-random (as the distribution of uniformly random $n$-bit numbers is perfectly equal to the distribution obtained by picking two uniformly random $n/2$-bit numbers $r_1,r_2$ and computing $r$ as $r_1 + 2^{n/2}r_2$), hence you can distinguish outputs of the PRG on random seeds from random $n$-bit values, contradicting the fact that the PRG is cryptographically secure. The same argument shows that $r_2$ cannot be distinguished from random.

More generally, fix any size-$k$ subset $S$ of $\{1, \cdots, n\}$, for some $k \leq n$; a similar argument shows that the $k$-bit string obtained by running a secure prg on a random seed, and taking the $k$ bits of the output indexed by $S$, is computationally indistinguishable from random (and the distinguishing advantage of any polytime adversary is at most equal to its distinguishing advantage against the PRG). You can have a bunch of random-looking bit strings just by considering any partition of the bits of your PRG output.

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