You are looking at a specific version 20120815:101923 of this paper. See the latest version.

Paper 2011/092

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

Akinori Kawachi and Christopher Portmann and Keisuke Tanaka

Abstract

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.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. In proceedings of ICITS 2011
Keywords
Information-theoretic securitynon-malleabilityrelations among notions of security
Contact author(s)
chportma @ gmail com
History
2012-08-15: revised
2011-02-28: received
See all versions
Short URL
https://ia.cr/2011/092
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.