Article Contents
Article Contents

# Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations

• *Corresponding author: Selçuk Kavut

This work is supported financially by Balıkesir University under grant BAP 2015/23

• We first give a brief survey of the results on highly nonlinear single-output Boolean functions and bijective S-boxes that are symmetric under some permutations. After that, we perform a heuristic search for the symmetric (and involution) S-boxes which are bijective in dimension 8 and identify corresponding permutations yielding rich classes in terms of cryptographically desirable properties.

Mathematics Subject Classification: 11T71, 94A60.

 Citation:

• Table 1.  A summary of the highest nonlinearities for odd $n\ge 9$

 Number of variables ($n$) 9 11 13 15 Bounds Bent concatenation bound 240 992 4032 16256 ($2^{n-1}-2^\frac{n-1}{2}$) Upper bound 244 1000 4050 16292 ($2\left\lfloor 2^{n-2}-2^{\frac{n}{2}-2}\right\rfloor$) Unbalanced nonlinearities [18] $-$ $-$ $-$ 16276 [13] 242 996 4040 $-$ Balanced nonlinearities [15] $-$ $-$ 4036 $-$ [20] $-$ $-$ $-$ 16272

Table 2.  Best achieved cryptographic properties [nonlinearity, differential uniformity, algebraic degree]

 $\#$ Representativepermutation Space size Best result (for involution S-boxes) Best result 1 $(7,6,2,1,8,5,4,3)$ $2^{147.93}$ $[84,44,7]$ $[84,44,7]$ 2 $(2,3,1,7,4,5,6,8)$ $2^{191.48}$ $[84,52,7]$ $[84,52,7]$ 3 $(6,7,5,8,4,3,1,2)^a$ $2^{208.29}$ $\bf{[106,6,7]}$ $\bf{[106,6,7]}, \bf{[108,8,6]}$ 4 $(4,3,2,5,8,1,7,6)$ $2^{227.35}$ $[0, -, -]$ $[0, -, -]$ 5 $(4,5,3,2,8,1,6,7)$ $2^{243.74}$ $\bf {[106,6,7]}$ $\bf {[106,6,7]}$ 6 $(8,3,4,6,7,1,5,2)$ $2^{277.78}$ $[104,6,7]$ $[104,6,7], {\bf{[106,8,7]}}$ 7 $(8,6,3,5,2,1,7,4)$ $2^{283.02}$ $[104,10,7]$ $\it {[104,8,7]}$ 8 $(4,6,7,5,1,2,3,8)$ $2^{357.97}$ $[84,44,7]$ $[84,44,7]$ 9 $(2,6,3,4,5,8,1,7)$ $2^{358.65}$ $[100,10,7]$ $[100,10,7],\it{[104,20,7]}$ 10 $(7,3,6,1,8,2,4,5)$ $2^{359.22}$ $[0, -, -]$ $[0, -, -]$ 11 $(7,6,1,2,3,8,5,4)^b$ $2^{412.21}$ $[104,6,7]$ $[104,6,7], {\bf{[106,8,7]}}$ 12 $(2,7,4,3,5,6,1,8)$ $2^{431.91}$ $[0, -, -]$ $[0, -, -]$ 13 $(6,4,8,2,1,7,5,3)$ $2^{440.19}$ $[84,22,7]$ $[84,22,7]$ 14 $(1,3,6,7,2,5,4,8)$ $2^{446.24}$ $[84,22,7]$ $[84,22,7]$ 15 $(1,5,6,4,3,2,7,8)$ $2^{476.86}$ $[84,52,7]$ $[84,52,7]$ 16 $(4,3,8,5,1,6,7,2)$ $2^{565.87}$ $[104,6,7]$ $[104,6,7]$ 17 $(1,6,3,4,2,5,7,8)$ $2^{693.43}$ $[84,44,7]$ $[84,44,7]$ 18 $(7,6,5,8,3,2,1,4)^c$ $2^{824.73}$ $[104,6,7]$ $[104,6,7]$ 19 $(1,5,8,4,2,7,6,3)$ $2^{835.24}$ $[104,8,7]$ $[104,8,7]$ 20 $(1,2,7,4,5,8,3,6)$ $2^{890.27}$ $[84,22,7]$ $[84,22,7]$ 21 $(8,2,3,4,5,6,7,1)$ $2^{1076.16}$ $[0, -, -]$ $[0, -, -]$ 22 $(1,2,3,4,5,6,7,8)^d$ $2^{1684}$ $[102,6,7]$ $\it{[104,6,7]}$ $^a:$ Linear equivalet to RSSBs $^b:$ Linear equivalent to 2-RSSBs $^c:$ Linear equivalent to 4-RSSBs $^d:$ The search space of all bijective S-boxes
