Relations Among Notions of Non-Malleability for Encryption

Since its introduction in the early 90's, the notion of non-malleability for encryption schemes has been formalized using a number of conceptually different definitional approaches---most notably, the ``semantical'' simulation-based approach, and the ``pragmatic'' indistinguishability-based approach.  We provide a full characterization of these approaches and consider their robustness under composition.