What do NM-CPA and NM-CCA mean?

Question

When I've been researching authenticated encryption, the following terms keep showing up:

• NM-CPA
• NM-CCA

....without any definition as to what they mean. I've tried searching the web for their definitions, but I'm not getting very far. Could someone explain what these abbreviations mean, and why papers such as this one don't give a definition of their meaning?

Edit: While the possible duplicate question explains IND-CPA and IND-CCA (which I think I'm still going to have trouble remembering), it doesn't explain the NM- ones.

Answer 1

There's a classic paper by Bellare, Desai, Pointcheval and Rogaway about the standard security notions: "Relations Among Notions of Security for Public Key Encryption Schemes" (PDF). This paper relates all the standard security notions you've heard of and gives definitions for all of them. I'll use it as the reference for this answer.

So first we need to understand the idea of the NM-* notions. It is for an adversary given an arbitrary ciphertext to produce a list of ciphertexts which, when decrypted, are in some way related to the originally encrypted plaintext.

Some notation we will need: $\bf x$ and $\bf y$ are $t-1$ element lists (also called "vectors") and $R$ is a relation over $t$ elements. For our understanding it suffices to think of it as a boolean predicate that takes $t$ arguments, eg $R(x_0,{\bf x})$ and deterministically returns true or false.

Now the game (formally called "experiment") has a one-bit parameter $b$ which will become important later on. But here are the steps:

1. Choose a keypair $(pk,sk)$ by running the non-deterministic key generation algorithm
2. Run the adversary $\mathcal A$ with access to an encryption oracle (for CPA), the public key if available and with access to a decryption oracle (for CCA). They are now allowed to make a polynomial number of calls to all available oracles and pick two messages $x_0$ and $x_1$ of the same length as well as save some state $s$.
3. Now encryption $x_1$ to $y$ using the encryption oracle.
4. Now run the adversary again, this time giving it $y$ and the saved state $s$ with the same oracle access as before. The adversary will return $R$ as well as a list of ciphertexts $\bf y$. Note that the adversary may not ask for decryption of $y$.
5. Now decrypt $\bf y$ element-wise to get $\bf x$.
6. The adversary wins iff $y$ isn't contained in the list $\bf y$, and all decryptions in 5 went without error, and $R(x_b,{\bf x})$ evaluates to true.

The "advantage" is then calculated as the difference between the probability of the adversary winning in the $b=1$ case and in the $b=0$ case. The idea being that the advantage takes into account the base-probability of an ordinary value satisfying the chosen relation "by accident" to handle choice of $R$ that eg always output true.

Note though that in the above description I've cut some details (like the formal distinction in adversary stages, the mentioning of CCA1 vs CCA2, and the formal concept of the sampling algorithm instead of instant-picking). If you're interested in those, go read the 2.3 of the linked paper, the above should allow you to easily fill in the gaps.

Answer 2

A cipher $E_k(m)$ is malleable if there is a nontrivial binary relation $\sim$ on messages such that given $c = E_k(m)$, it is easy to find $c' = E_k(m')$ with $m \sim m'$. For example, AES-CTR is malleable because for any $m$ and $m'$ with $m' = m \oplus \delta$, it is easy to compute $$c' = c \oplus \delta = E_k(m) \oplus \delta = E_k(m \oplus \delta) = E_k(m'),$$ in which case $m \sim m' = m \oplus \delta$. A hash-then-encrypt variant where we encrypt $m \mathbin\| H(m)$ instead is still malleable because it is easy to compute $\delta = (m \oplus m') \mathbin\| [H(m) \oplus H(m')]$ for any desired message $m'$. Similarly, textbook RSA, where the ciphertext for a message $m$ is $m^e \bmod n$, is malleable because for any $m$ and $m'$ with $m' = m \cdot \eta \bmod n$, it is easy to compute $$c' \equiv c \cdot \eta^e \equiv m^e \cdot \eta^e \equiv (m \cdot \eta)^e \equiv (m')^e \pmod n,$$ in which case $m \sim m' = m \cdot \eta \bmod n$.

As defined by Dolev–Dwork–Naor (paywall-free) and used throughout the literature, a cipher is nonmalleable (NM-) under an attack model (-CPA, -CCA, -CCA2, etc.) if, after interacting with the oracles in the attack model, and upon being presented a challenge ciphertext $c$ for a message of a form chosen by the adversary, the adversary cannot find—even using further interaction with the oracles—a nontrivial relation $\sim$ and a ciphertext $c'$ whose plaintext is related by $\sim$ to the plaintext of $c$. (Here we rule out trivial relations like $m \sim m$.)

In practical terms, nonmalleability means an adversary can't selectively modify ciphertexts; the worst they can do is denial of service or wholesale replacement.

The Bellare–Namprempre 2000 paper you cited on generic composition of symmetric ciphers and MACs doesn't formally define nonmalleability because nonmalleability is largely not important for the symmetric setting: when the sender and recipient share a key, they generally care about eavesdropping and forgery, but not about selective modification—detecting forgery means detecting selective modifications, and rejecting forgeries prevents abusing selective modifications to leak secrets.

Nonmalleability matters more in the setting of public-key anonymous encryption, like an activist leaking a document to a journalist. While it may not directly reveal to the adversary what a message was, selective modification can often be exploited in a larger system like an PGP mail client with EFAIL to leak the message when there is no notion of authentication to prevent forgery per se since anyone can anonymously submit documents. So nonmalleability is defined in the Bellare–Desai–Pointcheval–Rogaway 1998 paper on generic relations between notions of security for public-key encryption.