betaFeedback

WorksComputer Science

Correlation distribution for a class of Niho exponents via self-conjugate-reciprocal polynomials and Kloosterman sums

Abstract

Let q=2mq=2^m for an even m≥6m\geq 6 and let d=s(q−1)+1d=s(q-1)+1 with 4s≡5(modq+1)4s\equiv5\pmod{q+1}. In this paper, the correlation distribution between a binary m-sequence of period q2−1q^2-1 and its dd-decimation is considered. The cross-correlation function takes seven values q(i−1)−1q(i-1)-1 for 0≤i≤60\leq i\leq 6, and we determine their frequencies based on the study of low-degree self-conjugate-reciprocal polynomials and three mixed Kloosterman sums, which are finally expressed in terms of Km(1)K_m(1) and Km(ω)K_m(ω), where Km(⋅)K_m(\cdot) is the Kloomsterman sum on the finite field Fq\mathbb{F}_q and ωω is a primitive element of F4\mathbb{F}_4.

Introduction

Let qq be a power of two and Fq2\mathbb{F}_{q^2} be the finite field with q2q^2 elements. Niho in his thesis [1] intensively studied the cross-correlation between binary m-sequences of length q2−1q^2-1 and their dd-decimated m-sequences when dd is of the form d=s(q−1)+1d=s(q-1)+1 for certain positive integer ss. It turned out this type of integers involved interesting algebraic structures over finite fields and they were later referred to as normalized Niho exponents in the literature. In the last decades researchers have explored their applications in different areas, including low-correlation sequences [1, 2, 3, 4, 5, 6], bent functions [7, 8], highly nonlinear functions [9], permutation polynomials [10, 11], cyclic codes [12, 13], Weil sums [14, 15], Kloosterman sums [4], etc. Interested readers may refer to the survey on Niho exponents and their applications in [16].

When a Niho exponent dd is co-prime to q2−1q^2-1, the following three problems are equivalent [4]: the value distribution of cross-correlation between a binary m-sequence of length q2−1q^2-1 and its dd-decimated sequence, the value distribution of Walsh transforms of the power function xdx^d over the finite field Fq2\mathbb{F}_{q^2}, and the weight distribution of the cyclic code of length q2−1q^2-1 associated with α,αd\alpha,\alpha^d, where α\alpha is a primitive element of Fq2\mathbb{F}_{q^2}. More concretely, these three problems reduce to the value distribution of the following Weil sum

Wd(a)=∑x∈Fq2(−1)Tr2m(xd+ax),a∈Fq2,(1)W_d(a)=\sum_{x\in\mathbb{F}_{q^2}}(-1)^{\mathrm{Tr}_{2m}(x^d+ax)},\qquad a\in\mathbb{F}_{q^2}, \tag*{(1)}

where Tr2m(⋅)\mathrm{Tr}_{2m}(\cdot) denotes the trace function from Fq2=F22m\mathbb{F}_{q^2}=\mathbb{F}_{2^{2m}} to F2\mathbb{F}_2. Actually the cross-correlation function Cd(τ)C_d(\tau) between a binary m-sequence of length q2−1q^2-1 and its dd-decimated sequence is given by

Cd(τ)=Wd(ατ)−1,0≤τ<q2−1.C_d(\tau)=W_d(\alpha^\tau)-1,\qquad0\leq\tau<q^2-1.

To determine the value distribution of Wd(a)W_d(a) for a normalized Niho exponent d=s(q−1)+1d=s(q-1)+1, one typically transforms this problem to counting roots of an associated polynomial fs,a(x)=x2s−1+axs+aˉxs−1+1f_{s,a}(x)=x^{2s-1}+ax^s+\bar{a}x^{s-1}+1 in the unit circle U={u∈Fq2:uq+1=1}U=\{u\in\mathbb{F}_{q^2}:u^{q+1}=1\}, as the element aa runs through Fq2\mathbb{F}_{q^2}. It is worth noting that the problem has been investigated more than fifty years. Back to 1972 Niho in his PhD thesis [1] tried different choices of ss, provided a complete 4-valued distribution of cross-correlation for s=2s=2, and left a lot of problems unsolved. Other values of ss were considered later [17]. In 2006 Dobbertin, Felke, Helleseth and Rosendahl [4] considered a general form of Niho exponents d=s(q−1)+1d=s(q-1)+1 with s≡2r/(2r±1)(modq+1)s\equiv2^r/(2^r\pm1)\pmod{q+1}, which includes all known Niho-type decimations for which the cross-correlation function Cd(τ)C_d(\tau) takes 4 possible values. For s=3s=3, the polynomial fs,a(x)f_{s,a}(x) is quintic and can have at most 5 roots in UU, implying that the cross-correlation function may take 6 possible values; the cross-correlation distribution for odd mm was determined in [4] via Dickson polynomials and the cases of even mm were unsettled. Ten years later Xia, Li, Zeng and Helleseth [5] resolved the problem for both even and odd mm via an interesting connection to the number of weight-five codewords in Zetterberg codes. For s=4s=4, while the polynomial fs,a(x)f_{s,a}(x) has degree seven, Niho in his thesis conjectured that it actually had 0, 1, 2, 3, 5 roots in UU for even mm based on numerical results; this conjecture wasn’t resolved until the work of Helleseth, Katz and Li [15] in 2021, where they connected this problem to an orbit pattern of roots of self-conjugate-reciprocal polynomials under a conjugate-reciprocal action; and very recently Xiong and Yan [18] determined the complete distribution of the cross-correlation function for s=4s=4 by a detailed study of the case when fs,a(x)f_{s,a}(x) has five roots in UU. The developments of this research line, which traced back to Niho’s work in 1972, indicate the problem’s intractability as ss increase. More importantly, those developments uncovered some intrinsic connections of Niho-exponents and interesting objects in other branches of discrete mathematics and coding theory [7, 12, 5, 19].

