Construção de S-Boxes com Valores Ótimos de Não Linearidade Baseada em uma Relação entre o Multigrafo de Ramanujan e a Matriz da Transformação Afim

• Marcio Belleza LNCC
• Fábio Borges LNCC

DOI: https://doi.org/10.5753/sbseg.2019.13974

Abstract

A substitution box (S-Box) must have at least optimal values for nonlinearity (N L), differential uniformity, and algebraic degree. According to the literature, a cryptographically strong S-Box must have N L > 100. Advanced Encryption Standard (AES) uses a non-singular binary matrix S to generate its S-Box. Several papers choose S from approximately 2⁶² non-singular matrices or construct S-Box randomly, without guaranteeing N L > 100. In this paper, we identify that S can be studied as an adjacency matrix (A(G)) of a Ramanujan multigraph, and verify this relationship with other rotational matrices A(G). Thus, we reduced the search for S to the order of 10¹¹ and construct S-Boxes with N L > 100.

References

Bondy, J. A. (1976). Graph Theory With Applications. Elsevier Science Ltd., Oxford, UK, UK.

Canteaut, A. (2016). Lecture notes on cryptographic Boolean functions. Inria, Paris, France.

Carlet, C. (2010). Boolean Functions for Cryptography and Error-Correcting Codes, page 257–397. Encyclopedia of Mathematics and its Applications. Cambridge University Press.

Carlet, C. and Ding, C. (2007). Nonlinearities of s-boxes. Finite Fields and Their Applications, 13(1):121 – 135.

Chandrasekharappa, T. (2012). Enhancement of confidentiality and integrity using cryptographic techniques. PhD thesis, Manipal University, Manipal - India.

Chandrasekharappa, T., Prema, K., and Kumara, S. (2011). S-boxes generated using affine transformation giving maximum avalanche effect. Int. J. Comput. Sci. Eng., 3(9):3185–3193.

Charles, D. X., Lauter, K. E., and Goren, E. Z. (2009). Cryptographic hash functions from expander graphs. Journal of Cryptology, 22(1):93–113.

Costache, A., Feigon, B., Lauter, K. E., Massierer, M., and Puskás, A. (2018). Ramanujan graphs in cryptography. IACR Cryptology ePrint Archive, 2018:593.

Cui, J., Huang, L., Zhong, H., Chang, C., and Yang, W. (2011). An improved AES s-box and its performance analysis. International Journal of Innovative Computing, Information and Control, 7:2291–2302.

Daemen, J. and Rijmen, V. (2002). The Design of Rijndael. Springer-Verlag, Berlin, Heidelberg.

Das, S., Zaman, J. U., and Ghosh, R. (2013). Generation of AES s-boxes with various modulus and additive constant polynomials and testing their randomization. Procedia Technology, 10:957 – 962. First International Conference on Computational Intelligence: Modeling Techniques and Applications (CIMTA) 2013.

Davidoff, G., Sarnak, P., and Valette, A. (2003). Elementary Number Theory, Group Theory and Ramanujan Graphs. Number 55 in London Mathematical Society Student Texts. Cambridge University Press.

de la Cruz Jiménez, R. A. (2019). Generation of 8-bit s-boxes having almost optimal cryptographic properties using smaller 4-bit s-boxes and finite field multiplication. In Lange, T. and Dunkelman, O., editors, Progress in Cryptology – LATINCRYPT 2017, pages 191–206, Cham. Springer International Publishing.

Deva Sinha, S. and Arya, C. (2012). Algebraic construction and cryptographic properties of Rijndael substitution box. Defence Science Journal, 62:32–37.

Hoory, S., Linial, N., and Wigderson, A. (2006). Expander graphs and their applications. BULL. AMER. MATH. SOC., 43(4):439–561.

Isa, H., Jamil, N., and Reza Z ’aba, M. (2016). Hybrid heuristic methods in constructing cryptographically strong s-boxes. International Journal of Cryptology Research, 6:1– 15.

Klima, R. and Sigmon, N. (2016). Applied abstract algebra with MAPLE and MATLAB. Textbook in mathematics. CRC Press, London, 3rd ed. edition.

Lubotzky, A., Phillips, R., and Sarnak, P. (1988). Ramanujan graphs. Combinatorica, 8(3):261–277.

Meier,W. and Staffelbach, O. (1990). Nonlinearity criteria for cryptographic functions. In Quisquater, J.-J. and Vandewalle, J., editors, Advances in Cryptology — EUROCRYPT ’89, pages 549–562, Berlin, Heidelberg. Springer Berlin Heidelberg.

Murty, M. R. (2003). Ramanujan graphs. J. Ramanujan Math. Soc, 18:1–20.

Nover, H. (2005). Algebraic Cryptanalysis of AES: An Overview. University of Wisconsin, USA, pages 1–16.

Paar, C. and Pelzl, J. (2010). The Data Encryption Standard (DES) and Alternatives, pages 55–86. Springer Berlin Heidelberg, Berlin, Heidelberg.

Shannon, C. E. (1949). Communication theory of secrecy systems. The Bell System Technical Journal, 28(4):656–715.

Sloane, N. J. A. (2019). The on-line encyclopedia of integer sequences. http://oeis.org.

Stanica, P. (2007). Graph eigenvalues and Walsh spectrum of Boolean functions. Integers: Electronic Journal of Combinatorial Number Theory, 7(2).

Tao, T. (2015). Expansion in Finite Simple Groups of Lie Type. Graduate Studies in Mathematics: 164. American Mathematical Society, United States of America.

The Sage Developers (2009). SageMath, the Sage Mathematics Software System (Version 4.3). https://www.sagemath.org.

Waqas, U., Afzal, S., Mir, M. A., and Yousaf, M. (2014). Generation of AES-like sboxes by replacing affine matrix. In 2014 12th International Conference on Frontiers of Information Technology, pages 159–164.