Recently, I'm reading one paper of Boneh and Zhandry. They have mentioned a pseudo random number generator that takes input a $n$-bit string and gives a $2n$-bit string as output. They just used it as a generic construction. I want to learn specific construction of such kind of PRNG. Please refer me any link or please explain me the construction of such PRG.


It can be consctructed in many different ways.

I will just give an example using HMAC-$\mathcal{H}$ where $\mathcal{H}$ is a hash function which returns a $x$-bit hash.

So if you want to use a PRNG which takes $n$-bit inputs and returns $2n$-bit output, you could act this way:

  1. Divide the input into $\frac{x}{2}$-bit blocks $B_i$
  2. For each block $B_i$ computes $B'_i = \text{HMAC-}\mathcal{H}_K(B_i \space || \space i)$ where $K$ is the symmetric key used for the HMAC computation and $||$ denotes concatenation.

In that case, note that the property $n$-bit input returns a $2n$-bit output is confirmed only if $n \mod \frac{x}{2} = 0$, but you can still truncate the result after HMAC computations to get the expected output length.

  • $\begingroup$ If I use BBS generator that takes a n bits string and produces a sequence of 2n bits, then is it also true? @ Raoul722 $\endgroup$ Apr 11 '16 at 10:31
  • $\begingroup$ Yes I'm asking that can we use BBS instead of HMAC? @ Raoul722 $\endgroup$ Apr 11 '16 at 11:38
  • 1
    $\begingroup$ @MrigankaMandal Well, in the example given above, HMAC is used as a pseudo random function (PRF), so any other PRF could be used in this example. Here you are asking about a PRNG algorithm, so it would mean you use a PRNG to define an other one... It doesn't seem wise to me. $\endgroup$
    – Raoul722
    Apr 11 '16 at 11:50

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.