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
    86426
  • \( \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\)

    (Pseudo-OTP)

    image

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

    image

    image

    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.

    image

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

    image

    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.

    image

    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}\) ).
    image

    image

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

    image

    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?