[en] We describe the first domain extender for ideal ciphers, i.e. we show a construction that is indifferentiable from a 2n-bit ideal cipher, given a n-bit ideal cipher. Our construction is based on a 3-round Feistel, and is more efficient than first building a n-bit random oracle from a n-bit ideal cipher (as in [9]) and then a 2n-bit ideal cipher from a n-bit random oracle (as in [10], using a 6-round Feistel). We also show that 2 rounds are not enough for indifferentiability by exhibiting a simple attack. We also consider our construction in the standard model: we show that 2 rounds are enough to get a 2n-bit tweakable block-cipher from a n-bit tweakable block-cipher and we show that with 3 rounds we can get beyond the birthday security bound.
Disciplines :
Sciences informatiques
Identifiants :
UNILU:UL-CONFERENCE-2010-081
Auteur, co-auteur :
CORON, Jean-Sébastien ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Dodis, Yevgeniy; New York University
MANDAL, Avradip ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Seurin, Yannick; Orange Labs
Langue du document :
Anglais
Titre :
A Domain Extender for the Ideal Cipher
Date de publication/diffusion :
2010
Nom de la manifestation :
TCC
Lieu de la manifestation :
Zurich, Suisse
Date de la manifestation :
9-11 février 2010
Titre de l'ouvrage principal :
Proceedings of TCC 2010
Maison d'édition :
Springer
ISBN/EAN :
978-3-642-11798-5
Pagination :
273-289
Peer reviewed :
Peer reviewed
Commentaire :
5978
Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62-73 (1993)
Biryukov, A., Khovratovich, D., Nikolic, I.: Distinguisher and Related-Key Attack on the Full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231-249. Springer, Heidelberg (2009)
Biryukov, A., Khovratovich, D.: Related-key Cryptanalysis of the Full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1-18. Springer, Heidelberg (2009)
Black, J.: The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 328-340. Springer, Heidelberg (2006)
Black, J., Rogaway, P., Shrimpton, T.: Black-Box Analysis of the Block Cipher-Based Hash-Function Constructions from PGV. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 320. Springer, Heidelberg (2002)
Chakraborty, D., Sarkar, P.: A new mode of encryption providing a tweakable strong pseudo-random permutation. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 293-309. Springer, Heidelberg (2006)
Chakraborty, D., Sarkar, P.: HCH: A new tweakable enciphering scheme using the hash-encrypt-hash approach. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 287-302. Springer, Heidelberg (2006)
Coron, J.S., Dodis, Y., Mandal, A., Seurin, Y.: A Domain Extender for the Ideal Cipher. Full version of this paper. Cryptology ePrint Archive, Report 2009/356, http://eprint.iacr.org/
Coron, J.S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård Revisited: How to Construct a Hash Function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430-448. Springer, Heidelberg (2005)
Coron, J.S., Patarin, J., Seurin, Y.: The Random Oracle Model and the Ideal Cipher Model are Equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 1-20. Springer, Heidelberg (2008), Full version available at Cryptology ePrint Archive, Report 2008/246, http://eprint.iacr.org/
Desai, A.: The security of all-or-nothing encryption: Protecting against exhaustive key search. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, p. 359. Springer, Heidelberg (2000)
Dodis, Y., Puniya, P.: On the Relation Between the Ideal Cipher and the Random Oracle Models. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 184-206. Springer, Heidelberg (2006)
Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. In: Matsumoto, T., Imai, H., Rivest, R.L. (eds.) ASIACRYPT 1991. LNCS, vol. 739, pp. 210-224. Springer, Heidelberg (1993)
Fluhrer, S.R., McGrew, D.A.: The extended codebook (XCB) mode of operation. Technical Report 2004/078, IACR eprint archive (2004)
Granboulan, L.: Short signature in the random oracle model. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 364-378. Springer, Heidelberg (2002)
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)
Halevi, S.: Invertible Universal hashing and the TET Encryption Mode. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 412-429. Springer, Heidelberg (2007)
Jonsson, J.: An OAEP variant with a tight security proof, http://eprint.iacr.org/2002/034/
Kilian, J., Rogaway, P.: How to protect DES against exhaustive key search (An analysis of DESX). Journal of Cryptology 14(1), 17-35 (2001)
Krovetz, T.: Message Authentication on 64-Bit Architectures. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 327-341. Springer, Heidelberg (2007)
Liskov, M., Rivest, R., Wagner, D.: Tweakable Block Ciphers. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 31. Springer, Heidelberg (2002)
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal of Computing 17(2), 373-386 (1988)
Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21-39. Springer, Heidelberg (2004)
Minematsu, K.: Beyond-Birthday-Bound Security Based on Tweakable Block Cipher. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 308-326. Springer, Heidelberg (2009)
Naor, M., Reingold, O.: On the construction of pseudorandom permutations: Luby-Rackoff revisited. J. of Cryptology (1999); Preliminary Version: STOC 1997
Rogaway, P., Bellare, M., Black, J.: OCB: A block-cipher mode of operation for efficient authenticated encryption. In: ACM Conference on Computer and Communication Security, pp. 196-205 (2001)
Shoup, V.: Sequences of games: a tool for taming complexity in security proofs, http://eprint.iacr.org/2004/332/
Wang, P., Feng, D., Wu, W.: HCTR: A variable-input-length enciphering mode. In: Feng, D., Lin, D., Yung, M. (eds.) CISC 2005. LNCS, vol. 3822, pp. 175-188. Springer, Heidelberg (2005)
