• 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
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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]

Wilker Fernandes, Viviane Pardini Valério, Patricia Tempesta. Isochronicity of bi-centers for symmetric quartic differential systems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021215

[5]

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

[6]

Junchao Zhou, Nian Li, Xiangyong Zeng, Yunge Xu. A generic construction of rotation symmetric bent functions. Advances in Mathematics of Communications, 2021, 15 (4) : 721-736. doi: 10.3934/amc.2020092

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

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

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

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (46)
  • HTML views (167)
  • Cited by (0)

Other articles
by authors

[Back to Top]