Skip to main content
Engineering LibreTexts

7.2: Pseudorandom Ciphertexts

  • Page ID
    7377
  • \( \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}}\)

    When we introduced one-time security of encryption (in Section 2.2), we had two variants of the definition. The more general variant said, roughly, that encryptions of \(m_{L}\) should look like encryptions of \(m_{R}\). The more specific variant said that encryptions of every \(m\) should look uniform.

    We can do something similar for CPA security, by defining a security definition that says "encryptions of \(m\) look uniform." Note that it is not sufficient to use the same security libraries from the one-time security definition. It is important for the library to allow multiple encryptions under the same key. Just because a single encryption is pseudorandom, it doesn’t mean that multiple encryptions appear jointly pseudorandom. In particular, they may not look independent (this was an issue we saw when discussing the difficulty of constructing a PRF from a PRG).

    Definition \(7.2\) (CPA$ security)

    Let \(\Sigma\) be an encryption scheme. We say that \(\Sigma\) has pseudorandom ciphertexts in the presence of chosen-plaintext attacks (CPA$ security) if \(\mathcal{L}_{\text {cpa\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {cpa\$-rand }}^{\Sigma}\), where

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

    This definition is also called "IND$-CPA", meaning "indistinguishable from random under chosen plaintext attacks." This definition will be useful to use since:

    • It is easier to prove CPA$ security than to prove CPA security. Proofs for CPA security tend to be about twice as long and twice as repetitive, since they involve getting to a "half-way hybrid" and then performing the same sequence of hybrids steps in reverse. Taking the proof only to the same half-way point is generally enough to prove CPA$ security
    • CPA$ security implies CPA security. We show this below, but the main idea is the same as in the case of one-time security. If encryptions of all plaintexts look uniform, then encryptions of \(m_{L}\) look like encryptions of \(m_{R}\).
    • Most of the schemes we will consider achieve CPA$ anyway.

      Still, most of our high-level discussion of security properties will be based on CPA security. It is the "minimal" (i.e., least restrictive) definition that appears to capture our security intuitions.

    Claim 7.3

    If an encryption scheme has CPA$ security, then it also has CPA security.

    Proof

    We want to prove that \(\mathcal{L}_{\text {cpa-L }}^{\Sigma} \approx \mathcal{L}_{\text {cpa-R }}^{\Sigma}\), using the assumption that \(\mathcal{L}_{\text {cpa\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {cpa\$-rand }}^{\Sigma}\). The sequence of hybrids follows:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    The starting point is \(\mathcal{L}_{\text {cpa-L }}^{\Sigma}\), as expected.
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    It may look strange, but we have further factored out the call to Enc into a subroutine. It looks like everything from \(\mathcal{L}_{\text {cpa-L}}\) has been factored out, but actually the original library still "makes the choice" of which of \(m_L\), \(m_R\) to encrypt. 
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    We have replaced \(\mathcal{L}^{\Sigma}_{\text {cpa\$-real}}\) with \(\mathcal{L}^{\Sigma}_{\text {cpa\$-rand}}\). By our assumption, the change is indistinguishable. 
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    We have changed the argument being passed to CTXT. This has no effect on the library’s behavior since CTXT completely ignores its argument in these hybrids.
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    The mirror image of a previous step; we replace \(\mathcal{L}_{\text {cpa\$-rand }}\) with \(\mathcal{L}_{\text {cpa\$-real }}\).
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    The \(\mathcal{L}_{\text {cpa\$-real }}\) library has been inlined, and the result is \(\mathcal{L}_{\text {cpa-R }}^{\Sigma}\)

    The sequence of hybrids shows that \(\mathcal{L}_{\text {cpa-L }}^{\Sigma} \approx \mathcal{L}_{\text {cpa-R }}^{\Sigma}\), as desired.


    This page titled 7.2: Pseudorandom Ciphertexts is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.