• Previous Article
    On the equivalence of several classes of quaternary sequences with optimal autocorrelation and length $ 2p$
  • AMC Home
  • This Issue
  • Next Article
    On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $
doi: 10.3934/amc.2021011

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

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

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.

Citation: Thomas W. Cusick, Younhwan Cheon. The weight recursions for the 2-rotation symmetric quartic Boolean functions. Advances in Mathematics of Communications, doi: 10.3934/amc.2021011
References:
[1]

C. CarletG. 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.  Google Scholar

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

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

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

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

[6]

T. W. CusickY. 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.  Google Scholar

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

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

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

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

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

[12]

S. Kavut, Results on rotation-symmetric S-boxes, Information Sciences, 201 (2012), 93-113.  doi: 10.1016/j.ins.2012.02.030.  Google Scholar

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

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

[15]

H. KimS-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.  Google Scholar

[16]

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Th., 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.  Google Scholar

show all references

References:
[1]

C. CarletG. 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.  Google Scholar

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

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

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

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

[6]

T. W. CusickY. 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.  Google Scholar

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

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

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

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

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

[12]

S. Kavut, Results on rotation-symmetric S-boxes, Information Sciences, 201 (2012), 93-113.  doi: 10.1016/j.ins.2012.02.030.  Google Scholar

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

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

[15]

H. KimS-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.  Google Scholar

[16]

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Th., 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.  Google Scholar

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

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

[2]

Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409

[3]

Claude Carlet, Serge Feukoua. Three parameters of Boolean functions related to their constancy on affine spaces. Advances in Mathematics of Communications, 2020, 14 (4) : 651-676. doi: 10.3934/amc.2020036

[4]

Yulin Zhao, Siming Zhu. Higher order Melnikov function for a quartic hamiltonian with cuspidal loop. Discrete & Continuous Dynamical Systems, 2002, 8 (4) : 995-1018. doi: 10.3934/dcds.2002.8.995

[5]

Junchao Zhou, Nian Li, Xiangyong Zeng, Yunge Xu. A generic construction of rotation symmetric bent functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020092

[6]

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

[7]

Nupur Patanker, Sanjay Kumar Singh. Generalized Hamming weights of toric codes over hypersimplices and squarefree affine evaluation codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021013

[8]

David Keyes. $\mathbb F_p$-codes, theta functions and the Hamming weight MacWilliams identity. Advances in Mathematics of Communications, 2012, 6 (4) : 401-418. doi: 10.3934/amc.2012.6.401

[9]

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

[10]

Carlos Matheus, Jean-Christophe Yoccoz. The action of the affine diffeomorphisms on the relative homology group of certain exceptionally symmetric origamis. Journal of Modern Dynamics, 2010, 4 (3) : 453-486. doi: 10.3934/jmd.2010.4.453

[11]

M. L. Miotto. Multiple solutions for elliptic problem in $\mathbb{R}^N$ with critical Sobolev exponent and weight function. Communications on Pure & Applied Analysis, 2010, 9 (1) : 233-248. doi: 10.3934/cpaa.2010.9.233

[12]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011

[13]

Tsung-Fang Wu. On semilinear elliptic equations involving critical Sobolev exponents and sign-changing weight function. Communications on Pure & Applied Analysis, 2008, 7 (2) : 383-405. doi: 10.3934/cpaa.2008.7.383

[14]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

[15]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[16]

Rafael G. L. D'Oliveira, Marcelo Firer. Minimum dimensional Hamming embeddings. Advances in Mathematics of Communications, 2017, 11 (2) : 359-366. doi: 10.3934/amc.2017029

[17]

Ming Su, Arne Winterhof. Hamming correlation of higher order. Advances in Mathematics of Communications, 2018, 12 (3) : 505-513. doi: 10.3934/amc.2018029

[18]

Jiao Du, Longjiang Qu, Chao Li, Xin Liao. Constructing 1-resilient rotation symmetric functions over $ {\mathbb F}_{p} $ with $ {q} $ variables through special orthogonal arrays. Advances in Mathematics of Communications, 2020, 14 (2) : 247-263. doi: 10.3934/amc.2020018

[19]

Yi Ming Zou. Dynamics of boolean networks. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1629-1640. doi: 10.3934/dcdss.2011.4.1629

[20]

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (33)
  • HTML views (108)
  • Cited by (0)

Other articles
by authors

[Back to Top]