The security of triple encryption and a framework for code-based game-playing proofs. (English) Zbl 1140.94321

Bellare, Mihir; Rogaway, Phillip

Vaudenay, Serge (ed.), Advances in cryptology – EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28 – June 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34546-9/pbk). Lecture Notes in Computer Science 4004, 409-426 (2006).

Summary: We show that, in the ideal-cipher model, triple encryption (the cascade of three independently-keyed blockciphers) is more secure than single or double encryption, thereby resolving a long-standing open problem. Our result demonstrates that for DES parameters (56-bit keys and 64-bit plaintexts) an adversary’s maximal advantage against triple encryption is small until it asks about \(2^{78}\) queries. Our proof uses code-based game-playing in an integral way, and is facilitated by a framework for such proofs that we provide.
For the entire collection see [Zbl 1108.94002].

MSC:

94A60

Cryptography

References:

[1]	Aiello, W., Bellare, M., Di Crescenzo, G., Venkatesan, R.: Security amplification by composition: The case of doubly-iterated, ideal ciphers. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 390–407. Springer, Heidelberg (1998) · Zbl 0931.94011
[2]	Bellare, M., Goldwasser, S.: New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 194–211. Springer, Heidelberg (1990) · Zbl 0722.68042
[3]	Bellare, M., Rogaway, P.: Code-based game-playing proofs and the security of triple encryption. Cryptology ePrint archive report 2004/331 (2006)
[4]	Diffie, W., Hellman, M.: Exhaustive cryptanalysis of the data encryption standard. Computer 10, 74–84 (1977) · Zbl 05332334
[5]	Even, S., Goldreich, O.: On the power of cascade ciphers. ACM Transactions on Computer Systems 3(2), 108–116 (1985)
[6]	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) · Zbl 0808.94024
[7]	Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984) (earlier version in STOC 1982) · Zbl 0563.94013
[8]	Halevi, S.: A plausible approach to computer-aided cryptographic proofs. Cryptology ePrint archive report 2005/181 (2005)
[9]	Kilian, J., Rogaway, P.: How to protect DES against exhaustive key search (an analysis of DESX). J. of Cryptology 14(1), 17–35 (2001) (earlier version in Crypto 1996) · Zbl 1068.94531
[10]	Lucks, S.: Attacking triple encryption. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, pp. 239–253. Springer, Heidelberg (1998) · Zbl 1385.94056
[11]	Maurer, U., Massey, J.: Cascade ciphers: The importance of being first. J. of Cryptology 6(1), 55–61 (1993) · Zbl 0775.94096
[12]	Merkle, R., Hellman, M.: On the security of multiple encryption. Communications of the ACM 24, 465–467 (1981)
[13]	National Institute of Standards and Technology. FIPS PUB 46-3, Data Encryption Standard (DES), Also ANSI X9.52, Triple Data Encryption Algorithm modes of operation, 1998, and other standards (1999)
[14]	Shannon, C.: Communication theory of secrecy systems. Bell Systems Technical Journal 28(4), 656–715 (1949) · Zbl 1200.94005
[15]	Shoup, V.: Sequences of games: A tool for taming complexity in security proofs. Cryptology ePrint archive report 2004/332 (2006)
[16]	Yao, A.: Theory and applications of trapdoor functions. In: IEEE Symposium on the Foundations of Computer Science (FOCS 1982), pp. 80–91. IEEE Press, Los Alamitos (1982)