5.3: Application: Shorter Keys in One-Time-Secret Encryption

We revisit the motivating example from the beginning of this chapter. Alice \(\&\) Bob share only a \(\lambda\)-bit key but want to encrypt a message of length \(\lambda+\ell\). The main idea is to expand the key \(k\) into 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 \(5.2\) (Pseudo-OTP)

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

The resulting scheme will not have (perfect) one-time secrecy. That is, encryptions of \(m_{L}\) and \(m_{R}\) 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 5.3

Let \(\Sigma\) be an encryption scheme, and let \(\mathcal{L}_{\mathrm{ots}-\mathrm{L}}^{\Sigma}\) and \(\mathcal{L}_{\mathrm{ots}-\mathrm{R}}^{\Sigma}\) be defined as in Definition \(2.6\) (and repeated below for convenience). Then \(\Sigma\) has (computational) one-time secrecy if \(\mathcal{L}_{\mathrm{ots}-\mathrm{L}}^{\Sigma} \approx\) \(\mathcal{L}_{\mathrm{ots}-\mathrm{R}}^{\Sigma} .\) That is, if for all polynomial-time distinguishers \(\mathcal{A}\), we have \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\mathrm{ots}-\mathrm{L}}^{\Sigma} \Rightarrow 1\right] \approx\) \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {ots-R }}^{\Sigma} \Rightarrow 1\right]\)

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

This is essentially the same as Definition \(2.6\), except we are using \(\approx\) (indistinguishability) instead of \(\equiv\) (interchangeability).

Claim 5.4 

Let pOTP denote Construction 5.2. If pOTP is instantiated using a secure PRG G then pOTP has computational one-time secrecy.

Proof

We must show that \(\mathcal{L}_{\text {ots-L }}^{\text {pOTP }} \approx \mathcal{L}_{\text {ots-R }}^{\text {pOTP }} \cdot\) As usual, we will proceed using a sequence of hybrids that begins at \(\mathcal{L}_{\text {ots-L }}^{\text {pOTP }}\) and ends at \(\mathcal{L}_{\text {ots-R }}^{\text {pOTP }}\). For each hybrid library, we will demonstrate that it is indistinguishable from the previous one. Note that 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 \(\mathcal{L}_{\text {prg-real }}^{G}\) (one of the libraries in the PRG security definition), we can replace it with its counterpart \(\mathcal{L}_{\text {prg-rand }}^{G}\) (or vice-versa). The PRG security of \(G\) says that such a change will be indistinguishable.

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	The starting point is \(\mathcal{L}_{\text {ots-L }}^{\text {pOTP }}\), shown here with the details of pOTP filled in.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	The first hybrid step is to factor out the computations involving \(G\), in terms of the \(\mathcal{L}_{\text {prg-real }}^{G}\) library.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	From the PRG security of \(G\), we may replace the instance of \(\mathcal{L}_{\text {prg-real }}^{G}\) with \(\mathcal{L}_{\text {prg-rand }}^{G}\). The resulting hybrid library \(\mathcal{L}_{\text {hyb-2 }}\) is indistinguishable from the previous one.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	A subroutine has been inlined. Note that the resulting library is precisely \(\mathcal{L}_{\text {ots-L }}^{\text {OTP }}\) involving standard one-time pad on plaintexts of size \(\lambda+\ell\). We have essentially proven that pOTP is indistinguishable from standard OTP, and therefore we can apply the security of OTP.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	The (perfect) one-time secrecy of rOTP allows us to replace \(\mathcal{L}_{\text {ots-L }}^{\text {OTP }}\) with \(\mathcal{L}_{\text {ots-R }}^{\text {OTP }}\); 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 \(m_{R}\) being used instead of \(m_{L}\) ).

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	A statement has been factored out into a subroutine, which happens to exactly match \(\mathcal{L}_{\text {prg-rand }}^{G}\)
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	From the PRG security of \(G\), we can replace \(\mathcal{L}_{\text {prg-rand }}^{G}\) with \(\mathcal{L}_{\text {prg-real }}^{G}\). The resulting library is indistinguishable from the previous one.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	A subroutine has been inlined. The result is \(\mathcal{L}_{\text {ots-R }}^{\text {pOTP }}\)

Summarizing, we showed a sequence of hybrid libraries satisfying the following: \[\mathcal{L}_{\text {ots-L }}^{\text {pOTP }} \equiv \mathcal{L}_{\text {hyb-1 }} \approx \mathcal{L}_{\text {hyb-2 }} \equiv \mathcal{L}_{\text {hyb-3 }} \equiv \mathcal{L}_{\text {hyb-4 }} \equiv \mathcal{L}_{\text {hyb-5 }} \approx \mathcal{L}_{\text {hyb-6 }} \equiv \mathcal{L}_{\text {ots-R }}^{\text {pOTP }} .\] Hence, \(\mathcal{L}_{\text {ots-L }}^{\text {pOTP }} \approx \mathcal{L}_{\text {ots-R }}^{\text {pOTP }}\), and pOTP has (computational) one-time secrecy.