\input zb-basic
\input zb-ioport
\iteman{io-port 05897958}
\itemau{Kawachi, Akinori; Portmann, Christopher; Tanaka, Keisuke}
\itemti{Characterization of the relations between information-theoretic non-malleability, secrecy, and authenticity.}
\itemso{Fehr, Serge (ed.), Information theoretic security. 5th international conference, ICITS 2011, Amsterdam, The Netherlands, May 21--24, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20727-3/pbk). Lecture Notes in Computer Science 6673, 6-24 (2011).}
\itemab
Summary: 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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-20728-0\_2}
\end