Paper 2011/092

Characterization of the relations between information-theoretic non-malleability, secrecy, and authenticity

Akinori Kawachi, Christopher Portmann, and Keisuke Tanaka


Roughly speaking, an encryption scheme is said to be non-malleable, if no adversary can modify a ciphertext so that the resulting message is meaningfully related to the original message. We compare this notion of security to secrecy and authenticity, and provide a complete characterization of their relative strengths. In particular, we show that information-theoretic perfect non-malleability is equivalent to perfect secrecy of two different messages. This implies that for $n$-bit messages a shared secret key of length roughly $2n$ is necessary to achieve non-malleability, which meets the previously known upper bound. We define approximate non-malleability by relaxing the security conditions and only requiring non-malleability to hold with high probability (over the choice of secret key), and show that any authentication scheme implies approximate non-malleability. Since authentication is possible with a shared secret key of length roughly $\log n$, the same applies to approximate non-malleability.

Note: This is the full version of our ICITS 2011 paper. Section 6, Appendix A, and Appendix B do not appear in the published version.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. In proceedings of ICITS 2011
Information-theoretic securitynon-malleabilityrelations among notions of security
Contact author(s)
chportma @ gmail com
2012-08-15: revised
2011-02-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akinori Kawachi and Christopher Portmann and Keisuke Tanaka},
      title = {Characterization of the relations between information-theoretic non-malleability, secrecy, and authenticity},
      howpublished = {Cryptology ePrint Archive, Paper 2011/092},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.