×

A proof of the Welch and Niho conjectures on cross-correlations of binary \(m\)-sequences. (English) Zbl 1027.94006

The authors study the number of values attained by the cross-correlation of a binary \(m\)-sequence and its decimation by a factor of \(t\). This number equals the number of nonzero weights in the dual of \(C_{1,t}\), the binary cyclic code of length \(2^m-1\) with defining zeros \(\alpha\) and \(\alpha^t\), where \(\alpha\) is primitive in \(\mathrm{GF}(2^m)\).
A unified method is presented for proving that \(C^\perp_{1,t}\) has three weight for the following pairs \((m,t)\):
(a) \(t= 2^r+1\) if \((r,m)= 1\) (proved by Gold in 1968),
(b) \(t= 2^{2r}- 2^r+ 1\) if \((r,m)= 1\) (proved by Welch (1969) and Kasami (1971)),
(c) \(m= 2r+ 1\), \(t= 2^r+ 3\) (conjectured by Welch in 1972),
(d) \(m\) is odd, \(4r\equiv-1\pmod m\), \(t= 2^{2r}+ 2^r- 1\) (conjectured by Niho, 1972).
The method uses the Pless power moment identities, a deep theorem of McEliece on the divisibility of nonzero weights in cyclic codes by powers of two, and an ingenious counting method. In the application of the Pless power moment identities, Dobbertin’s breakthrough result [H. Dobbertin, IEEE Trans. Inf. Theory 45, 1271–1275 (1999; Zbl 0957.94021); Inf. Comput. 151, 57–72 (1999; Zbl 1072.94513)] is used, which states that in cases (c) and (d), \(C_{1,t}\) has minimum distance 5.

MSC:

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94B15 Cyclic codes
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brouwer, A. E.; Tolhuizen, L. M.G. M., A sharpening of the Johnson bound for binary linear codes, Des. Codes and Cryptogr., 3, 95-98 (1991) · Zbl 0770.94005
[2] Calderbank, A. R.; Goethals, J.-M., Three-weight codes and association schemes, Philips J. Res., 39, 143-152 (1984) · Zbl 0546.94016
[3] Calderbank, A. R.; McGuire, G.; Poonen, B.; Rubinstein, M., On a conjecture of Helleseth regarding pairs of binary m-sequences, IEEE Trans. Inform. Theory, 42, 988-990 (1996) · Zbl 0943.94513
[4] A. Canteaut, P. Charpin, and, H. Dobbertin, Binary m-sequences with three-valued cross-correlation: A proof of Welch’s conjecture, submitted for publication.; A. Canteaut, P. Charpin, and, H. Dobbertin, Binary m-sequences with three-valued cross-correlation: A proof of Welch’s conjecture, submitted for publication. · Zbl 1003.94519
[5] Carlet, A.; Charpin, P.; Zinoviev, V., Codes, bent functions, and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15, 125-156 (1998) · Zbl 0938.94011
[6] Chang, A.; Gaal, P.; Golomb, S. W.; Gong, G.; Kumar, P. V., On a Sequence Conjectured to Have Ideal 2-level Autocorrelation Function (1998), ISIT: ISIT Cambridge
[7] Cusick, T.; Dobbertin, H., Some new three-valued cross-correlation functions for binary m-sequences, IEEE Trans. Inform. Theory, 42, 1238-1240 (1996) · Zbl 0855.94012
[8] Dobbertin, H., Almost perfect nonlinear power functions on GF \((2^n)\): The Welch case, IEEE Trans. Inform. Theory, 45, 1271-1275 (1999) · Zbl 0957.94021
[9] Dobbertin, H., Almost Perfect nonlinear power functions on GF \((2^n)\): The Niho case, Inform. and Comput., 151, 57-72 (1999) · Zbl 1072.94513
[10] Evans, R.; Hollmann, H. D.L.; Krattenthaler, C.; Xiang, Q., Gauss sums, Jacobi sums, and p-ranks of cyclic difference sets, J. Combin. Theory Ser. A, 87, 74-119 (1999) · Zbl 0943.05021
[11] Gold, R., Maximal recursive sequences with 3-valued cross-correlation functions, IEEE Trans. Inform. Theory, 14, 154-156 (1968) · Zbl 0228.62040
[12] Helleseth, T., Some results about the cross-correlation function between two maximal linear sequences, Discrete Math., 16, 209-232 (1976) · Zbl 0348.94017
[13] Kasami, T., Weight distribution of Bose-Chaudhuri-Hocquenghem codes, (Bose, R. C.; Dowling, T. A., Proceedings Conference Combinatorial Mathematics and Its Applications (1969), Univ. of North Carolina Press: Univ. of North Carolina Press Chapel Hill), 335-357 · Zbl 0211.51401
[14] Kasami, T., The weight enumerator for several classes of subcodes of the 2nd order binary Reed-Muller codes, Inform. and Control, 18, 369-394 (1971) · Zbl 0217.58802
[15] van Lint, J. H.; Wilson, R. M., On the minimum distance of cyclic codes, IEEE Trans. Inform. Theory, 32, 23-40 (1986) · Zbl 0616.94012
[16] McEliece, R. J., On periodic sequences from GF \((q)\), J. Combin. Theory Ser. A, 10, 80-91 (1971) · Zbl 0219.12020
[17] McGuire, G.; Calderbank, A. R., Proof of a conjecture of Sarwate and Pursley regarding pairs of binary m-sequences, IEEE Trans. Inform. Theory, 41, 1153-1155 (1995) · Zbl 0830.94010
[18] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1977), North-Holland: North-Holland Amsterdam · Zbl 0369.94008
[19] Niho, Y., Multi-valued Cross-Correlation Functions Between Two Maximal Linear Recursive Sequences (1972), Univ. of Southern California: Univ. of Southern California Los Angeles
[20] Pless, V., Power moment identities on weight distributions in error correcting codes, Inform. and Control, 6, 147-152 (1963) · Zbl 0149.37905
[21] Sarwate, D. V.; Pursley, M. B., Cross-correlation properties of pseudorandom and related sequences, Proc. IEEE, 68, 593-619 (1980)
[22] Welch, L. R., Trace Mappings in Finite Fields and Shift Register Cross-Correlation Properties (1969), Univ. Southern CaliforniaElectrical Engineering Department Report
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.