Optimization of the High Nonlinear S-Boxes Generation Method

Mariia Rodinko; Roman Oliynykov; Yurii Gorbenko

doi:10.1515/tmmp-2017-0020

Abstract

The known method of high nonlinear S-boxes generation based on the gradient descent [Kazymyrov, O. V.: Methods and Techniques of Generation of Nonlinear Substitutions for Symmetric Encryption Algorithms. The thesis for the scholarly degree of candidate of technical sciences, speciality 05.13.21 - - Information security systems, Kharkiv National University of Radioelectronics, Kharkiv, 2014. (In Russian)] requires consecutive applications of several criteria for each formed substitution. This paper presents an improvement of the considered method by the appropriate selection of the criteria application order which decreases the required computational power for S-box generation. The proposed modification allows generation of a byte substitution with nonlinearity 104, algebraic immunity 3 and 8-uniformity within approximately 30 minutes of a single PC running time.

References

[1] MENEZES, A. J.-SCOTT, A. V.-VAN OORSCHOT, P. C.: Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL, USA, 1996.
Search in Google Scholar Back to article
[2] GORBENKO, I. D.: Applied Cryptology. Theory. Practice. Application: Monograph. Kharkiv National University of Radioelectronics, JSC Institute of Information Technologies, Kharkiv, 2012. (In Ukrainian)
Search in Google Scholar Back to article
[3] SHANNON, C. E.: Communication Theory of Secrecy Systems. Bell Syst. Tech. J. 28 (1949), 656-715.
Search in Google Scholar Back to article
[4] SOROKA, L. S.-KUZNETSOV, O. O.-MOSKOVCHENKO, I. V.-ISAYEV S. A.: The research of differential properties of block symmetric, Inform. Process. Syst. 6 (2010), 286-294. (In Russian)
Search in Google Scholar Back to article
[5] OLIYNYKOV, R.-KAZYMYROV, O.: An impact of S-box Boolean function properties to strength of modern symmetric block ciphers, Radio Engineering 166 (2011), 11-17.
Search in Google Scholar Back to article
[6] KAZYMYROV, O. V.: Methods and Techniques of Generation of Nonlinear Substitutions for Symmetric Encryption Algorithms. The thesis for the scholarly degree of candidate of technical sciences, speciality 05.13.21-Information security systems, Kharkiv National University of Radioelectronics, Kharkiv, 2014. (In Russian)
Search in Google Scholar Back to article
[7] KAZYMYROV, O.-KAZYMYROVA, V.-OLIYNYKOV, R.: A method for generation of high-nonlinear S-boxes based on gradient descent, IACR Cryptology ePrint Archive, 2013, 578-578.
Search in Google Scholar Back to article
[8] BIHAM, E.-SHAMIR, A.: Differential cryptanalysis of DES-like cryptosystem, J. Cryptology 4 (1991), 3-72.10.1007/BF00630563
Search in Google Scholar Back to article
[9] MATSUI, M.: Linear cryptoanalysis method for DES cipher. In: Adv. in Cryptology- -EUROCRYPT ’93, (T. Helleseth, ed.), Lofthus, Norway, 1993, Lecture Notes in Comput. Sci., Vol. 765, Springer, Berlin, 1994, pp. 386-397.10.1007/3-540-48285-7_33
Search in Google Scholar Back to article
[10] COURTOIS, N. T.-PIEPRZYK, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Proc. of the 8th Internat. Conf. on the Theory and Appl. of Cryptology and Inform. Security-ASIACRYPT ’02, Queenstown, New Zealand, 2002, Lecture Notes in Comput. Sci., Vol. 2501, Springer, Berlin, 2002, pp. 267-287.
Search in Google Scholar Back to article
[11] CRAMA, Y.-HAMMER, P. L.: Boolean Models and Methods inMathematics, Computer Science and Engineering. In: Encyclopedia Math. Appl., Vol. 2, Cambridge University Press, 2010.
Search in Google Scholar Back to article
[12] NYBERG, K.: Differentially uniform mapping for cryptography. In: Adv. in Cryptology- -EUROCRYPT ’93, (T. Helleseth, ed.), Lofthus, Norway, 1993, Lecture Notes in Comput. Sci., Vol. 765, Springer, Berlin, 1994, pp. 55-64.10.1007/3-540-48285-7_6
Search in Google Scholar Back to article
[13] NYBERG, K.: Linear approximation of block ciphers. In: Adv. in Cryptology-EUROCRYPT ’94 (A. De Santis, ed.), Perugia, Italy, 1994, Lecture Notes in Comput. Sci., Vol. 950, Springer, Berlin, 1995, pp. 439-444.10.1007/BFb0053460
Search in Google Scholar Back to article
[14] HONG, S.-LEE, S.-LIM, J.-SUNG, J.-CHEON, D.-CHO, I.: Provable security against differential and linear cryptanalysis for SPN structure. In: Proc. of the 7th Internat. Workshop-FSE ’00 (B. Schneier, ed.), New York, NY, USA, 2000, Lecture Notes in Comput. Sci., Vol. 1978, Springer, Berlin, 2001, pp. 273-283.
Search in Google Scholar Back to article
[15] CARLET, C.: Vectorial Boolean functions for cryptography. In: Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Y. Crama and P. Hammer, eds.), Cambridge University Press, Cambridge, 2010, pp. 39-469.10.1017/CBO9780511780448.012
Search in Google Scholar Back to article
[16] NYBERG, K.: Perfect nonlinear S-boxes. In: Proc. of the Workshop on the Theory and Application of Cryptographic Techniques-EUROCRYPT ’91, Brighton, UK, 1991, Lecture Notes in Comput. Sci., Vol. 547, Springer, Berlin, 1991, pp. 378-386.10.1007/3-540-46416-6_32
Search in Google Scholar Back to article
[17] KAZYMYROV, O. V.-OLIYNYKOV, R. V.: Vectorial Boolean functions application in substitutions generation for symmetric cryptographic transformation, Inform. Process. Syst. 6 (2012), 97-102. (In Russian)
Search in Google Scholar Back to article
[18] NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY (NIST): Advanced Encryption Standard (AES). Federal Information Processing Standards (FIPS) Publication 197, Nov. 2001.
Search in Google Scholar Back to article
[19] TESAR, P.: A new method for generating high non-linearity Sboxes, Radioengineering 19 (2010), 23-26.
Search in Google Scholar Back to article
[20] OLIYNYKOV, R. ET ALL.: DSTU 7624:2014. National Standard of Ukraine. Information technologies. Cryptographic Data Security. Symmetric block transformation algorithm. Ministry of Economical Development and Trade of Ukraine, 2015. (In Ukrainian) Block cipher description is available in Englist at http://eprint.iacr.org/2015/650.pdf
Search in Google Scholar Back to article
[21] OLIYNYKOV, R. ET ALL.: DSTU 7564:2014. National Standard of Ukraine. Information technologies. Cryptographic Data Security. Hash function. Ministry of Economical Development and Trade of Ukraine, 2015. (In Ukrainian)
Search in Google Scholar Back to article

Optimization of the High Nonlinear S-Boxes Generation Method

Abstract

Paradigm

My account