1
$\begingroup$

Reading through Katz & Lindell's Intro to Modern Crypto, I came across these notions which were introduced in quick succession without much differentiation between them.

How do Indistinguishability(IND) and Non-Malleability(NM) differ? Which is the stronger notion of the two, in which (if any) scenario are they equivalent?

$\endgroup$
2
$\begingroup$

For this answer I'll use the paper linked in the comments: "Relations Among Notions of Security for Public-Key Encryption Schemes" by Bellare, Desai, Pointcheval and Rogaway (PDF) which also contains this very nice overview graph on page 4 of the PDF:

Result-Graph

How do Indistinguishability(IND) and Non-Malleability(NM) differ?

Generally in the IND setup you try to infer some information (at least 1 bit) about a given plaintext using your given capabilities (encryption and decryption oracles at the various stages).

In the NM setting on the other hand you are given a ciphertext $y$ of a plaintext $x$ and now want to come up with some "meaningful" relation $R$ such that given $y$ you can find a vector $\bf y$ which when component-wise decrypted yields a vector of plaintexts $\bf x$ such that $R(x, {\bf x})$ holds.

In case you are asking yourself how the distinction between CCA1 and CCA2 is implemented for NM, in CCA1 you only get access to a decryption oracle before seeing $y$.

Which is the stronger notion of the two [...]?

As can be seen in the above graph, for a given attacker capability X, NM-X generally implies IND-X but the converse doesn't always hold.

[In] which (if any) scenario are they equivalent?

As can be seen in the above graph, NM-X and IND-Y are equivalent only if X=Y is the CCA2 attacker model.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.