In this paper, we will consider the following Niho exponent

d=s(q−1)+1,4s≡5(modq+1),(2)d=s(q-1)+1,\qquad4s\equiv5\pmod{q+1}, \tag*{(2)}

which covers some instances in [1 Table 3-3]. In this case dd is co-prime to q2−1q^2-1 when mm is even. For the associated polynomial fs,a(x)f_{s,a}(x), one can equivalently consider a hexic polynomial Pa(x)=x6+ax5+aˉx+1P_a(x)=x^6+ax^5+\bar{a}x+1, indicating that the cross-correlation function takes at most 7 values of the form q(i−1)−1q(i-1)-1 for 0≤i≤60\leq i\leq6. In order to determine the cross-correlation distribution for this Niho exponent, we start by developing some general results on self-conjugate-reciprocal (SCR) polynomials [15], namely polynomials f(x)=∑i=0dfixi∈Fq2[x]f(x)=\sum_{i=0}^{d}f_i x^i\in\mathbb{F}_{q^2}[x] whose coefficients satisfy fi=(fd−i)qf_i=(f_{d-i})^q, which include polynomials fs,a(x)f_{s,a}(x) as special cases. In this part we provide one general way to transform SCR polynomials over Fq2\mathbb{F}_{q^2} to polynomials over Fq\mathbb{F}_q (see Proposition 3.1) and one way to transform quartic SCR polynomials over Fq2\mathbb{F}_{q^2} to cubic resolvent polynomials over Fq\mathbb{F}_q (see Proposition 3.4).

This helps us characterize the cases where Pa(x)P_a(x) has exactly 4, 5, or 6 roots in UU, which are described mainly in terms of trace conditions on involved parameters. Furthermore, we consider the enumeration of those cases by calculating character sums for those trace conditions. Based on the correspondence between (x,y)(x,y) and (x+y,xy)(x+y,xy) in Fq2\mathbb{F}_{q^2}, we transform all involved character sums and express them in terms of Kloosterman sums Km(1)K_m(1) and Km(ω)K_m(\omega), where ω\omega is a primitive element of F4\mathbb{F}_4. Finally the complete correlation distribution is determined and is given as follows.

