Skip to main content
Engineering LibreTexts

5.2: Pseudorandom Generators in Practice

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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

    Screen Shot 2019-03-02 at 4.15.13 PM.png

    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.


    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.

    Screen Shot 2019-03-02 at 4.50.01 PM.png

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

    Screen Shot 2019-03-02 at 4.53.46 PM.png

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

    Screen Shot 2019-03-02 at 4.53.24 PM.png

    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.

    Screen Shot 2019-03-02 at 4.55.56 PM.png

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

    Screen Shot 2019-03-02 at 4.57.49 PM.png

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

    Screen Shot 2019-03-02 at 4.59.35 PM.png

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

    Screen Shot 2019-03-02 at 5.00.42 PM.png

    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.

    Screen Shot 2019-03-02 at 5.01.55 PM.png

    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.

    This page titled 5.2: Pseudorandom Generators in Practice is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .

    • Was this article helpful?