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

SelÇuk Kavut; Seher Tutdere

doi:10.3934/amc.2020010

Article Contents

2020, Volume 14, Issue 1: 127-136. Doi: 10.3934/amc.2020010

This issue Previous Article A note on the fast algebraic immunity and its consequences on modified majority functions Next Article Certified lattice reduction

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

SelÇuk Kavut^1, , and
Seher Tutdere^2,

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
^*Corresponding author: Selçuk Kavut

Received: November 2018

Published: August 2019

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

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 11T71, 94A60.

Citation:

Full Text(HTML)

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} $)	240	992	4032	16256
Upper bound	244	1000	4050	16292
($ 2\left\lfloor 2^{n-2}-2^{\frac{n}{2}-2}\right\rfloor $)	244	1000	4050	16292
Unbalanced nonlinearities
[18]	$ - $	$ - $	$ - $	16276
[13]	242	996	4040	$ - $
Balanced nonlinearities
[15]	$ - $	$ - $	4036	$ - $
[20]	$ - $	$ - $	$ - $	16272

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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. 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.