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


## 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)

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]$$

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.

The starting point is $$\mathcal{L}_{\text {ots-L }}^{\text {pOTP }}$$, shown here with the details of pOTP filled in.

The first hybrid step is to factor out the computations involving $$G$$, in terms of the $$\mathcal{L}_{\text {prg-real }}^{G}$$ library.

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.

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.

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}$$ ).

A statement has been factored out into a subroutine, which happens to exactly match $$\mathcal{L}_{\text {prg-rand }}^{G}$$

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.

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.

## Extending the Stretch of a PRG

The stretch of a PRG measures how much longer its output is than its input. Can we use a PRG with small stretch to construct a PRG with larger stretch? The answer is yes, but only if you do it the right way!

5.3: Application: Shorter Keys in One-Time-Secret Encryption is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.