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 logn, the same applies to approximate non-malleability.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998)
Bellare, M., Sahai, A.: Non-malleable encryption: Equivalence between two notions, and an indistinguishability-based characterization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 519–536. Springer, Heidelberg (1999), full version available at http://eprint.iacr.org/2006/228
Bierbrauer, J., Johansson, T., Kabatianskii, G.A., Smeets, B.J.M.: On families of hash functions via geometric codes and concatenation. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 331–342. Springer, Heidelberg (1994)
Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. SIAM Journal on Computing 30(2), 391–437 (2000); a preliminary version appeared at STOC 1991
Hanaoka, G.: Some information theoretic arguments for encryption: Non-malleability and chosen-ciphertext security (invited talk). In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 223–231. Springer, Heidelberg (2008)
Hanaoka, G., Hanaoka, Y., Hagiwara, M., Watanabe, H., Imai, H.: Unconditionally secure chaffing-and-winnowing: A relationship between encryption and authentication. In: Fossorier, M.P.C., Imai, H., Lin, S., Poli, A. (eds.) AAECC 2006. LNCS, vol. 3857, pp. 154–162. Springer, Heidelberg (2006)
Hanaoka, G., Shikata, J., Hanaoka, Y., Imai, H.: Unconditionally secure anonymous encryption and group authentication. The Computer Journal 49(3), 310–321 (2006); a preliminary version appeared at Asiacrypt 2002
Katz, J., Yung, M.: Characterization of security notions for probabilistic private-key encryption. Journal of Cryptology 19(1), 67–95 (2006)
Kawachi, A., Portmann, C., Tanaka, K.: Characterization of the relations between information-theoretic non-malleability, secrecy, and authenticity. Cryptology ePrint Archive, Report 2011/092 (2011); full version of the current paper, http://eprint.iacr.org/2011/092
McAven, L., Safavi-Naini, R., Yung, M.: Unconditionally secure encryption under strong attacks. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 427–439. Springer, Heidelberg (2004)
Pass, R., Shelat, A., Vaikuntanathan, V.: Construction of a non-malleable encryption scheme from any semantically secure one. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 271–289. Springer, Heidelberg (2006)
Pass, R., Shelat, A., Vaikuntanathan, V.: Relations among notions of non-malleability for encryption. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 519–535. Springer, Heidelberg (2007)
Portmann, C., Tanaka, K.: Information-theoretic secrecy with access to decryption oracles. To appear in IEICE Transactions A, Fundamentals of Electronics, Communications and Computer Sciences (2011)
Shannon, C.: Communication theory of secrecy systems. Bell System Technical Journal 28(4), 656–715 (1949)
Stinson, D.R.: Universal hashing and authentication codes. Designs, Codes and Cryptography 4(3), 369–380 (1994); a preliminary version appeared at CRYPTO 1991
Stinson, D.R.: On the connections between universal hashing, combinatorial designs and error-correcting codes. Proceedings of Congressus Numerantium 114, 7–27 (1996)
Stinson, D.R.: Cryptography: Theory and Practice, 2 edn. Chapman & Hall/CRC (2002)
Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences 22(3), 265–279 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kawachi, A., Portmann, C., Tanaka, K. (2011). Characterization of the Relations between Information-Theoretic Non-malleability, Secrecy, and Authenticity. In: Fehr, S. (eds) Information Theoretic Security. ICITS 2011. Lecture Notes in Computer Science, vol 6673. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20728-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-20728-0_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20727-3
Online ISBN: 978-3-642-20728-0
eBook Packages: Computer ScienceComputer Science (R0)