# American Institute of Mathematical Sciences

February  2020, 14(1): 127-136. doi: 10.3934/amc.2020010

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

 1 Department of Computer Engineering, Faculty of Engineering, Balıkesir University, 10145 Balıkesir, Turkey 2 Department of Mathematics, Faculty of Arts and Science, Balıkesir University, 10145 Balıkesir, Turkey

*Corresponding author: Selçuk Kavut

Received  November 2018 Published  August 2019

Fund Project: 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.

Citation: SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010
##### References:
 [1] M. Bartholomew-Biggs, Chapter 5: The steepest descent method, in Nonlinear Optimization with Financial Applications. Springer US, (2005), 51–64.  Google Scholar [2] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [9] S. Kavut, Results on rotation-symmetric S-boxes, Information Sciences, 201 (2012), 93-113.  doi: 10.1016/j.ins.2012.02.030.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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. Google Scholar [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. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [22] P. Stǎnicǎ, S. Maitra and J. Clark, Results on rotation symmetric bent and correlation immune Boolean functions, Lecture Notes in Computer Science, 3017 (2004), 161-177.   Google Scholar

show all references

##### References:
 [1] M. Bartholomew-Biggs, Chapter 5: The steepest descent method, in Nonlinear Optimization with Financial Applications. Springer US, (2005), 51–64.  Google Scholar [2] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [9] S. Kavut, Results on rotation-symmetric S-boxes, Information Sciences, 201 (2012), 93-113.  doi: 10.1016/j.ins.2012.02.030.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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. Google Scholar [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. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [22] P. Stǎnicǎ, S. Maitra and J. Clark, Results on rotation symmetric bent and correlation immune Boolean functions, Lecture Notes in Computer Science, 3017 (2004), 161-177.   Google Scholar
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
 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
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
 $\#$ 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] Pascale Charpin, Jie Peng. Differential uniformity and the associated codes of cryptographic functions. Advances in Mathematics of Communications, 2019, 13 (4) : 579-600. doi: 10.3934/amc.2019036 [2] Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129 [3] Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201 [4] Sugata Gangopadhyay, Constanza Riera, Pantelimon Stăniă. Gowers $U_2$ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020056 [5] Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025 [6] Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038 [7] Claude Carlet, Serge Feukoua. Three basic questions on Boolean functions. Advances in Mathematics of Communications, 2017, 11 (4) : 837-855. doi: 10.3934/amc.2017061 [8] Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031 [9] Axel Kohnert, Johannes Zwanzger. New linear codes with prescribed group of automorphisms found by heuristic search. Advances in Mathematics of Communications, 2009, 3 (2) : 157-166. doi: 10.3934/amc.2009.3.157 [10] Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399 [11] Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83 [12] Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048 [13] Yu Zhou. On the distribution of auto-correlation value of balanced Boolean functions. Advances in Mathematics of Communications, 2013, 7 (3) : 335-347. doi: 10.3934/amc.2013.7.335 [14] Claude Carlet, Serge Feukoua. Three parameters of Boolean functions related to their constancy on affine spaces. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020036 [15] Yang Yang, Xiaohu Tang, Guang Gong. Even periodic and odd periodic complementary sequence pairs from generalized Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 113-125. doi: 10.3934/amc.2013.7.113 [16] Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197 [17] Daria Bugajewska, Mirosława Zima. On the spectral radius of linearly bounded operators and existence results for functional-differential equations. Conference Publications, 2003, 2003 (Special) : 147-155. doi: 10.3934/proc.2003.2003.147 [18] Volodymyr Pichkur. On practical stability of differential inclusions using Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (5) : 1977-1986. doi: 10.3934/dcdsb.2017116 [19] Pierre Magal. Global stability for differential equations with homogeneous nonlinearity and application to population dynamics. Discrete & Continuous Dynamical Systems - B, 2002, 2 (4) : 541-560. doi: 10.3934/dcdsb.2002.2.541 [20] Yi Ming Zou. Dynamics of boolean networks. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1629-1640. doi: 10.3934/dcdss.2011.4.1629

2018 Impact Factor: 0.879

## Tools

Article outline

Figures and Tables