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

Thomas W. Cusick; Younhwan Cheon

doi:10.3934/amc.2021011

Article Contents

2023, Volume 17, Issue 3: 589-604. Doi: 10.3934/amc.2021011

This issue Previous Article Partial direct product difference sets and almost quaternary sequences Next Article Some progress on optimal $ 2 $-D $ (n\times m,3,2,1) $-optical orthogonal codes

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

Thomas W. Cusick^1, and
Younhwan Cheon^2,

1.
Department of Mathematics, University at Buffalo, 244 Mathematics Bldg., Buffalo, NY 14260
2.
Department of Military Operations Research, Korea Army Academy at YeongCheon, 135-9, Hoguk-ro, Gogyeong-myeon, Yeongcheon-si, Gyeongsangbuk-do, Republic of Korea, 38900

Received: October 2020

Revised: February 2021

Early access: May 2021

Published: June 2023

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

Abstract

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.

Keywords:

Mathematics Subject Classification: 94C10 94A60 06E30.

Citation:

Full Text(HTML)

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}) $

| Show Table

DownLoad: CSV

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) $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.