# PRNG that takes input a $n$-bit string and gives output a $2n$-bit string?

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.

## 1 Answer

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.

• If I use BBS generator that takes a n bits string and produces a sequence of 2n bits, then is it also true? @ Raoul722 – Mriganka Mandal Apr 11 '16 at 10:31
• Yes I'm asking that can we use BBS instead of HMAC? @ Raoul722 – Mriganka Mandal Apr 11 '16 at 11:38
• @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. – Raoul722 Apr 11 '16 at 11:50