# American Institute of Mathematical Sciences

doi: 10.3934/amc.2020115

## A New Construction of odd-variable Rotation symmetric Boolean functions with good cryptographic properties

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

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

Received  April 2020 Revised  August 2020 Published  October 2020

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

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.

Citation: Bingxin Wang, Sihong Su. A New Construction of odd-variable Rotation symmetric Boolean functions with good cryptographic properties. Advances in Mathematics of Communications, doi: 10.3934/amc.2020115
##### References:

show all references

##### References:
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$
 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$
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$
 $\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$
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
 $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
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
 $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
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.01 0.005 0.0027 0.0019 $-$ $-$ $-$ $-$ [17] $-$ 0.217 0.21 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.174 0.15440 0.132008 0.11699981 0.10614658
 $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.01 0.005 0.0027 0.0019 $-$ $-$ $-$ $-$ [17] $-$ 0.217 0.21 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.174 0.15440 0.132008 0.11699981 0.10614658
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
 $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
 [1] Ville Salo, Ilkka Törmä. Recoding Lie algebraic subshifts. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 1005-1021. doi: 10.3934/dcds.2020307 [2] Evan Greif, Daniel Kaplan, Robert S. Strichartz, Samuel C. Wiese. Spectrum of the Laplacian on regular polyhedra. Communications on Pure & Applied Analysis, 2021, 20 (1) : 193-214. doi: 10.3934/cpaa.2020263 [3] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [4] Stefan Ruschel, Serhiy Yanchuk. The spectrum of delay differential equations with multiple hierarchical large delays. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 151-175. doi: 10.3934/dcdss.2020321 [5] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [6] Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098 [7] Teresa D'Aprile. Bubbling solutions for the Liouville equation around a quantized singularity in symmetric domains. Communications on Pure & Applied Analysis, 2021, 20 (1) : 159-191. doi: 10.3934/cpaa.2020262 [8] Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115 [9] Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $(n, m)$-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117 [10] Shao-Xia Qiao, Li-Jun Du. Propagation dynamics of nonlocal dispersal equations with inhomogeneous bistable nonlinearity. Electronic Research Archive, , () : -. doi: 10.3934/era.2020116 [11] Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015 [12] Xinyu Mei, Yangmin Xiong, Chunyou Sun. Pullback attractor for a weakly damped wave equation with sup-cubic nonlinearity. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 569-600. doi: 10.3934/dcds.2020270 [13] Tahir Aliyev Azeroğlu, Bülent Nafi Örnek, Timur Düzenli. Some results on the behaviour of transfer functions at the right half plane. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020106 [14] Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243 [15] Lei Liu, Li Wu. Multiplicity of closed characteristics on $P$-symmetric compact convex hypersurfaces in $\mathbb{R}^{2n}$. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378 [16] Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 215-242. doi: 10.3934/cpaa.2020264

2019 Impact Factor: 0.734

## Tools

Article outline

Figures and Tables