What do NM-CPA and NM-CCA mean? 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.
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.