# 5.2: Pseudorandom Generators in Practice

- Page ID
- 7342

PRGs essentially convert a smaller amount of uniform randomness into a larger amount of *good-enough-for-polynomial-time* randomness. So a natural first application of PRGs is to obtain one-time-secure encryption but with keys that are shorter than the plaintext. This is the first of many acts of crypto-magic which are impossible except when restricting our focus to polynomial-time adversaries.

The main idea is to hold a short key k, expand it to a longer string using a PRG G, and use the result as a one-time pad on the (longer) plaintext. More precisely, let \(G\) : \(\{0,1\}^{\lambda} \rightarrow \{0,1\}^{\lambda + \ell}\) be a PRG, and define the following encryption scheme:

**Construction \(\PageIndex{1}\) : Pseudo-OTP**

The resulting scheme will not have (perfect) one-time secrecy. That is, encryptions of \(m_L\) and mR will not be identically distributed in general. However, the distributions will be indistinguishable if \(G\) is a secure PRG. The precise flavor of security obtained by this construction is the following.

Definition \(\PageIndex{1}\)

*Let* \(\Sigma\) *be an encryption scheme, and let* \(\mathscr{L}^{\Sigma}_{\text{ots-L}}\) *and* \(\mathscr{\Sigma}_{\text{ots-R}}\) *be defined as in Definition 2.2.1 (and repeated below for convenience). Then* \(\Sigma) *has (computational) one-time secrecy if* \(\mathscr{L}^{\Sigma}_{\text{ots-L}} ≋ \mathscr{L}^{\Sigma}_{\text{ots-R}}\).

*That is, if for all polynomial-time distinguishers*\(?\)

*, we have*\(Pr[? \diamondsuit \mathscr{L}^{\Sigma}_{\text{ots-L}} = 1] \approx Pr[? \diamondsuit \mathscr{L}^{\Sigma}_{\text{ots-R}} = 1]\).

\[\mathscr{L}^{\Sigma}_{ots-L}\space\space\space\space\space\space\space\space\space\space \mathscr{L}^{\Sigma}_{ots-R}\\\underline{QUERY(m_L,m_R\space\in\Sigma.M):}\space\space\space\space\space\space\space\space\space\space\underline{QUERY(m_L, m_R\space\in\Sigma. M):}\\k\space\leftarrow\space \Sigma .\text{KeyGen} \space\space\space\space\space\space\space\space\space\space k\space\Sigma . \text{KeyGen}\\c\space\leftarrow\space\text{Enc(}j,m_L)\space\space\space\space\space\space\space\space\space c\space\leftarrow\space\Sigma .\text{Enc(}k,m_R)\\\text{return}\space c\space\space\space\space\space\space\space\space\space\space\text{return}\space c\nonumber\]

**Claim \(\PageIndex{1}\)**

*Let* \(pOTP[G]\) *denote Construction 5.2.1 instantiated with *\(PRG G\)*. If *\(G\)* is a secure PRG then* \(pOTP[*G*]\) *has computational one-time secrecy*.

**Proof:**

We must show that \(\mathscr{L}^{\text{pOTP[G]}}_{\text{ots-L}} ≋ \mathscr{L}^{\text{pOTP[G]}}_{\text{ots-R}}\). As usual, we will proceed using a sequence of hybrids that begins at \(\mathscr{L}^{\text{pOTP[G]}}_{\text{ots-L}}\) and ends at \(\mathscr{L}^{\text{pOTP[G]}}_{\text{ots-R}}\). For each hybrid library, we will demonstrate that it is indistinguishable from the previous one. Note that we we are allowed to use the fact that \(G\) is a secure PRG. In practical terms, this means that if we can express some hybrid library in terms of \(\mathscr{L}^G_{\text{prg-real}}\) (one of the libraries in the PRG security definition), we can replace it with its counterpart \(\mathscr{L}^G_{\text{prg-rand}}\) (or vice-versa). The PRG security of \(G\) says that such a change will be indistinguishable.

The starting point is \(\mathscr{L}^{\text{pOTP[G]}}_{\text{ots-L}}\), shown here with the details of \(\text{pOTP[G]}\) filled in

The first hybrid step is to factor out the computations involving \(G\), in terms of the \(\mathscr{L}^G_{\text{prg-real}}\) library.

From the PRG security of \(G\), we may replace the instance of \(\mathscr{L}^G_{\text{prg-real}}\) with \(\mathscr{L}^G_{\text{prg-rand}}\). The resulting hybrid library \(\mathscr{L}_{hyb-2}\) is indistinguishable from the previous one.

A subroutine has been inlined. Note that the resulting library is precisely \(\mathscr{L}^{\text{OTP}}_{\text{ots-L}}\)! Here, OTP is instantiated on plaintexts of size \(\lambda +\ell\) (and the variable \(k\) has been renamed to \(z\)).

The (perfect) one-time secrecy of OTP allows us to replace \(\mathscr{L}^{\text{OTP}}_{\text{ots-L}}\)with \(\mathscr{L}^{\text{OTP}}_{\text{ots-R}}\); they are interchangeable.

The rest of the proof is essentially a “mirror image” of the previous steps, in which we perform the same steps but in reverse (and with mRhanging around instead of \(m_L\)).

A statement has been factored out into a subroutine, which happens to exactly match \(\mathscr{L}^G_{\text{prg-rand}}\).

From the PRG security of G, we can replace \(\mathscr{L}^G_{\text{prg-rand}}\) with \(\mathscr{L}^G_{\text{prg-real}}\)l. The resulting library is indistinguishable from the previous one.

A subroutine has been inlined. The result is \(\mathscr{L}^{\text{pOTP[G]}}_{\text{ots-R}}\).

Summarizing, we showed a sequence of hybrid libraries satisfying the following:

\(\mathscr{L}^{\text{pOTP[G]}}_{\text{ots-L}} \equiv \mathscr{L}_{\text{hyb-1}} ≋ \mathscr{L}_{\text{hyb-2}} \equiv \mathscr{L}_{\text{hyb-3}} \equiv \mathscr{L}_{\text{hyb-4}} \equiv ℒ\mathscr{L}_{\text{hyb-5}} ≋ \mathscr{L}_{\text{hyb-6}} \equiv \mathscr{L}^{\text{pOTP[G]}}_{\text{ots-R}}\).

Hence, \(\mathscr{L}^{\text{pOTP[G]}}_{\text{ots-L}} ≋ \mathscr{L}^{\text{pOTP[G]}}_{\text{ots-R}}\) , and pOTP has (computational) one-time secrecy.