A new construction of odd-variable rotation symmetric boolean functions with good cryptographic properties

Bingxin Wang; Sihong Su

doi:10.3934/amc.2020115

Article Contents

2022, Volume 16, Issue 2: 365-382. Doi: 10.3934/amc.2020115

This issue Previous Article Constructions of linear codes with small hulls from association schemes Next Article Optimal strategies for CSIDH

A new construction of odd-variable rotation symmetric boolean functions with good cryptographic properties

Bingxin Wang and
Sihong Su^,

School of Mathematics and Statistics, Henan University, Kaifeng, 475004, China

^*Corresponding author: Sihong Su (E-mail: sush@henu.edu.cn)
^*Corresponding author: Sihong Su (E-mail: sush@henu.edu.cn)

Received: March 31, 2020

Revised: August 31, 2020

Published: May 2022

The second author is supported by the National Natural Science Foundation of China (Grant No. 61502147)

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

Abstract

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.

Keywords:

Mathematics Subject Classification: 06E30, 94D10.

Citation:

Full Text(HTML)

Table 1. The nonlinearities of the rotation symmetric Boolean functions

function	nonlinearity
[14]	$ {2^{n-1}-{n-1\choose k}}+2 $
[17]	$ 2^{n-1}-{n-1\choose k}+2^k-2 $
[11]	$ 2^{n-1}-{n-1\choose k}+2^k+2^{k-2}-k $
[21]	$ 2^{n-1}-{n-1\choose k}+2^k+2^{k-1}-2k $
[20]	$ 2^{n-1}-{n-1\choose k}+(k-5)2^{k-1}+2k+2 $
[6]	$ 2^{n-1}-{n-1\choose k}+\sum_{h=3}^k(n-2h)\|T_h\|+L_k $

| Show Table

DownLoad: CSV

Table 2. The entries of the vectors in $ T $ for $ n = 13 $

	$ \alpha_1 $	$ \alpha_2 $	$ \alpha_3 $	$ \alpha_4 $	$ \alpha_5 $	$ \alpha_6 $	$ \alpha_7 $	$ \alpha_8 $	$ \alpha_9 $	$ \alpha_{10} $	$ \alpha_{11} $	$ \alpha_{12} $	$ \alpha_{13} $
$ 0 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $
$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $
$ 2 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $
$ 3 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 1 $
$ 4 $	$ 1 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 1 $	$ 0 $	$ 1 $	$ 0 $	$ 1 $	$ 1 $	$ 0 $
$ 5 $	$ 0 $	$ 0 $	$ 0 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 0 $	$ 1 $	$ 0 $	$ 0 $	$ 0 $
$ 6 $	$ 0 $	$ 1 $	$ 1 $	$ 0 $	$ 1 $	$ 1 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 1 $	$ 1 $
$ 7 $	$ 1 $	$ 1 $	$ 0 $	$ 0 $	$ 1 $	$ 0 $	$ 0 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 0 $	$ 0 $
$ 8 $	$ 0 $	$ 0 $	$ 1 $	$ 1 $	$ 0 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $
$ 9 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 1 $	$ 1 $	$ 1 $	$ 1 $
$ 10 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $
$ 11 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $
$ 12 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $	$ 0 $

| Show Table

DownLoad: CSV

Table 3. Comparison of the nonlinearities

$ n $	$ 9 $	11	13	15	17	19	21
$ F(x) $	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
$ f $ in (13)	188	782	3208	13064	52988	214406	866160

| Show Table

DownLoad: CSV

Table 4. Comparison of the nonlinearities

$ n $	27	37	47	57
$ F(x) $	56708264	59644341436	62135313450064	64408903437167496
[17]	56716454	59644603578	62135321838670	64408903705602950
[21]	56720526	59644734616	62135326032930	64408903839820624
[20]	56741060	59646045410	62135388947584	64408906524175298
[6]	56748298	59648002864	62135605652036	64408924613659456
$ f $ in (13)	56747394	59647951550	62135614817362	64408926590774154

| Show Table

DownLoad: CSV

Table 5. Comparison of the nonlinearity biases

$ n $	9	11	13	15	17	19	21	27	37	47	57
$ F(x) $	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
$ f $ in (13)	0.266	0.236	0.217	0.203	0.1915	0.1821	0.1740	0.15440	0.132008	0.11699981	0.10614658

| Show Table

DownLoad: CSV

Table 6. Comparison of the fast algebraic immunities

$ n $	$ 9 $	11	13	15
[3]	8	10	12	14
[21]	$ - $	10	12	14
[20]	$ - $	10	12	13
[6]	$ - $	10	12	14
$ f $ in (13)	6	8	10	10

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.