References

  1. [1]Y. Niho, Multi-Valued Cross-Correlation Functions Between Two Maximal Linear Recursive Sequences. Ph.D. dissertation, University of Southern California, Los Angeles, 1972.
  2. [2]T. Helleseth, “Some results about the cross-correlation function between two maximal linear sequences,” Discrete Math., vol. 16, no. 3, pp. 209–232, 1976.DOI
  3. [3]T. Helleseth, J. Lahtonen, and P. Rosendahl, “On Niho type cross-correlation functions of m-sequences,” Finite Fields Appl., vol. 13, no. 2, pp. 305–317, 2007.
  4. [4]H. Dobbertin, P. Felke, T. Helleseth, and P. Rosendahl, “Niho type cross-correlation functions via Dickson polynomials and Kloosterman sums,” IEEE Trans. Inform. Theory, vol. 52, no. 2, pp. 613–627, 2006.DOI
  5. [5]Y. Xia, N. Li, X. Zeng, and T. Helleseth, “An open problem on the distribution of a Niho-type cross-correlation function,” IEEE Trans. Inform. Theory, vol. 62, no. 12, pp. 7546–7554, 2016.DOI
  6. [6]Y. Xia, N. Li, X. Zeng, and T. Helleseth, “On the correlation distribution for a Niho decimation,” IEEE Trans. Inform. Theory, vol. 63, no. 11, pp. 7206–7218, 2017.DOI
  7. [7]H. Dobbertin, G. Leander, A. Canteaut, C. Carlet, P. Felke, and P. Gaborit, “Construction of bent functions via Niho power functions,” J. Combin. Theory Ser. A, vol. 113, no. 5, pp. 779–798, 2006.DOI
  8. [8]G. Leander and A. Kholosha, “Bent functions with 2^r Niho exponents,” IEEE Trans. Inf. Theory, vol. 52, no. 12, pp. 5529–5532, 2006.DOI
  9. [9]N. Li, T. Helleseth, A. Kholosha, and X. Tang, “On the Walsh transform of a class of functions from Niho exponents,” IEEE Trans. Inf. Theory, vol. 59, no. 7, pp. 4662–4667, 2013.DOI
  10. [10]N. Li and T. Helleseth, “Several classes of permutation trinomials from Niho exponents,” Cryptogr. Commun., vol. 9, no. 6, pp. 693–705, 2017.DOI
  11. [11]T. Bai and Y. Xia, “A new class of permutation trinomials constructed from Niho exponents,” Cryptogr. Commun., vol. 10, pp. 1023–1036, 2017.arxiv.org/abs/1707.00549
  12. [12]P. Charpin, “Cyclic codes with few weights and Niho exponents,” J. Combin. Theory Ser. A, vol. 108, no. 2, pp. 247–259, 2004.DOI
  13. [13]S. Li, T. Feng, and G. Ge, “On the weight distribution of cyclic codes with Niho exponents,” IEEE Trans. Inf. Theory, vol. 60, no. 7, pp. 3903–3912, 2014.arxiv.org/abs/1401.1887
  14. [14]D. J. Katz, “Weil sums of binomials, three-level cross-correlation, and a conjecture of Helleseth,” J. Combin. Theory Ser. A, vol. 119, no. 8, pp. 1644–1659, 2012.DOI
  15. [15]T. Helleseth, D. J. Katz, and C. Li, “The resolution of Niho’s last conjecture concerning sequences, codes, and Boolean functions,” IEEE Trans. Inform. Theory, vol. 67, no. 10, pp. 6952–6962, 2021.arxiv.org/abs/2006.12239
  16. [16]N. Li and X. Zeng, “A survey on the applications of Niho exponents,” Cryptography and Communications, vol. 11, pp. 509–548, May 2019.DOI
  17. [17]H. D. L. Hollmann and Q. Xiang, “A proof of the Welch and Niho conjectures on cross-correlations of binary m-sequences,” Finite Fields Appl., vol. 7, pp. 253–286, Apr. 2001.DOI
  18. [18]M. Xiong and H. Yan, “The cross-correlation distribution of the Niho-type decimation d = 4(2ᵐ − 1) + 1,” arXiv:2609.04683v2, 2026.arxiv.org/abs/2609.04683
  19. [19]M. Xiong, N. Li, Z. Zhou, and C. Ding, “Weight distribution of cyclic codes with arbitrary number of generalized Niho type zeroes,” Des. Codes Cryptogr., vol. 78, no. 3, pp. 713–730, 2016.
  20. [20]H. D. Kloosterman, “On the representation of numbers in the form ax²+by²+cz²+dt²,” Acta Math., vol. 49, pp. 407–464, 1926.DOI
  21. [21]R. Lidl and H. Niederreiter, Finite Fields. Cambridge, U.K.: Cambridge Univ. Press, 2nd ed., 1996.DOI
  22. [22]T. Helleseth and V. Zinoviev, “On Z₄-linear Goethals codes and Kloosterman sums,” Des. Codes Cryptogr., vol. 17, pp. 269–288, 1999.DOI
  23. [23]P. Charpin and G. Gong, “Hyperbent functions, Kloosterman sums, and Dickson polynomials,” IEEE Trans. Inform. Theory, vol. 54, no. 9, pp. 4230–4238, 2008.
  24. [24]H. D. L. Hollmann and Q. Xiang, “Kloosterman sum identities over F₂ᵐ,” Discrete Math., vol. 279, no. 1, pp. 277–286, 2004.DOI
  25. [25]V. A. Zinoviev, “On classical Kloosterman sums,” Cryptogr. Commun., vol. 11, no. 3, pp. 461–496, 2019.DOI
  26. [26]L. Carlitz, “Kloosterman sums and finite field extensions,” Acta Arith., vol. 16, pp. 179–194, 1969.DOI
  27. [27]L. Carlitz and S. Uchiyama, “Bounds for exponential sums,” Duke Math. J., vol. 24, pp. 37–42, 1957.DOI
  28. [28]P. Rosendahl, “A generalization of Niho’s theorem,” Des. Codes Cryptogr., vol. 38, pp. 331–336, 2006.DOI
  29. [29]T. Helleseth, “A note on the cross-correlation function between two binary maximal length linear sequences,” Discrete Math., vol. 23, no. 3, pp. 301–307, 1978.DOI
  30. [30]A. W. Bluher, “Permutation properties of Dickson and Chebyshev polynomials with connections to number theory,” Finite Fields Appl., vol. 76, p. 101899, 2021.DOI
  31. [31]E. R. Berlekamp, “An analog to the discriminant over fields of characteristic two,” J. Algebra, vol. 38, pp. 315–317, 1976.DOI
  32. [32]K. S. Williams, “Note on cubics over GF(2ⁿ) and GF(3ⁿ),” J. Number Theory, vol. 7, no. 4, pp. 361–365, 1975.DOI

Paper details

vlnc:W_sfeahpct
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents