5.3: Application: Shorter Keys in One-Time-Secret Encryption
- Page ID
- 86426
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:
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.
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).
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.