Abstract
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).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
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)
Acknowledgments
We would like to show many thanks to Prof. Cunsheng Ding and anonymous reviewers for their helpful advice and comments. This work was supported by the National Natural Science Foundation of China (Grant Nos. 61272499, 10990011). Yanfeng Qi acknowledges support from Aisino Corporation Inc.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tang, C., Qi, Y. & Xu, M. A note on cyclic codes from APN functions. AAECC 25, 21–37 (2014). https://doi.org/10.1007/s00200-014-0217-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-014-0217-4