-
Previous Article
Certified lattice reduction
- AMC Home
- This Issue
-
Next Article
A note on the fast algebraic immunity and its consequences on modified majority functions
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 |
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.
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, 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. 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, Lecture Notes in Computer Science, 3017 (2004), 161-177.
|
Number of variables ( |
9 | 11 | 13 | 15 |
Bounds | ||||
Bent concatenation bound | 240 | 992 | 4032 | 16256 |
( |
||||
Upper bound | 244 | 1000 | 4050 | 16292 |
( |
||||
Unbalanced nonlinearities | ||||
[18] | 16276 | |||
[13] | 242 | 996 | 4040 | |
Balanced nonlinearities | ||||
[15] | 4036 | |||
[20] | 16272 |
Number of variables ( |
9 | 11 | 13 | 15 |
Bounds | ||||
Bent concatenation bound | 240 | 992 | 4032 | 16256 |
( |
||||
Upper bound | 244 | 1000 | 4050 | 16292 |
( |
||||
Unbalanced nonlinearities | ||||
[18] | 16276 | |||
[13] | 242 | 996 | 4040 | |
Balanced nonlinearities | ||||
[15] | 4036 | |||
[20] | 16272 |
Representative permutation |
Space size |
Best result (for involution S-boxes) |
Best result | |
1 | ||||
2 | ||||
3 | ||||
4 | ||||
5 | ||||
6 | ||||
7 | ||||
8 | ||||
9 | ||||
10 | ||||
11 | ||||
12 | ||||
13 | ||||
14 | ||||
15 | ||||
16 | ||||
17 | ||||
18 | ||||
19 | ||||
20 | ||||
21 | ||||
22 | ||||
Representative permutation |
Space size |
Best result (for involution S-boxes) |
Best result | |
1 | ||||
2 | ||||
3 | ||||
4 | ||||
5 | ||||
6 | ||||
7 | ||||
8 | ||||
9 | ||||
10 | ||||
11 | ||||
12 | ||||
13 | ||||
14 | ||||
15 | ||||
16 | ||||
17 | ||||
18 | ||||
19 | ||||
20 | ||||
21 | ||||
22 | ||||
[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] |
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 |
[18] |
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 |
[19] |
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 |
[20] |
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 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]