Article Contents
Article Contents

# The weight recursions for the 2-rotation symmetric quartic Boolean functions

• A Boolean function in $n$ variables is 2-rotation symmetric if it is invariant under even powers of $\rho(x_1, \ldots, x_n) = (x_2, \ldots, x_n, x_1)$, but not under the first power (ordinary rotation symmetry); we call such a function a 2-function. A 2-function is called monomial rotation symmetric (MRS) if it is generated by applying powers of $\rho^2$ to a single monomial. If the quartic MRS 2-function in $2n$ variables has a monomial $x_1 x_q x_r x_s$, then we use the notation ${2-}(1,q,r,s)_{2n}$ for the function. A detailed theory of equivalence of quartic MRS 2-functions in $2n$ variables was given in a $2020$ paper by Cusick, Cheon and Dougan. This theory divides naturally into two classes, called $mf1$ and $mf2$ in the paper. After describing the equivalence classes, the second major problem is giving details of the linear recursions that the Hamming weights for any sequence of functions ${2-}(1,q,r,s)_{2n}$ (with $q < r < s,$ say), $n = s, s+1, \ldots$ can be shown to satisfy. This problem was solved for the $mf1$ case only in the $2020$ paper. Using new ideas about "short" functions, Cusick and Cheon found formulas for the $mf2$ weights in a $2021$ sequel to the $2020$ paper. In this paper the actual recursions for the weights in the $mf2$ case are determined.

Mathematics Subject Classification: 94C10 94A60 06E30.

 Citation:

• Table 1.  The recursion polynomial for $f$ corresponding to some $\mu$ values

 $\mu$ $p(x)$ $2$ $x^3-4x^2-8x+32=(x-4)(x^2-8)$ $4$ $x^5-4x^4-64x+256=(x-4)(x^4-64)$ $6$ $x^7-4x^6-512x+2048=(x-4)(x^6-512)$ $8$ $x^9-4x^8-4096x+16384=(x-4)(x^8-4096)$ $t-1$($t$ is odd) $x^t -4x^{t-1} -2^{(3t-3)/2}x + 2^{(3t+1)/2}= (x-4)(x^{t-1}-2^{(3t-3)/2})$

Table 2.  List of $\chi:F_\chi(x)$

 $\chi$ $F_\chi(x)$ 2 $(x-4)(x^2-2x-6)$ 4 $(x-4)(x^2-2x-6)(x^2+6)$ 6 $(x-4)(x^2-2x-6)(x^6+12x^3-216)$ 8 $(x-4)(x^2-2x-6)(x^2+6)(x^2-6)(x^8+96x^4+1296)$ 10 $(x-4)(x^2-2x-6)(x^{10}-72x^5-7776)(x^{10}+264x^5-7776)$ 12 $(x-4)(x^2-2x-6)(x^2+6)(x^4-6x^2+36)(x^6-12x^3-216)$ $(x^6+12x^3-216)(x^{12}+1104x^6+46656)$ 14 $(x-4)(x^2-2x-6)(x^{14}-1584x^7-2779936)(x^{14}+432x^7-2779936)$ $(x^{14}+3792x^7-2779936)$ 16 $(x-4)(x^2-2x-6)(x^2+6)(x^2-6)(x^4+36)(x^8-96x^4+1296)$ $(x^8+96x^4+1296)(x^{16}+3456x^8+1679616)(x^{16}+14208x^8+1679616)$
•  [1] 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. Comb. Th. A, 127 (2014), 161-175.  doi: 10.1016/j.jcta.2014.05.008. [2] A. Chirvasitu and T. W. Cusick, Affine equivalence for quadratic rotation symmetric Boolean functions, Designs, Codes and Cryptography, 88 (2020), 1301-1329.  doi: 10.1007/s10623-020-00748-5. [3] T. W. Cusick, Weight recursions for any rotation symmetric Boolean functions, IEEE Trans. Inform. Th., 64 (2018), 2962-2968.  doi: 10.1109/TIT.2017.2785773. [4] T. W. Cusick and Y. Cheon, Affine equivalence of quartic homogeneous rotation symmetric Boolean functions, Inform. Sci., 259 (2014), 192-211.  doi: 10.1016/j.ins.2013.09.001. [5] T. W. Cusick and Y. Cheon, Weights for short quartic Boolean functions, Inform. Sci., 547 (2021), 18-27.  doi: 10.1016/j.ins.2020.07.019. [6] T. W. Cusick, Y. Cheon and K. Dougan, Theory of 2-rotation symmetric quartic Boolean functions, Inform. Sci., 508 (2020), 358-379.  doi: 10.1016/j.ins.2019.08.074. [7] T. W. Cusick and B. Johns, Theory of 2-rotation symmetric cubic Boolean functions, Designs, Codes and Cryptography, 76 (2015), 113-133.  doi: 10.1007/s10623-014-9964-2. [8] T. W. Cusick and D. Padgett, A recursive formula for weights of Boolean rotation symmetric functions, Discrete Appl. Math., 160 (2012), 391-397.  doi: 10.1016/j.dam.2011.11.006. [9] G. Everest, A. I. Shparlinski and T. Ward, Recurrence Sequences, Math. Surveys Monographs, 104, American Mathematical Society, Providence, 2003. doi: 10.1090/surv/104. [10] S. Kavut and M. D. Yücel, Generalized rotation symmetric and dihedral symmetric Boolean functions - 9 variable Boolean functions with nonlinearity $242$, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC 2007), Springer LNCS, 485, Springer, Berlin, 2007,321–329. doi: 10.1007/978-3-540-77224-8_37. [11] 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. [12] S. Kavut, Results on rotation-symmetric S-boxes, Information Sciences, 201 (2012), 93-113.  doi: 10.1016/j.ins.2012.02.030. [13] S. Kavut and S. Baloğlu, Classification of $6\times 6$ S-boxes obtained by concatenation of RSSBs, in Lightweight Cryptography for Security and Privacy, Springer LNCS, 10098, Springer, Berlin, 2017,110–127. doi: 10.1007/978-3-319-55714-4_8. [14] S. Kavut and S. Baloğlu, Results on symmetric S-boxes constructed by concatenation of RSSBs, Cryptogr. Commun., 11 (2019), 641-660.  doi: 10.1007/s12095-018-0318-1. [15] H. Kim, S-M. Park and S. G. Hahn, On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2, Discrete Appl. Math., 157 (2009), 428-432.  doi: 10.1016/j.dam.2008.06.022. [16] J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Th., 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.

Tables(2)