A note on cyclic codes from APN functions
Tóm tắt
Cyclic codes, as linear block error-correcting codes in coding theory, play a vital role and have wide applications. Ding (SIAM J Discret Math 27(4):1977–1994, 2013), Ding and Zhou (Discret Math, 2014) constructed a number of classes of cyclic codes from almost perfect nonlinear (APN) functions and planar functions over finite fields and presented some open problems on cyclic codes from highly nonlinear functions. In this paper, we consider two open problems involving the inverse APN function
$$f(x)=x^{q^m-2}$$
and the Dobbertin APN function
$$f(x)=x^{2^{4i}+2^{3i}+2^{2i}+2^{i}-1}$$
. From the calculation of linear spans and the minimal polynomials of two sequences generated by these two classes of APN functions, the dimensions of the corresponding cyclic codes are determined and lower bounds on the minimum weight of these cyclic codes are presented. Actually, we present a framework for the minimal polynomial and linear span of the sequence
$$s^{\infty }$$
defined by
$$s_t={\mathrm {Tr}}((1+\alpha ^t)^e)$$
, where
$$\alpha $$
is a primitive element in
$${\mathrm {GF}}(q)$$
. These techniques can also be applied to other open problems in Ding (SIAM J Discret Math 27(4):1977–1994, 2013), Ding and Zhou (Discret Math, 2014).
Tài liệu tham khảo
Antweiler, M., Bomer, L.: complex sequences over \(\text{ GF }(p^M)\) with a two-level autocorrelation function and a large linear span. IEEE Trans. Inform. Theory 38, 120–130 (1992)
Beth, T., Ding, C.: On almost perfect nonlinear permutations. In: Advances in Cryptology-EUROCRYPT 93, Lecture Notes in Comput. Sci. 765, p. 6576. Springer, New York (1993)
Blake, I., Mullen, R.C.: The Mathematical Theory of Coding. Academic Press, New York (1975)
Canteaut, A., Charpin, P., Dobbertin, H.: Weight divisibility of cyclic codes, highly nonlinear functions on\(F_{2^m}\), and crosscorrelation of maximum-length sequences. SIAM. J. Discret. Math. 13(1), 105–138 (2000)
Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosys-tems. Des. Codes Cryptogr. 15, 125–156 (1998)
Carlet, C., Ding, C., Yuan, J.: Linear codes from highly nonlinear functions and their secret sharing schemes. IEEE Trans. Inform. Theory 51(6), 2089–2102 (2005)
Charpin, P.: Open problems on cyclic codes. In: Pless, V.S., Huffman, W.C., Brualdi, R.A. (eds.) Handbook of Coding Theory, Part 1: Algebraic Coding. Elsevier, Amsterdam, The Netherlands, ch. 11 (1998)
Chien, R.T.: Cyclic decoding procedure for the Bose-Chaudhuri-Hocquenghem codes. IEEE Trans. Inform. Theory 10, 357–363 (1964)
Ding, C.: Cyclic codes from some monomials and trinomials. SIAM J. Discret. Math. 27(4), 1977–1994 (Dec. 2013)
Ding, C., Xiao, G., Shan, W.: The stability theory of stream ciphers. In: Lecture Notes in Computer Science, vol. 561. Springer, Heidelberg (1991)
Ding, C., Zhou, Z.: Binary cyclic codes from explicit polynomials over \(\text{ GF }(2^m)\). Discret. Math. (to appear) (2014)
Dobbertin, H.: Almost perfect nonlinear power functions on \(\text{ GF }(2^n)\): the Niho case. Inform. Comput. 151, 57–72 (1999)
Forney, G.D.: On decoding BCH codes. IEEE Trans. Inform. Theory 11(4), 549–557 (1995)
Helleseth, T., Rong, C., Sandberg, D.: New families of almost perfect nonlinear power mappings. IEEE Trans. Inform. Theory 45(2), 475–485 (1999)
Hartmann, C.R.P., Tzeng, K.K.: Generalizations of the BCH bound. Inf. Control 20, 489–498 (1972)
Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003)
Lucas, E.: Théorie des fonctions numériques simplement périodiques. Am. J. Math. 1, 229–231 (1878)
Lidl, L., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997)
Nyberg, K.: Differentially uniform mappings for cryptography. In: Advances in Cryptology-EUROCRYPT 93, Lecture Notes in Comput. Sci. 765, pp. 55–64. Springer, New York (1993)
Prange, E.: Some Cyclic Error-Correcting Codes with Simple Decoding Algorithms. Air Force Cambridge Research Center-TN-58-156, Cambridge, MA (April 1958)
Si, W., Ding, C.: A simple stream cipher with proven properties. Cryptogr. Commun. 4(2), 79–104 (2012)
van Lint, J.H., Wilson, R.M.: On the minimum distance of cyclic codes. IEEE Trans. Inform. Theory 32(1), 23–40 (1986)