zbMATH — the first resource for mathematics

Cyclic codes with few weights and Niho exponents. (English) Zbl 1072.94016
In this paper binary cyclic codes which have two nonzeros only are treated. Such a code is of length \(n=2^{m}-1\), \(m=2t\), and of dimension \(2m\). To study its weights is actually to compute the sums \(S_{k}(a)=\sum _{x\in F_{2^{m}}} (-1)^{\text{Tr}(x^{k}+ax)}\), \(a\in F_{2^{m}}\), where \(k\) and \(n\) are coprime and Tr is the trace function on \( F_{2^{m}}\), the finite field of order \(2^{m}\). These sums can be seen as the Fourier-transforms of the Boolean function Tr\((x^{k})\) and the function \(S_{k}(a)\) provides the crosscorrelation function of one \(m\)-sequence of length \(n\) with its decimation by \(k\). The main result is that when \(k\equiv 2^{j}\) (mod \(2^{t}-1\)), for some \(j\), then \(S_{k}(a)\) takes at least four values when \(a\) runs through \( F_{2^{m}}\). This produces an upper bound on the nonlinearity of these Boolean functions, but to find the exact nonlinearity remains an open problem. Finally, three conjectures are proposed.

94B15 Cyclic codes
06E30 Boolean functions
Full Text: DOI
[1] Calderbank, R.; McGuire, G.; Poonen, B.; Rubinstein, M., On a conjecture of helleseth regarding pairs of binary \scm-sequences, IEEE trans. inform. theory, 42, 988-990, (1996) · Zbl 0943.94513
[2] Canteaut, A.; Charpin, P.; Dobbertin, H., Weight divisibility of cyclic codes, highly nonlinear functions on GF(\(2^m\)) and crosscorrelation of maximum-length sequences, SIAM J. discrete math., 13, 1, 105-138, (2000) · Zbl 1010.94013
[3] Canteaut, A.; Charpin, P.; Videau, M., Cryptanalysis of block ciphers and weight divisibility of some binary codes, (), 75-97 · Zbl 1072.94006
[4] Carlet, C.; Charpin, P.; Zinoviev, V., Codes, bent functions and permutations suitable for DES-like cryptosystems, Designs, codes cryptogr., 15, 125-156, (1998) · Zbl 0938.94011
[5] P. Charpin, Open Problems on cyclic codes, Handbook of Coding Theory, Part 1: Algebraic Coding, V.S. Pless, W.C. Huffman (Eds.), R.A. Brualdi (assistant ed.), Elsevier, Amsterdam, the Netherlands, 1998 (Chapter 11).
[6] H. Dobbertin. Construction of bent functions and balanced Boolean functions with high nonlinearity, Fast Software Encryption, Lecture Notes in Computer Science, vol. 1008, Springer, Berlin, Germany, 1994, pp. 61-74. · Zbl 0939.94563
[7] Dobbertin, H., One-to-one highly nonlinear power functions on \(\mathit{GF}(2^n)\). AAECC, Appl. algebra eng. comm. comput., 9, 139-152, (1998) · Zbl 0924.94026
[8] H. Dobbertin, P. Felke, T. Helleseth, P. Rosendalh, Niho type cross-correlation functions via Dickson polynomials and Klosterman sums, preprint. · Zbl 1178.94220
[9] Helleseth, T., Some results about the crosscorrelation function between two maximal linear sequences, Discrete math., 16, 209-232, (1976) · Zbl 0348.94017
[10] T. Helleseth, P.V. Kumar, Sequences with low correlation, Handbook of Coding Theory, Part 3: Applications, V.S. Pless, W.C. Huffman (Eds.), R.A. Brualdi (assistant ed.), Elsevier, Amsterdam, the Netherlands, 1998 (Chapter 21). · Zbl 0924.94027
[11] G. McGuire, On certain 3-weight cyclic codes having symmetric weight and a conjecture of Helleseth, in Proceedings of Sequences and their Applications, SETA 01, Springer, series: Discrete Mathematics and Theoretical Computer Science, Springer, Berlin, 2002, pp. 281-295. · Zbl 1030.94043
[12] McGuire, G., On three weights in cyclic codes with two zeros, Finite fields appl., 10, 97-104, (2004) · Zbl 1119.94016
[13] Y. Niho, Multi-valued cross-correlation functions between two maximal linear recursive sequences, Ph.D. Thesis, USCEE Rep. 409. University Southern California, 1972.
[14] V.S. Pless, W.C. Huffman, R.A. Brualdi, An introduction to algebraic codes. Handbook of Coding Theory, Part 1: Algebraic Coding, V.S. Pless, W.C. Huffman (Eds.), R.A. Brualdi (assistant ed.), Elsevier, Amsterdam, the Netherlands, 1998 (Chapter 1). · Zbl 0919.94049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.