Skip to main content
Engineering LibreTexts

7.1: Limits of Deterministic Encryption

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

    We have already seen block ciphers / PRPs, which seem to satisfy everything needed for a secure encryption scheme. For a block cipher, \(F\) corresponds to encryption, \(F^{-1}\) corresponds to decryption, and all outputs of \(F\) look pseudorandom. What more could you ask for in a good encryption scheme?

    Example

    Example We will see that a block cipher, when used "as-is," is not a CPA-secure encryption scheme. Let F denote the block cipher and suppose its block length is blen.

    Consider the following adversary \(\mathcal{A}\), that tries to distinguish the \(\mathcal{L}_{\text {cpa- } \star}\) libraries:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\mathrm{cpa}-\mathrm{L}}\), the EAVESDROP algorithm will encrypt its first argument. So, \(c_{1}\) and \(c_{2}\) will both be computed as \(F\left(k, 0^{\text {blen }}\right)\). Since \(F\) is a deterministic function, this results in identical outputs from EAVESDROP. In other words \(c_{1}=c_{2}\), and \(\mathcal{A} \diamond\) \(\mathcal{L}_{\text {cpa-L }}\) always outputs \(1.\)
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\mathrm{cpa}-\mathrm{R}}\), the EAVESDROP algorithm will encrypt its second argument. So, \(c_{1}\) and \(c_{2}\) are computed as \(c_{1}=\) \(F\left(k, 0^{\text {blen }}\right)\) and \(c_{2}=F\left(k, 1^{\text {blen }}\right)\). Since \(F\) is a permutation, \(c_{1} \neq c_{2}\), so \(\mathcal{A} \diamond \mathcal{L}_{\mathrm{cpa}-\mathrm{R}}\) never outputs 1.

    This adversary has advantage 1 in distinguishing the libraries, so the bare block cipher \(F\) is not a CPA-secure encryption scheme.

    Impossibility of Deterministic Encryption

    The reason a bare block cipher does not provide CPA security is that it is deterministic. Calling \(\operatorname{Enc}(k, m)\) twice - with the same key and same plaintext - leads to the same ciphertext. Even one-time pad is deterministic. \({ }^{1}\) One of the first and most important aspects of CPA security is that it is incompatible with deterministic encryption. Deterministic encryption can never be CPA-secure! In other words, we can attack the CPA-security of any scheme \(\Sigma\), knowing only that it has deterministic encryption. The attack is a simple generalization of our attack against a bare PRP:

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

    A good way to think about what goes wrong with deterministic encryption is that it leaks whether two ciphertexts encode the same plaintext, and this is not allowed by CPA security. Think of sealed envelopes as an analogy for encryption. I shouldn’t be able to tell whether two sealed envelopes contain the same text! We are only now seeing this issue because this is the first time our security definition allows an adversary to see multiple ciphertexts encrypted under the same key.

    Avoiding Deterministic Encryption

    Is CPA security even possible? How exactly can we make a non-deterministic encryption scheme? This sounds challenging! We must design an Enc algorithm such that calling it twice with the same plaintext and key results in different ciphertexts (otherwise the attack \(\mathcal{A}\) above violates CPA security). What’s more, it must be possible to decrypt all of those different encryptions of the same plaintext to the correct value!

    There are 3 general ways to design an encryption scheme that is not deterministic:

    • Encryption/decryption can be stateful, meaning that every call to Enc or Dec will actually modify the value of \(k\). The symmetric ratchet construction described in Section \(5.5\) could be thought of as such a stateful construction. The key is updated via the ratchet mechanism for every encryption. A significant drawback with stateful encryption is that synchronization between sender and receiver is fragile and can be broken if a ciphertext is lost in transit.
    • Encryption can be randomized. Each time a plaintext is encrypted, the Enc algorithm chooses fresh, independent randomness specific to that encryption. The main challenge in designing a randomized encryption method is to incorporate randomness into each ciphertext in such a way that decryption is still possible. Although this sounds quite challenging, we have already seen such a method, and we will prove its CPA security in the next sections. In this book we will focus almost entirely on randomized encryption.
    • Encryption can be nonce-based. A "nonce" stands for "number used only once" and it refers to an extra argument that is passed to the Enc and Dec algorithms. A nonce does not need to be chosen randomly; it does not need to be secret; it only needs to be distinct among all calls made to Enc. By guaranteeing that some input to Enc will be different every time (even when the key and plaintext are repeated), the Enc algorithm can be deterministic and still provide CPA security.
      fig-ch01_patchfile_01.jpg
      Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

      Nonce-based encryption requires a change to the interface of encryption, and therefore a change to the correctness & security definitions as well. The encryption/decryption algorithms syntax is updated to \(\operatorname{Enc}(k, v, m)\) and \(\operatorname{Dec}(k, v, c)\), where \(v\) is a nonce. The correctness property is that \(\operatorname{Dec}(k, v, \operatorname{Enc}(k, v, m))=m\) for all \(k, v, m\), so both encryption & decryption algorithms should use the same nonce. The security definition allows the adversary to choose the nonce, but gives an error if the adversary tries to encrypt multiple ciphertexts with the same nonce. In this way, the definition enforces that the nonces are distinct.

      Note that the calling program provides a single value \(v\) (not a \(v_{L}\) and \(v_{R}\) ). Both libraries use the nonce \(v\) that is given, and this implies that the encryption scheme does not need to hide \(v\). If something is the same between both libraries, then it is not necessary to hide it in order to make the libraries indistinguishable.

    If an encryption scheme does not fall into one of these three categories, it cannot satisfy our definition of CPA-security. You can and should use deterministic encryption as a sanity check against any proposed encryption algorithm.


    \({ }^{1}\) Remember, we can always consider what will happen when running one-time pad encryption twice with the same key + plaintext. The one-time secrecy definition doesn’t give us any security guarantees about using one-time pad in this way, but we can still consider it as a thought experiment


    This page titled 7.1: Limits of Deterministic Encryption 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.