Skip to main content
Engineering LibreTexts

7.3: CPA-Secure Encryption Based On PRFs

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

    CPA security presents a significant challenge; its goals seem difficult to reconcile. On the one hand, we need an encryption method that is randomized, so that each plaintext \(m\) is mapped to a large number of potential ciphertexts. On the other hand, the decryption method must be able to recognize all of these various ciphertexts as being encryptions of \(m\).

    However, we have already seen a way to do this! In Chapter 6 we motivated the concept of a PRF with the following encryption technique. If Alice and Bob share a huge table \(T\) initialized with uniform data, then Alice can encrypt a plaintext \(m\) to Bob by saying something like "this is encrypted with one-time pad, using key #674696273" and sending \(T[674696273] \oplus m\). Seeing the number 674696273 doesn’t help the eavesdropper know what \(T[674696273]\) is. A PRF allows Alice & Bob to do the same encryption while sharing only a short key \(k\). Instead of a the huge table \(T\), they can instead use a PRF \(F(k, \cdot)\) to derive a common pseudorandom value. Knowing a value \(r\) doesn’t help the adversary predict \(F(k, r)\), when \(k\) is secret.

    So, translated into more precise PRF notation, an encryption of \(m\) will look like \((r, F(k, r) \oplus m)\). Since Bob also has \(k\), he can decrypt any ciphertext of this form by computing \(F(k, r)\) and XOR’ing the second ciphertext component to recover \(m\).

    It remains to decide how exactly Alice will choose \(r\) values. We argued, informally, that as long as these \(r\) values don’t repeat, security is preserved. This is indeed true, and the distinctness of the \(r\) values is critical. Recall that there are 3 ways to avoid deterministic encryption, and all 3 of them would work here:

    • In a stateful encryption, \(r\) could be used as a counter. Use \(r=i\) to encrypt/decrypt the \(i\) th ciphertext.
    • In a randomized encryption, choose \(r\) uniformly at random for each encryption. If the \(r\) values are long enough strings, then repeating an \(r\) value should be negligibly likely.
    • In a nonce-based encryption, we can simply let \(r\) be the nonce. In the nonce-based setting, it is guaranteed that these values won’t repeat.

    In this section we will show the security proof for the case of randomized encryption, since it is the most traditional setting and also somewhat more robust than the others. The exercises explore how the nonce-based approach is more fragile when this scheme is extended in natural ways.

    Construction 7.4

    Let \(F\) be a secure PRF with in \(=\lambda\). Define the following encryption scheme based on \(F\) :

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

    It is easy to check that the scheme satisfies the correctness property.

    Claim 7.5

    Construction 7.4 has CPA$ security (and therefore CPA security) if \(F\) is a secure PRF.

    The proof has more steps than other proofs we have seen before, and some steps are subtle. So let us use a Socratic dialogue to illustrate the strategy behind the proof:

    SALVIATI: The ciphertexts of Construction \(7.4\) are indistinguishable from uniform randomness.
    SIMPLICIO: Salviati, you speak with such confidence! Do tell me why you say that these ciphertexts appear pseudorandom.
    SALVIATI: Simple! The ciphertexts have the form \((r, F(k, r) \oplus m)\). By its very definition, \(r\) is chosen uniformly, while \(F(k, r) \oplus m\) is like a one-time pad ciphertext which is also uniformly distributed.
    SIMPLICIO: Your statement about \(r\) is self-evident but \(F(k, r) \oplus m\) confuses me. This does not look like the one-time pad that we have discussed. For one thing, the same \(k\) is used "every time" not "one-time."
    SALVIATI: I did say it was merely "like" one-time pad. The one-time pad "key" is not \(k\) but \(F(k, r)\). And since \(F\) is a pseudorandom function, all its outputs will appear independently uniform (not to mention uncorrelated with their respective r), even when the same seed is used every time. Is this not what we require from a one-time padkey?
    SIMPLICIO: I see, but surely the outputs of \(F\) appear independent only when its inputs are distinct? I know that \(F\) is deterministic, and this may lead to the same "onetime pad key" being used on different occasions.
    SALVIATI: Your skepticism serves you well in this endeavor, Simplicio. Indeed, the heart of your concern is that Alice may choose r such that it repeats. I say that this is negligibly likely, so that we can safely ignore such a bothersome event.
    SIMPLICIO: Bothersome indeed, but why do you say that \(r\) is unlikely to repeat? 
    SALVIATI: Oh Simplicio, now you are becoming bothersome! This value \(r\) is \(\lambda\) bits long and chosen uniformly at random each time. Do you not recall our agonizingly long discussion about the birthday paradox?
    SImPLICIO: Oh yes, now I remember it well. Now I believe I understand all of your reasoning: Across all ciphertexts that are generated, \(r\) is unlikely to repeat because of the birthday paradox. Now, provided that \(r\) never repeats, Alice invokes the PRF on distinct inputs. A PRF invoked on distinct inputs provides outputs that are uniformly random for all intents and purposes. Hence, using these outputs as one-time pads completely hides the plaintext. Is that right, Salviati?
    SALVIATI: Excellent! Now we may return to discussing the motion of the Sun and Earth ...

    Look for Simplicio’s final summary to be reflected in the sequence of hybrids used in the formal proof:

    Proof

    We prove that \(\mathcal{L}_{\text {cpa\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {cpa\$-rand }}^{\Sigma}\) using the hybrid technique:

      The starting point is \(\mathcal{L}_{\text {cpa\$-real }}^{\Sigma}\) The details of \(\sum\) have been filled in and highlighted.
      The statements pertaining to the PRF have been factored out in terms of the \(\mathcal{L}_{\text {prf-real }}^{F}\) library.
      We have replaced \(\mathcal{L}_{\text {prf-real }}^{F}\) with \(\mathcal{L}_{\text {prf-rand }}^{F}\) From the PRF security of \(F\), these two hybrids are indistinguishable.

    At this point in the proof, it is easy to imagine that we are done. Ciphertexts have the form \((r, x)\), where \(r\) is chosen uniformly and \(x\) is the result of encrypting the plaintext with what appears to be a one-time pad. Looking more carefully, however, the "one-time pad key" is \(T[r]\) - a value that could potentially be used more than once if \(r\) is ever repeated!

    As Simplicio rightly pointed out, a PRF gives independently random(-looking) outputs when called on distinct inputs. But in our current hybrid there is no guarantee that PRF inputs are distinct! Our proof must explicitly contain reasoning about why PRF inputs are unlikely to be repeated. We do so by appealing to the sampling-with-replacement lemma of Lemma \(4.11.\)

    We first factor out the sampling of \(r\) values into a subroutine. The subroutine corresponds to the \(\mathcal{L}_{\text {samp-L }}\) library of Lemma 4.11:

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

    Next, \(\mathcal{L}_{\text {samp-L }}\) is replaced by \(\mathcal{L}_{\text {samp-R. By Lemma }} 4.11\), the difference is indistinguishable:

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

    Inspecting the previous hybrid, we can reason that the arguments to LOOKUP are guaranteed to never repeat. Therefore the \(\mathcal{L}_{\text {prf-rand }}\) library can be greatly simplified. In particular, the if-condition in \(\mathcal{L}_{\text {prf-rand }}\) is always true. Simplifying has no effect on the library’s output behavior:

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

    Now we are indeed using unique one-time pads to mask the plaintext. We are in much better shape than before. Recall that our goal is to arrive at a hybrid in which the outputs of CTXT are chosen uniformly. These outputs include the value \(r\), but now \(r\) is no longer being chosen uniformly! We must revert \(r\) back to being sampled uniformly, and then we are nearly to the finish line.

      As promised, \(\mathcal{L}_{\text {samp-R }}\) has been replaced by \(\mathcal{L}_{\text {samp-L. }}\) The difference is indistinguishable due to Lemma \(4.11.\)
      All of the subroutine calls have been inlined; no effect on the library’s output behavior.
      We have applied the one-time pad rule with respect to variables \(z\) and \(x\), but omitted the very familiar steps (factor out, replace library, inline) that we have seen several times before. The resulting library is precisely \(\mathcal{L}_{\text {cpa\$-rand }}^{\Sigma}\) since it samples uniformly from \(\Sigma . C=\{0,1\}^{\lambda} \times\) \(\{0,1\}^{\text {out}}\).

    The sequence of hybrids shows that \(\mathcal{L}_{\text {cpa\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {cpa\$-rand }}^{\Sigma}\), so \(\Sigma\) has pseudorandom ciphertexts.


    This page titled 7.3: CPA-Secure Encryption Based On PRFs 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.

    • Was this article helpful?