# 5.2: Application: Shorter Keys in One-Time-Series Encryption

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.