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.

[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. BrowningJ. F. DillonM. 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. KavutS. MaitraS. 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. KavutS. 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. RijmenP. 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. 

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.

[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. BrowningJ. F. DillonM. 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. KavutS. MaitraS. 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. KavutS. 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. RijmenP. 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. 

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
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]
$ \# $ Representative
permutation
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
$ \# $ Representative
permutation
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]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136

[3]

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

[4]

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

[5]

Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056

[6]

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

[7]

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069

[13]

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

[14]

Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022013

[15]

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

[16]

Rui Zhang, Sihong Su. A new construction of weightwise perfectly balanced Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021020

[17]

Claude Carlet. Expressing the minimum distance, weight distribution and covering radius of codes by means of the algebraic and numerical normal forms of their indicators. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022047

[18]

Shengyang Jia, Lei Deng, Quanwu Zhao, Yunkai Chen. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021225

[19]

Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. Upper bounds on the length function for covering codes with covering radius $ R $ and codimension $ tR+1 $. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021074

[20]

Claude Carlet, Serge Feukoua. Three parameters of Boolean functions related to their constancy on affine spaces. Advances in Mathematics of Communications, 2020, 14 (4) : 651-676. doi: 10.3934/amc.2020036

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (765)
  • HTML views (375)
  • Cited by (0)

Other articles
by authors

[Back to Top]