Abstract
This paper describes a hybrid symmetric cipher that combines a strongly-secure function, e.g., a pseudorandom function (PRF), which is secure against any Chosen-Plaintext Attack, and a weak PRF, which is only secure against any Known-Plaintext Attack. Although this kind of composition is potentially faster than the modes of PRFs, it has not been extensively studied. Our main contribution is in proposing a new block cipher scheme that is suitable for hybrid composition. We describe efficient hybrid constructions of pseudorandom permutation and strong pseudorandom permutation for an arbitrarily large block size using our new scheme.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aiello, W., Rajagopalan, S., Venkatesan, R.: High-Speed Pseudorandom Number Generation with Small Memory. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 290–304. Springer, Heidelberg (1999)
Anderson, R., Biham, E.: Two Practical and Provably Secure Block Ciphers: BEAR and LION. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 113–120. Springer, Heidelberg (1996)
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A Concrete Security Treatment of Symmetric Encryption. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, pp. 394–403 (1997)
Biryukov, A.: New 128-bit Key Stream Cipher LEX. ECRYPT Stream Cipher Project Report, available from: http://www.ecrypt.eu.org/stream/
Daemen, J., Govaerts, R., Vandewalle, J.: Resynchronization Weaknesses in Synchronous Stream Ciphers. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 159–167. Springer, Heidelberg (1994)
Damgård, I., Nielsen, J.: Expanding Pseudorandom Functions; or: From Known-Plaintext Security to Chosen-Plaintext Security. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 449–464. Springer, Heidelberg (2002)
Goldreich, O., Goldwasser, S., Micali, S.: How to Construct Random Functions. Journal of the ACM 33(4), 792–807 (1986)
Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Springer, Heidelberg
Halevi, S., Krawczyk, H.: MMH:Software Message Authentication in the Gbit/second rates. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 172–189. Springer, Heidelberg (1997)
Halevi, S., Rogaway, P.: A Tweakable Enciphering Mode. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 482–499. Springer, Heidelberg (2003)
Halevi, S., Rogaway, P.: A Parallelizable Enciphering Mode. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 292–304. Springer, Heidelberg (2004)
Iwata, T., Kurosawa, K.: On the Universal Hash Functions in Luby-Rackoff Cipher. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 226–236. Springer, Heidelberg (2003)
Luby, M., Rackoff, C.: How to Construct Pseudo-random Permutations from Pseudo-random functions. SIAM J. Computing 17(2), 373–386 (1988)
Lucks, S.: Faster Luby-Rackoff Ciphers. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 189–203. Springer, Heidelberg (1996)
Maurer, U.: A Simplified and Generalized Treatment of Luby-Rackoff Pseudorandom Permutation Generators. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 239–255. Springer, Heidelberg (1993)
Maurer, U., Massey, J.L.: Cascade Ciphers: The Importance of Being First. J. Cryptology 6(1), 55–61 (1993)
Maurer, U.: Indistinguishability of Random Systems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 110–132. Springer, Heidelberg (2002)
Maurer, U., Pietrzak, K.: Composition of Random Systems: When Two Weak Make One Strong. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 410–427. Springer, Heidelberg (2004)
Minier, M., Gilbert, H.: New Results on the Pseudorandomness of Some Blockcipher Constructions. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 248–266. Springer, Heidelberg (2002)
Moriai, S., Vaudenay, S.: On the Pseudorandomness of Top-Level Schemes of Block Ciphers. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 289–302. Springer, Heidelberg (2000)
Myers, S.: Black-Box Composition Does Not Imply Adaptive Security. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 189–206. Springer, Heidelberg (2004)
Naor, M., Reingold, O.: Number-theoretic Constructions of Efficient Pseudo-random Functions. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, pp. 458–467 (1997)
Naor, M., Reingold, O.: From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs (Extended Abstract). In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 267–282. Springer, Heidelberg (1998)
Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. J. of Computer and Systems Sciences 58(2), 336–375 (1999)
Naor, M., Reingold, O.: On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited. Journal of Cryptology 12(1), 29–66 (1999)
Naor, M., Reingold, O.: The NR Mode of Operation (manuscript), available from: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/nr-mode.ps
Patel, S., Ramzan, Z., Sundaram, G.: Towards Making Luby-Rackoff Ciphers Optimal and Practical. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 171–185. Springer, Heidelberg (1999)
Patarin, J.: Security of Random Feistel Schemes with 5 or More Rounds. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 106–122. Springer, Heidelberg (2004)
Vaudenay, S.: Feistel Ciphers with L 2-Decorrelation. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 1–14. Springer, Heidelberg (1999)
Vaudenay, S.: Provable Security for Block Ciphers by Decorrelation. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 249–275. Springer, Heidelberg (1998)
Vaudenay, S.: Adaptive-Attack Norm for Decorrelation and Super-Pseudorandomness. In: Heys, H.M., Adams, C.M. (eds.) SAC 1999. LNCS, vol. 1758, pp. 49–61. Springer, Heidelberg (2000)
Wegman, M., Carter, L.: New Hash Functions and Their Use in Authentication and Set Equality. Journal of Computer and System Sciences 22, 265–279 (1981)
Zheng, Y., Matsumoto, T., Imai, H.: On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 461–480. Springer, Heidelberg (1990)
ECRYPT Stream Cipher Project, http://www.ecrypt.eu.org/stream/
Security in Storage Working Group, An IEEE Information Assurance Activity, http://www.siswg.org
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Minematsu, K., Tsunoo, Y. (2006). Hybrid Symmetric Encryption Using Known-Plaintext Attack-Secure Components. In: Won, D.H., Kim, S. (eds) Information Security and Cryptology - ICISC 2005. ICISC 2005. Lecture Notes in Computer Science, vol 3935. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11734727_21
Download citation
DOI: https://doi.org/10.1007/11734727_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33354-8
Online ISBN: 978-3-540-33355-5
eBook Packages: Computer ScienceComputer Science (R0)