Abstract
A standard notion of non-malleability is that an adversary cannot forge a ciphertext c′ from a single valid ciphertext c for which a plaintext m′ of c′ is meaningfully related to a plaintext m of c. The multi-ciphertext non-malleability is a stronger notion; an adversary is allowed to obtain multiple ciphertexts c 1,c 2,... in order to forge c′. We provide an efficient symmetric-key encryption scheme with an information-theoretic version of the multi-ciphertext non-malleability in this paper by using ℓ-wise almost independent permutations of Kaplan, Naor, and Reingold.
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
Brodsky, A., Hoory, S.: Simple permutations mix even better. Random Struct. Algorithms 32(3), 274–289 (2008)
Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM J. Comput. 30(2), 391–437 (2000)
Gowers, W.T.: An almost m-wise independent random permutation of the cube. Combinatorics, Probability & Computing 5, 119–130 (1996)
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., Shikata, J., Hanaoka, Y., Imai, H.: Unconditionally secure anonymous encryption and group authentication. Comput. J. 49(3), 310–321 (2006)
Hoory, S., Magen, A., Myers, S., Rackoff, C.: Simple permutations mix well. Theor. Comput. Sci. 348(2-3), 251–261 (2005)
Kaplan, E., Naor, M., Reingold, O.: Derandomized constructions of k-wise (almost) independent permutations. Algorithmica 55(1), 113–133 (2009)
Kawachi, A., Portmann, C., Tanaka, K.: Characterization of the Relations between Information-Theoretic Non-malleability, Secrecy, and Authenticity. In: Fehr, S. (ed.) ICITS 2011. LNCS, vol. 6673, pp. 6–24. Springer, Heidelberg (2011)
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.: Relations Among Notions of Non-malleability for Encryption. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 519–535. Springer, Heidelberg (2007)
Rees, E.G.: Notes on geometry. Springer (1983)
Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4) (2008)
Russell, A., Wang, H.: How to fool an unbounded adversary with a short key. IEEE Transactions on Information Theory 52(3), 1130–1140 (2006)
Saks, M.E., Srinivasan, A., Zhou, S., Zuckerman, D.: Low discrepancy sets yield approximate min-wise independent permutation families. Inf. Process. Lett. 73(1-2), 29–32 (2000)
Shannon, C.: Communication theory of secrecy systems. Bell System Technical Journal 28(4), 656–715 (1949)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kawachi, A., Takebe, H., Tanaka, K. (2012). Symmetric-Key Encryption Scheme with Multi-ciphertext Non-malleability. In: Hanaoka, G., Yamauchi, T. (eds) Advances in Information and Computer Security. IWSEC 2012. Lecture Notes in Computer Science, vol 7631. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34117-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-34117-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34116-8
Online ISBN: 978-3-642-34117-5
eBook Packages: Computer ScienceComputer Science (R0)