-
Previous Article
Optimal strategies for CSIDH
- AMC Home
- This Issue
-
Next Article
Constructions of linear codes with small hulls from association schemes
A new construction of odd-variable rotation symmetric boolean functions with good cryptographic properties
School of Mathematics and Statistics, Henan University, Kaifeng, 475004, China |
Rotation symmetric Boolean functions constitute a class of cryptographically significant Boolean functions. In this paper, based on the theory of ordered integer partitions, we present a new class of odd-variable rotation symmetric Boolean functions with optimal algebraic immunity by modifying the support of the majority function. Compared with the existing rotation symmetric Boolean functions on odd variables, the newly constructed functions have the highest nonlinearity.
References:
[1] |
A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight 4 and 5, in Advances in Cryptology-EUROCRYPT 2000 (eds. B. Preneel), Springer, Berlin, Heidelberg, 2000,573–588.
doi: 10.1007/3-540-45539-6. |
[2] |
C. Carlet, Boolean functions for cryptography and error correcting codes, to appear in Cambridge University Press.
doi: 10.1017/CBO9780511780448.011. |
[3] |
C. Carlet and K. Feng, An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, in ASIACRYPT 2008 (eds. J. Pieprzyk), Lecture Notes in Computer Science, 5350, Springer, Heidelberg, 2008,425–440.
doi: 10.1007/978-3-540-89255-7_26. |
[4] |
C. Carlet, G. Gao and W. Liu,
A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions, J. Combin. Theory Ser. A, 127 (2014), 161-175.
doi: 10.1016/j.jcta.2014.05.008. |
[5] |
C. Carlet, X. Zeng, C. Li and L. Hu,
Further properties of several classes of Boolean functions with optimum algebraic immunity, Des. Codes Cryptogr., 52 (2009), 303-338.
doi: 10.1007/s10623-009-9284-0. |
[6] |
Y. Chen, F. Guo and J. Ruan,
Constructing odd-variables RSBFs with optimal algebraic immunity, good nonlieanrity and good behavior against fast algebraic attarcks, Discrete Appl. Math., 262 (2019), 1-12.
doi: 10.1016/j.dam.2019.02.041. |
[7] |
N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in EUROCRYPT 2003, Lecture Notes in Computer Science, 2656, Springer-Verlag, Heidelberg, 2003,345–359.
doi: 10.1007/3-540-39200-9_21. |
[8] |
D. Dalai, S. Maitra and S. Sarkar,
Basic theory in construction of Boolean functions with maximum possible annihilator immunity, Des. Codes Cryptogr., 40 (2006), 41-58.
doi: 10.1007/s10623-005-6300-x. |
[9] |
C. Ding, G. Xiao and W. Shan, The stability theory of stream ciphers, in Lecture Notes in Computer Science, 561, Springer-Verlag, Berlin, 1991.
doi: 10.1007/3-540-54973-0. |
[10] |
J. Du, Q. Wen, J. Zhang and S. Pang,
Constructions of resilient rotation symmetric Boolean functions on given number of variables, IET Inform. Secur., 8 (2014), 265-272.
doi: 10.1049/iet-ifs.2013.0090. |
[11] |
S. Fu, J. Du, L. Qu and C. Li,
Construction of odd-variable rotation symmetric boolean functions with maximum algebraic immunity, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 99 (2016), 853-855.
doi: 10.1016/j.dam.2016.06.005. |
[12] |
G. Gao,
Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Trans. Inform. Theory, 58 (2012), 4908-4913.
doi: 10.1109/TIT.2012.2193377. |
[13] |
W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in Advances in Cryptology-EUROCRYPT 2004, Lecture Notes in Computer Science, 3027, Springer Heidelberg, 2004,474–491.
doi: 10.1007/978-3-540-24676-3_28. |
[14] |
S. Sarkar and S. Maitra, Construction of rotation symmetric Boolean functions with maximum algebraic immunity on odd number of variables, in AAECC 2007, Lecture Notes in Computer Science, 4851, 2007,271–280.
doi: 10.1007/978-3-540-77224-8_32. |
[15] |
P. Stnic and S. Maitra,
Rotation symmetric Boolean functions-count and cryptographic properties, Discrete Appl. Math., 156 (2002), 1567-1580.
doi: 10.1016/j.dam.2007.04.029. |
[16] |
S. Su,
A new construction of rotation symmetric bent functions with maximal algebraic degree, Adv. Math. Commun., 13 (2019), 253-265.
doi: 10.3934/amc.2019017. |
[17] |
S. Su and X. Tang,
Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity, Des. Codes Cryptogr., 71 (2014), 183-199.
doi: 10.1007/s10623-012-9727-x. |
[18] |
S. Su and X. Tang,
Systematic constructions of rotation symmetric bent functions, 2-rotation symmetric bent functions, and bent idempotent functions, IEEE Trans. Inf. Theory, 63 (2017), 4658-4667.
doi: 10.1109/TIT.2016.2621751. |
[19] |
L. Sun, F. Fu and X. Guang,
Two classes of 1-resilient prime-variable rotation symmetric Boolean functions, IEICE Trans Fund. Electron. Comm. Comput. Sci., E100-A (2017), 902-907.
doi: 10.1587/transfun.E100.A.902. |
[20] |
H. Zhang and S. Su,
A new construction of rotation symmetric Boolean functions with optimal algebraic immunity and higher nonlinearity, Discrete Appl. Math., 262 (2019), 13-28.
doi: 10.1016/j.dam.2019.02.030. |
[21] |
Q. Zhao, G. Han, D. Zheng and X. Li,
Constructing odd-variable rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity, Chinese J. Electron., 28 (2019), 45-51.
doi: 10.1007/s12190-019-01245-2. |
show all references
References:
[1] |
A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight 4 and 5, in Advances in Cryptology-EUROCRYPT 2000 (eds. B. Preneel), Springer, Berlin, Heidelberg, 2000,573–588.
doi: 10.1007/3-540-45539-6. |
[2] |
C. Carlet, Boolean functions for cryptography and error correcting codes, to appear in Cambridge University Press.
doi: 10.1017/CBO9780511780448.011. |
[3] |
C. Carlet and K. Feng, An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, in ASIACRYPT 2008 (eds. J. Pieprzyk), Lecture Notes in Computer Science, 5350, Springer, Heidelberg, 2008,425–440.
doi: 10.1007/978-3-540-89255-7_26. |
[4] |
C. Carlet, G. Gao and W. Liu,
A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions, J. Combin. Theory Ser. A, 127 (2014), 161-175.
doi: 10.1016/j.jcta.2014.05.008. |
[5] |
C. Carlet, X. Zeng, C. Li and L. Hu,
Further properties of several classes of Boolean functions with optimum algebraic immunity, Des. Codes Cryptogr., 52 (2009), 303-338.
doi: 10.1007/s10623-009-9284-0. |
[6] |
Y. Chen, F. Guo and J. Ruan,
Constructing odd-variables RSBFs with optimal algebraic immunity, good nonlieanrity and good behavior against fast algebraic attarcks, Discrete Appl. Math., 262 (2019), 1-12.
doi: 10.1016/j.dam.2019.02.041. |
[7] |
N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in EUROCRYPT 2003, Lecture Notes in Computer Science, 2656, Springer-Verlag, Heidelberg, 2003,345–359.
doi: 10.1007/3-540-39200-9_21. |
[8] |
D. Dalai, S. Maitra and S. Sarkar,
Basic theory in construction of Boolean functions with maximum possible annihilator immunity, Des. Codes Cryptogr., 40 (2006), 41-58.
doi: 10.1007/s10623-005-6300-x. |
[9] |
C. Ding, G. Xiao and W. Shan, The stability theory of stream ciphers, in Lecture Notes in Computer Science, 561, Springer-Verlag, Berlin, 1991.
doi: 10.1007/3-540-54973-0. |
[10] |
J. Du, Q. Wen, J. Zhang and S. Pang,
Constructions of resilient rotation symmetric Boolean functions on given number of variables, IET Inform. Secur., 8 (2014), 265-272.
doi: 10.1049/iet-ifs.2013.0090. |
[11] |
S. Fu, J. Du, L. Qu and C. Li,
Construction of odd-variable rotation symmetric boolean functions with maximum algebraic immunity, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 99 (2016), 853-855.
doi: 10.1016/j.dam.2016.06.005. |
[12] |
G. Gao,
Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Trans. Inform. Theory, 58 (2012), 4908-4913.
doi: 10.1109/TIT.2012.2193377. |
[13] |
W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in Advances in Cryptology-EUROCRYPT 2004, Lecture Notes in Computer Science, 3027, Springer Heidelberg, 2004,474–491.
doi: 10.1007/978-3-540-24676-3_28. |
[14] |
S. Sarkar and S. Maitra, Construction of rotation symmetric Boolean functions with maximum algebraic immunity on odd number of variables, in AAECC 2007, Lecture Notes in Computer Science, 4851, 2007,271–280.
doi: 10.1007/978-3-540-77224-8_32. |
[15] |
P. Stnic and S. Maitra,
Rotation symmetric Boolean functions-count and cryptographic properties, Discrete Appl. Math., 156 (2002), 1567-1580.
doi: 10.1016/j.dam.2007.04.029. |
[16] |
S. Su,
A new construction of rotation symmetric bent functions with maximal algebraic degree, Adv. Math. Commun., 13 (2019), 253-265.
doi: 10.3934/amc.2019017. |
[17] |
S. Su and X. Tang,
Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity, Des. Codes Cryptogr., 71 (2014), 183-199.
doi: 10.1007/s10623-012-9727-x. |
[18] |
S. Su and X. Tang,
Systematic constructions of rotation symmetric bent functions, 2-rotation symmetric bent functions, and bent idempotent functions, IEEE Trans. Inf. Theory, 63 (2017), 4658-4667.
doi: 10.1109/TIT.2016.2621751. |
[19] |
L. Sun, F. Fu and X. Guang,
Two classes of 1-resilient prime-variable rotation symmetric Boolean functions, IEICE Trans Fund. Electron. Comm. Comput. Sci., E100-A (2017), 902-907.
doi: 10.1587/transfun.E100.A.902. |
[20] |
H. Zhang and S. Su,
A new construction of rotation symmetric Boolean functions with optimal algebraic immunity and higher nonlinearity, Discrete Appl. Math., 262 (2019), 13-28.
doi: 10.1016/j.dam.2019.02.030. |
[21] |
Q. Zhao, G. Han, D. Zheng and X. Li,
Constructing odd-variable rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity, Chinese J. Electron., 28 (2019), 45-51.
doi: 10.1007/s12190-019-01245-2. |
11 | 13 | 15 | 17 | 19 | 21 | ||
186 | 772 | 3172 | 12952 | 52666 | 213524 | 863820 | |
[3] | 232 | 980 | 3988 | 16212 | 65210 | 261428 | 1046552 |
[17] | 802 | 3234 | 13078 | 52920 | 214034 | 864842 | |
[21] | 810 | 3256 | 13130 | 53034 | 214274 | 865336 | |
[20] | 784 | 3218 | 13096 | 53068 | 214568 | 866402 | |
[6] | 794 | 3230 | 13098 | 53044 | 214486 | 866294 | |
188 | 782 | 3208 | 13064 | 52988 | 214406 | 866160 |
11 | 13 | 15 | 17 | 19 | 21 | ||
186 | 772 | 3172 | 12952 | 52666 | 213524 | 863820 | |
[3] | 232 | 980 | 3988 | 16212 | 65210 | 261428 | 1046552 |
[17] | 802 | 3234 | 13078 | 52920 | 214034 | 864842 | |
[21] | 810 | 3256 | 13130 | 53034 | 214274 | 865336 | |
[20] | 784 | 3218 | 13096 | 53068 | 214568 | 866402 | |
[6] | 794 | 3230 | 13098 | 53044 | 214486 | 866294 | |
188 | 782 | 3208 | 13064 | 52988 | 214406 | 866160 |
27 | 37 | 47 | 57 | |
56708264 | 59644341436 | 62135313450064 | 64408903437167496 | |
[17] | 56716454 | 59644603578 | 62135321838670 | 64408903705602950 |
[21] | 56720526 | 59644734616 | 62135326032930 | 64408903839820624 |
[20] | 56741060 | 59646045410 | 62135388947584 | 64408906524175298 |
[6] | 56748298 | 59648002864 | 62135605652036 | 64408924613659456 |
56747394 | 59647951550 | 62135614817362 | 64408926590774154 |
27 | 37 | 47 | 57 | |
56708264 | 59644341436 | 62135313450064 | 64408903437167496 | |
[17] | 56716454 | 59644603578 | 62135321838670 | 64408903705602950 |
[21] | 56720526 | 59644734616 | 62135326032930 | 64408903839820624 |
[20] | 56741060 | 59646045410 | 62135388947584 | 64408906524175298 |
[6] | 56748298 | 59648002864 | 62135605652036 | 64408924613659456 |
56747394 | 59647951550 | 62135614817362 | 64408926590774154 |
9 | 11 | 13 | 15 | 17 | 19 | 21 | 27 | 37 | 47 | 57 | |
0.273 | 0.246 | 0.226 | 0.209 | 0.1964 | 0.1855 | 0.1762 | 0.15498 | 0.132061 | 0.11700409 | 0.10614691 | |
[3] | 0.094 | 0.043 | 0.026 | 0.010 | 0.0050 | 0.0027 | 0.0019 | ||||
[17] | 0.217 | 0.210 | 0.202 | 0.1925 | 0.1835 | 0.1752 | 0.15486 | 0.132057 | 0.11700397 | 0.10614690 | |
[21] | 0.209 | 0.205 | 0.199 | 0.1908 | 0.1826 | 0.1748 | 0.15480 | 0.132055 | 0.11700391 | 0.10614690 | |
[20] | 0.234 | 0.214 | 0.201 | 0.1902 | 0.1815 | 0.1737 | 0.15449 | 0.132036 | 0.11700302 | 0.10614686 | |
[6] | 0.224 | 0.211 | 0.201 | 0.1906 | 0.1818 | 0.1738 | 0.15438 | 0.132007 | 0.11699994 | 0.10614661 | |
0.266 | 0.236 | 0.217 | 0.203 | 0.1915 | 0.1821 | 0.1740 | 0.15440 | 0.132008 | 0.11699981 | 0.10614658 |
9 | 11 | 13 | 15 | 17 | 19 | 21 | 27 | 37 | 47 | 57 | |
0.273 | 0.246 | 0.226 | 0.209 | 0.1964 | 0.1855 | 0.1762 | 0.15498 | 0.132061 | 0.11700409 | 0.10614691 | |
[3] | 0.094 | 0.043 | 0.026 | 0.010 | 0.0050 | 0.0027 | 0.0019 | ||||
[17] | 0.217 | 0.210 | 0.202 | 0.1925 | 0.1835 | 0.1752 | 0.15486 | 0.132057 | 0.11700397 | 0.10614690 | |
[21] | 0.209 | 0.205 | 0.199 | 0.1908 | 0.1826 | 0.1748 | 0.15480 | 0.132055 | 0.11700391 | 0.10614690 | |
[20] | 0.234 | 0.214 | 0.201 | 0.1902 | 0.1815 | 0.1737 | 0.15449 | 0.132036 | 0.11700302 | 0.10614686 | |
[6] | 0.224 | 0.211 | 0.201 | 0.1906 | 0.1818 | 0.1738 | 0.15438 | 0.132007 | 0.11699994 | 0.10614661 | |
0.266 | 0.236 | 0.217 | 0.203 | 0.1915 | 0.1821 | 0.1740 | 0.15440 | 0.132008 | 0.11699981 | 0.10614658 |
[1] |
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 |
[2] |
Thomas W. Cusick, Younhwan Cheon. The weight recursions for the 2-rotation symmetric quartic Boolean functions. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021011 |
[3] |
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 |
[4] |
Sihong Su. A new construction of rotation symmetric bent functions with maximal algebraic degree. Advances in Mathematics of Communications, 2019, 13 (2) : 253-265. doi: 10.3934/amc.2019017 |
[5] |
Tingting Pang, Nian Li, Li Zhang, Xiangyong Zeng. Several new classes of (balanced) Boolean functions with few Walsh transform values. Advances in Mathematics of Communications, 2021, 15 (4) : 757-775. doi: 10.3934/amc.2020095 |
[6] |
Deng Tang. A note on the fast algebraic immunity and its consequences on modified majority functions. Advances in Mathematics of Communications, 2020, 14 (1) : 111-125. doi: 10.3934/amc.2020009 |
[7] |
Junchao Zhou, Nian Li, Xiangyong Zeng, Yunge Xu. A generic construction of rotation symmetric bent functions. Advances in Mathematics of Communications, 2021, 15 (4) : 721-736. doi: 10.3934/amc.2020092 |
[8] |
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 |
[9] |
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 |
[10] |
Wenying Zhang, Zhaohui Xing, Keqin Feng. A construction of bent functions with optimal algebraic degree and large symmetric group. Advances in Mathematics of Communications, 2020, 14 (1) : 23-33. doi: 10.3934/amc.2020003 |
[11] |
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 |
[12] |
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 |
[13] |
Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038 |
[14] |
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 |
[15] |
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 |
[16] |
Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022013 |
[17] |
Yvjing Yang, Yang Liu, Jungang Lou, Zhen Wang. Observability of switched Boolean control networks using algebraic forms. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1519-1533. doi: 10.3934/dcdss.2020373 |
[18] |
Pieter C. Allaart. An algebraic approach to entropy plateaus in non-integer base expansions. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6507-6522. doi: 10.3934/dcds.2019282 |
[19] |
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 |
[20] |
Rui Zhang, Sihong Su. A new construction of weightwise perfectly balanced Boolean functions. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021020 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]