Skip to main content
Library homepage
Loading table of contents menu...
Engineering LibreTexts

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

  • 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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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



    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.

    • Was this article helpful?