•  [1] M. Bartholomew-Biggs, Chapter 5: The steepest descent method, in Nonlinear Optimization with Financial Applications. Springer US, (2005), 51–64. [2] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563. [3] K. A. Browning, J. F. Dillon, M. T. McQuistan and A. J. Wolfe, An APN permutation in dimension six, Contemporary Mathematics, 518 (2010), 33-42.  doi: 10.1090/conm/518/10194. [4] C. Ding, G. Xiao and W. Shan, The Stability Theory of Stream Ciphers, Lecture Notes in Computer Science, 561. Springer-Verlag, Berlin Heidelberg, 1991. doi: 10.1007/3-540-54973-0. [5] H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, Lecture Notes in Computer Science, 1008 (1994), 61-74.  doi: 10.1007/3-540-60590-8_5. [6] E. Filiol and C. Fontaine, Highly nonlinear balanced Boolean functions with a good correlation-immunity, Lecture Notes in Computer Science, 1403 (1998), 475-488.  doi: 10.1007/BFb0054147. [7] C. Fontaine, On some cosets of the first-order Reed-Muller code with high minimum weight, IEEE Transactions on Information Theory, 45 (1999), 1237-1243.  doi: 10.1109/18.761276. [8] X.-D. Hou, On the norm and covering radius of first-order Reed-Muller codes, IEEE Transactions on Information Theory, 43 (1997), 1025-1027.  doi: 10.1109/18.568715. [9] S. Kavut, Results on rotation-symmetric S-boxes, Information Sciences, 201 (2012), 93-113.  doi: 10.1016/j.ins.2012.02.030. [10] S. Kavut and Sevdenur Baloǧlu, Results on symmetric S-boxes constructed by concatenation of RSSBs, Cryptography and Communications, 11 (2019), 641–660, http://dx.doi.org/10.1007/s12095-018-0318-1. doi: 10.1007/s12095-018-0318-1. [11] S. Kavut, S. Maitra, S. Sarkar and M. D. Yücel, Enumeration of 9-variable rotation symmetric Boolean functions having nonlinearity $>240$, Lecture Notes in Computer Science, 4329 (2006), 266-279.  doi: 10.1007/11941378_19. [12] S. Kavut, S. Maitra and M. D. Yücel, Search for Boolean functions with excellent profiles in the rotation symmetric class, IEEE Transactions on Information Theory, 53 (2007), 1743-1751.  doi: 10.1109/TIT.2007.894696. [13] S. Kavut and M. D. Yücel, 9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class, Information and Computation, 208 (2010), 341-350.  doi: 10.1016/j.ic.2009.12.002. [14] S. Maitra, Balanced Boolean function on 13-variables having nonlinearity strictly greater than the bent concatenation bound, Boolean Functions in Cryptology and Information Security, 173–182, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., 18, IOS, Amsterdam, 2008. Available from: https://eprint.iacr.org/2007/309.pdf. [15] S. Maitra, S. Kavut and M. D. Yücel, Balanced Boolean function on 13-variables having nonlinearity greater than the bent concatenation bound, Proceedings of Boolean Functions: Cryptography and Applications, (2008), 109–118. [16] M. Matsui, Linear cryptanalysis method for DES cipher, Lecture Notes in Computer Science, 765 (1993), 386-397.  doi: 10.1007/3-540-48285-7_33. [17] K. Nyberg, Differentially uniform mappings for cryptography, Lecture Notes in Computer Science, 765 (1994), 55-64.  doi: 10.1007/3-540-48285-7_6. [18] N. J. Patterson and D. H. Wiedemann, The covering radius of the $(2^15, 16)$ Reed-Muller code is at least 16276, IEEE Transactions on Information Theory, 29 (1983), 354-356.  doi: 10.1109/TIT.1983.1056679. [19] V. Rijmen, P. S. L. M. Barreto and D. L. Gazzoni Filho, Rotation symmetry in algebraically generated cryptographic substitution tables, Information Processing Letters, 106 (2008), 246-250.  doi: 10.1016/j.ipl.2007.09.012. [20] S. Sarkar and S. Maitra, Idempotents in the neighbourhood of Patterson-Wiedemann functions having Walsh spectra zeros, Designs, Codes and Cryptography, 49 (2008), 95-103.  doi: 10.1007/s10623-008-9181-y. [21] P. Stǎnicǎ and S. Maitra, Rotation symmetric Boolean functions - count and cryptographic properties, Discrete Applied Mathematics, 156 (2008), 1567-1580.  doi: 10.1016/j.dam.2007.04.029. [22] P. Stǎnicǎ, S. Maitra and J. Clark, Results on rotation symmetric bent and correlation immune Boolean functions, Fast Software Encryption Workshop - FSE 2004, Lecture Notes in Computer Science, 3017 (2004), 161-177.

Tables(2)