Characterization of the Relations Between Information-Theoretic Non-Malleability, Secrecy, and Authenticity
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. The authors compare this notion of security to secrecy and authenticity, and provide a complete characterization of their relative strengths. In particular, they 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.