# zbMATH — the first resource for mathematics

On quadratic approximations in block ciphers. (English. Russian original) Zbl 1171.94361
Probl. Inf. Transm. 44, No. 3, 266-286 (2008); translation from Probl. Peredachi Inf. 44, No. 3, 105-127 (2008).
Summary: We consider quadratic approximations (of Boolean functions) of a special form and their potential applications in block cipher cryptanalysis. We show that the use of $$k$$-bent functions as ciphering functions extremely increases the resistance of ciphers to such approximations. We consider examples of 4-bit permutations recommended for use in S-boxes of the algorithms GOST 28147-89, DES, and $$s^{3}$$DES; we show that in almost all cases there exist more probable (than linear) quadratic relations of a special form on input and output bits of these permutations.
##### MSC:
 94A60 Cryptography
Full Text:
##### References:
 [1] Matsui, M. and Yamagishi, A., A New Method for Known Plaintext Attack of FEAL Cipher, Advances in Cryptology–EUROCRYPT’92. Proc. Workshop on the Theory and Application of Cryptographic Techniques, Balatonfüred, Hungary, 1992, Rueppel, R.A., Ed., Lect. Notes Comp. Sci., vol. 658, Berlin: Springer, 1993, pp. 81–91. [2] Matsui, M., Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology–EUROCRYPT’93. Proc. Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, 1993, Helleseth, T., Ed., Lect. Notes Comp. Sci., vol. 765, Berlin: Springer, 1994, pp. 386–397. · Zbl 0951.94519 [3] Biham, E. and Shamir, A., Differential Cryptanalysis of DES-like Cryptosystems, J. Cryptology, 1991, vol. 4, no. 1, pp. 3–72. · Zbl 0729.68017 · doi:10.1007/BF00630563 [4] Nyberg, K., Linear Approximation of Block Ciphers, Advances in Cryptology–EUROCRYPT’94. Proc. Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, 1994, De Santis, A., Ed., Lect. Notes Comp. Sci., vol. 950, Berlin: Springer, 1995, pp. 439–444. · Zbl 0885.94023 [5] Harpers, C., Kramer, G.G., and Massey, J.L., A Generalization of Linear Cryptanalysis and the Applicability of Matsui’s Piling-up Lemma, Advances in Cryptology–EUROCRYPT’95. Proc. Int. Conf. on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, 1995, Guillou, L.C. and Quisquater, J.-J., Eds., Lect. Notes Comp. Sci., vol. 921, Berlin: Springer, 1995, pp. 24–38. · Zbl 0973.94522 [6] Buttyan, L. and Vajda, I., Searching for the Best Linear Approximation of DES-like Cryptosystems, Electron. Lett., 1995, vol. 31, no. 11, pp. 873–874. · doi:10.1049/el:19950590 [7] Matsui, M., New Structure of Block Ciphers with Provable Security Against Differential and Linear Cryptanalysis, Advances in Cryptology–EUROCRYPT’96. Proc. Int. Conf. on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, 1996, Maurer, U.M., Ed., Lect. Notes Comp. Sci., vol. 1070, Berlin: Springer, 1996, pp. 205–218. · Zbl 1373.94925 [8] Daemen, J., Govaerts, R., and Vandewalle, J., Correlation Matrices, Proc. 2nd Int. Workshop on Fast Software Encryption (FSE’94), Leuven, Belgium, 1994, Preneel, B., Ed., Lect. Notes Comp. Sci., vol. 1008, Berlin: Springer, 1995, pp. 275–285. [9] Kaliski, B.S., Jr., and Robshaw, M.J.B., Linear Cryptanalysis Using Multiple Approximations, Advances in Cryptology–CRYPTO’94. Proc. 14th Ann. Int. Cryptology Conf., Santa Barbara, USA, 1994, Desmedt, Y., Ed., Lect. Notes Comp. Sci., vol. 839, Berlin: Springer, 1994, pp. 26–39. · Zbl 0939.94534 [10] Biryukov, A., De Cannière, C., and Quisquater, M., On Multiple Linear Approximations, Advances in Cryptology–CRYPTO 2004. Proc. 24th Ann. Int. Cryptology Conf., Santa Barbara, USA, 2004, Franklin, M.K., Ed., Lect. Notes Comp. Sci., vol. 3152, Berlin: Springer, 2004, pp. 1–22. · Zbl 1104.94018 [11] Sakurai, K. and Furuya, S., Improving Linear Cryptanalysis of LOKI91 by Probabilistic Counting Method, Proc. 4th Int. Workshop on Fast Software Encryption (FSE’97), Haifa, Israel, 1997, Biham, E., Ed., Lect. Notes Comp. Sci., vol. 1267, Berlin: Springer, 1997, pp. 114–133. · Zbl 1385.94069 [12] Baignères, T., Junod, P., and Vaudenay, S., How Far Can We Go beyond Linear Cryptanalysis?, Advances in Cryptology–ASIACRYPT 2004. Proc. 10th Int. Conf. on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, 2004, Lee, P.J., Ed., Lect. Notes Comp. Sci., vol. 3329, Berlin: Springer, 2004, pp. 432–450. · Zbl 1094.94025 [13] Selçuk, A.A., On Probability of Success in Linear and Differential Cryptanalysis, J. Cryptology, 2008, vol. 21, no. 1, pp. 131–147. · Zbl 1147.68510 · doi:10.1007/s00145-007-9013-7 [14] Knudsen, L.R., Practically Secure Feistel Cyphers, Proc. Cambridge Security Workshop on Fast Software Encryption, Cambridge, UK, 1993, Anderson, R.J., Ed., Lect. Notes Comp. Sci., vol. 809, Berlin: Springer, 1994, pp. 211–221. [15] Shorin, V.V., Jelezniakov, V.V., and Gabidulin, E.M., Linear and Differential Cryptanalysis of Russian GOST, Proc. Int. Workshop on Coding and Cryptography (WCC 2001), Paris, France, 2001, Electron. Notes Discrete Math., vol. 6, Amsterdam: Elsevier, 2001, pp. 538–547. · Zbl 0985.94035 [16] Borst, J., Preneel, B., and Vandewalle, J., Linear Cryptanalysis of RC5 and RC6, Proc. 6th Int. Workshop on Fast Software Encryption (FSE’99), Rome, Italy, 1999, Knudsen, L.R., Ed., Lect. Notes Comp. Sci., vol. 1636, Berlin: Springer, 1999, pp. 16–30. · Zbl 0940.94009 [17] Hawkes, P. and O’Connor, L., On Applying Linear Cryptanalysis to IDEA, Advances in Cryptology–ASIACRYPT’96. Proc. Int. Conf. on the Theory and Applications of Cryptology and Information Security, Kyongju, Korea, 1996, Kim, K. and Matsumoto, T., Eds., Lect. Notes Comp. Sci., vol. 1163, Berlin: Springer, 1996, pp. 105–115. · Zbl 1006.94536 [18] Biham, E., Dunkelman, O., and Keller, N., Differential-Linear Cryptanalysis of Serpent, Proc. 10th Int. Workshop on Fast Software Encryption (FSE 2003), Lund, Sweden, 2003, Johansson, T., Ed., Lect. Notes Comp. Sci., vol. 2887, Berlin: Springer, 2003, pp. 9–21. · Zbl 1254.94024 [19] Mansoori, S.D. and Bizaki, H.K., On the Vulnerability of Simplified AES Algorithm Against Linear Cryptanalysis, Int. J. Comp. Sci. Network Security, 2007, vol. 7, no. 7, pp. 257–263. [20] Nakahara, J., Jr., A Linear Analysis of Blowfish and Khufu, Proc. 3rd Int. Conf. on Information Security Practice and Experience (ISPEC 2007), Hong Kong, China, 2007, Dawson, E. and Wong, D.S., Eds., Lect. Notes Comp. Sci., vol. 4464, Berlin: Springer, 2007, pp. 20–32. [21] Rothaus, O.S., On ”Bent” Functions, J. Combin. Theory, Ser. A, 1976, vol. 20, no. 3, pp. 300–305. · Zbl 0336.12012 · doi:10.1016/0097-3165(76)90024-8 [22] Logachev, O.A., Sal’nikov, A.A., and Yashchenko, V.V., Bulevy funktsii v teorii kodirovaniya i kriptologii (Boolean Functions in Coding Theory and Cryptology), Moscow: Mos. Tsentr Nepreryvnogo Mat. Obrazovaniya (MCCME), 2004. [23] Dobbertin, H. and Leander, G., A Survey of Some Recent Results on Bent Functions, Proc. 3rd Int. Conf. on Sequences and Their Applications (SETA 2004), Seul, Korea, 2004, Helleseth, T., Sarwate, D.V., Song, H.-Y., and Yang, K., Eds., Lect. Notes Comp. Sci., vol. 3486, Berlin: Springer, 2005, pp. 1–29. · Zbl 1145.94439 [24] Chee, S., Lee, S., and Kim, K., Semi-bent Functions, Advances in Cryptology–ASIACRYPT’94. Proc. 4th Int. Conf. on the Theory and Applications of Cryptology, Wollongong, Australia, 1994, Pieprzyk, J. and Safavi-Naini, R., Eds., Lect. Notes Comp. Sci., vol. 917, Berlin: Springer, 1995, pp. 107–118. [25] Dobbertin, H. and Leander, G., Cryptographer’s Toolkit for Construction of 8-Bit Bent Functions, Cryptology ePrint Archive, Report no. 2005/089. Available at http://eprint.iacr.org/2005/089 . [26] Qu, C., Seberry, J., and Pieprzyk, J., Homogeneous Bent Functions, Discrete Appl. Math., 2000, vol. 102, no. 1–2, pp. 133–139. · Zbl 1016.94029 · doi:10.1016/S0166-218X(99)00234-6 [27] Youssef, A.M. and Gong, G., Hyper-Bent Functions, Advances in Cryptology–EUROCRYPT 2001. Proc. 20th Int. Ann. Conf. on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, Pfitzmann, B., Ed., Lect. Notes Comp. Sci., vol. 2045, Berlin: Springer, 2001, pp. 406–419. · Zbl 1013.94544 [28] Kuz’min, A.S., Markov, V.T., Nechaev, A.A., and Shishkov, A.B., Approximation of Boolean Functions by Monomial Ones, Diskret. Mat., 2006, vol. 18, no. 1, pp. 9–29 [Discrete Math. Appl. (Engl. Transl.), 2006, vol. 16, no. 1, pp. 7–28]. · Zbl 1103.94035 · doi:10.4213/dm29 [29] Carlet, C. and Gaborit, P., Hyper-bent Functions and Cyclic Codes, J. Combin. Theory, Ser. A, 2006, vol. 113, no. 3, pp. 466–482. · Zbl 1086.94031 · doi:10.1016/j.jcta.2005.04.008 [30] Youssef, A.M., Generalized Hyper-bent Functions over GF(p), Discrete Appl. Math., 2007, vol. 155, no. 8, pp. 1066–1070. · Zbl 1183.94049 · doi:10.1016/j.dam.2006.11.007 [31] Kuz’min, A.S., Markov, V.T., Nechaev, A.A., Shishkin, V.A., and Shishkov, A.B., Bent and Hyper-bent Functions over a Field of 2 Elements, Probl. Peredachi Inf., 2008, vol. 44, no. 1, pp. 15–37 [Probl. Inf. Trans. (Engl. Transl.), 2008, vol. 44, no. 1, pp. 12–33]. [32] Parker, M.G. and Pott, A., On Boolean Functions Which Are Bent and Negabent, Int. Workshop on Sequences, Subsequences, and Consequences (SSC 2007), Los Angeles, USA, 2007. Revised Invited Papers, Golomb, S.W., Gong, G., Helleseth, T., and Song, H.-Y., Eds., Lect. Notes Comp. Sci., vol. 4893, Berlin: Springer, 2007, pp. 9–23. · Zbl 1154.94426 [33] Knudsen, L.R. and Robshaw, M.J.B., Non-linear Approximations in Linear Cryptanalysis, Advances in Cryptology–EUROCRYPT’96. Proc. Int. Conf. on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, 1996, Maurer, U.M., Ed., Lect. Notes Comp. Sci., vol. 1070, Berlin: Springer, 1996, pp. 224–236. · Zbl 1304.94069 [34] Shimoyama, T. and Kaneko, T., Quadratic Relation of S-box and Its Application to the Linear Attack of Full Round DES, Advances in Cryptology–CRYPTO’98. Proc. 18th Ann. Int. Cryptology Conf., Santa Barbara, USA, 1998, Krawczyk, H., Ed., Lect. Notes Comp. Sci., vol. 1462, Berlin: Springer, 1998, pp. 200–211. · Zbl 0931.94038 [35] Nakahara, J., Jr., Preneel, B., and Vandewalle, J., Experimental Non-linear Cryptanalysis, COSIC Internal Report, Katholieke Univ. Leuven, 2003. [36] Estévez-Tapiador, J.M., Clark, J.A., and Hernández-Castro, J.C., Non-linear Cryptanalysis Revisited: Heuristic Search for Approximations to S-Boxes, Cryptography and Coding. Proc. 11th IMA Int. Conf., Cirencester, UK, 2007, Galbraith, S.D., Ed., Lect. Notes Comp. Sci., vol. 4887, Berlin: Springer, 2007, pp. 99–117. · Zbl 1154.94434 [37] Ryazanov, B.V. and Chechëta, S.I., On the Approximation of a Random Boolean Function by a Set of Quadratic Forms, Diskret. Mat., 1995, vol. 7, no. 3, pp. 129–145 [Discrete Math. Appl. (Engl. Transl.), 1995, vol. 5, no. 5, pp. 473–489]. [38] Ivanov, A.V., Using Reduced Representations of Boolean Functions in Constructing Their Nonlinear Approximations, Vestn. Tomsk. Gos. Univ., 2007, no. 23, pp. 31–35. [39] Tokareva, N.N., Bent Functions with Stronger Nonlinearity Properties: k-Bent Functions, Diskretn. Anal. Issled. Oper., Ser. 1, 2007, vol. 14, no. 4, pp. 76–102 [J. Appl. Indust. Math. (Engl. Transl.), 2008, vol. 2, no. 4, to appear]. · Zbl 1249.94039 [40] Krotov, D.S., $$\mathbb{Z}$$4-linear Perfect Codes, Diskretn. Anal. Issled. Oper., Ser. 1, 2000, vol. 7, no. 4, pp. 78–90 (Engl. transl. available at http://arxiv.org/abs/0710.0198 ). [41] Krotov, D.S., $$\mathbb{Z}$$4-linear Hadamard and Extended Perfect Codes, in Proc. Int. Workshop on Coding and Cryptography, 2001, Paris, France, pp. 329–334. [42] Tokareva, N.N., Description of k-Bent Functions in Four Variables, Diskretn. Anal. Issled. Oper., Ser. 1, 2008, vol. 15, no. 4, pp. 74–83. · Zbl 1249.94086 [43] Rostovtsev, A.G. and Makhovenko, E.B., Vvedenie v teoriyu iterirovannykh shifrov (Introduction to the Theory of Iterated Ciphers), St. Petersburg: Mir i Sem’ya, 2003. [44] Heys, H.M. and Tavares, S.E., Substitution-Permutation Networks Resistant to Differential and Linear Cryptanalysis, J. Cryptology, 1996, vol. 9, no. 1, pp. 1–19. · Zbl 0843.94009 · doi:10.1007/BF02254789 [45] Schneier, B., Applied Cryptography: Protocols, Algorithms, and Source Code in C, New York: Wiley, 1996, 2nd ed. Translated under the title Prikladnaya kriptografiya. Protokoly, algoritmy, ishodnye teksty na yazyke Si Moscow: Triumf, 2002. · Zbl 0853.94001 [46] Kim, K., Park, S., and Lee, S., Reconstruction of s 2DES S-Boxes and Their Immunity to Differential Cryptanalysis, in Proc. 1993 Korea-Japan Joint Workshop on Information Security and Cryptography, Seoul, Korea, 1993, pp. 282–291. [47] Biham, E. and Biryukov, A., How to Strengthen DES Using Existing Hardware, Advances in Cryptology–ASIACRYPT’94. Proc. 4th Int. Conf. on the Theory and Applications of Cryptology, Wollongong, Australia, 1994, Pieprzyk, J. and Safavi-Naini, R., Eds., Lect. Notes Comp. Sci., vol. 917, Berlin: Springer, 1995, pp. 398–412. · Zbl 0873.94014 [48] Nechaev, A.A., Kerdock Code in a Cyclic Form, Diskret. Mat., 1989, vol. 1, no. 4, pp. 123–139 [Discrete Math. Appl. (Engl. Transl.), 1991, vol. 1, no. 4, pp. 365–384]. · Zbl 0718.94012 [49] Hammons, A.R., Jr., Kumar, P.V., Calderbank, A.R., Sloane, N.J.A., and Solé, P., The $$\mathbb{Z}$$4-Linearity of Kerdock, Preparata, Goethals, and Related Codes, IEEE Trans. Inform. Theory, 1994, vol. 40, no. 2, pp. 301–319. · Zbl 0811.94039 · doi:10.1109/18.312154
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.