A note on cyclic codes from APN functions

详细信息    查看全文

• 作者：Chunming Tang (1)
  Yanfeng Qi (2) (3)
  Maozhi Xu (2)
  
• 关键词：Cyclic codes ; Sequences ; Linear span ; Minimal polynomials ; APN functions ; 94B15 ; 94A55
• 刊名：Applicable Algebra in Engineering, Communication and Computing
• 出版年：2014
• 出版时间：April 2014
• 年：2014
• 卷：25
• 期：1-2
• 页码：21-37
• 全文大小：215 KB
• 参考文献：1. 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-30 (1992) CrossRef
  2. 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)
  3. Blake, I., Mullen, R.C.: The Mathematical Theory of Coding. Academic Press, New York (1975)
  4. 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-38 (2000) CrossRef
  5. Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosys-tems. Des. Codes Cryptogr. 15, 125-56 (1998) CrossRef
  6. Carlet, C., Ding, C., Yuan, J.: Linear codes from highly nonlinear functions and their secret sharing schemes. IEEE Trans. Inform. Theory 51(6), 2089-102 (2005) CrossRef
  7. 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)
  8. Chien, R.T.: Cyclic decoding procedure for the Bose-Chaudhuri-Hocquenghem codes. IEEE Trans. Inform. Theory 10, 357-63 (1964) CrossRef
  9. Ding, C.: Cyclic codes from some monomials and trinomials. SIAM J. Discret. Math. 27(4), 1977-994 (Dec. 2013)
  10. Ding, C., Xiao, G., Shan, W.: The stability theory of stream ciphers. In: Lecture Notes in Computer Science, vol. 561. Springer, Heidelberg (1991)
  11. Ding, C., Zhou, Z.: Binary cyclic codes from explicit polynomials over $\text{ GF }(2^m)$ . Discret. Math. (to appear) (2014)
  12. Dobbertin, H.: Almost perfect nonlinear power functions on $\text{ GF }(2^n)$ : the Niho case. Inform. Comput. 151, 57-2 (1999) CrossRef
  13. Forney, G.D.: On decoding BCH codes. IEEE Trans. Inform. Theory 11(4), 549-57 (1995) CrossRef
  14. Helleseth, T., Rong, C., Sandberg, D.: New families of almost perfect nonlinear power mappings. IEEE Trans. Inform. Theory 45(2), 475-85 (1999) CrossRef
  15. Hartmann, C.R.P., Tzeng, K.K.: Generalizations of the BCH bound. Inf. Control 20, 489-98 (1972) CrossRef
  16. Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003) CrossRef
  17. Lucas, E.: Théorie des fonctions numériques simplement périodiques. Am. J. Math. 1, 229-31 (1878)
  18. Lidl, L., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997)
  19. Nyberg, K.: Differentially uniform mappings for cryptography. In: Advances in Cryptology-EUROCRYPT 93, Lecture Notes in Comput. Sci. 765, pp. 55-4. Springer, New York (1993)
  20. Prange, E.: Some Cyclic Error-Correcting Codes with Simple Decoding Algorithms. Air Force Cambridge Research Center-TN-58-156, Cambridge, MA (April 1958)
  21. Si, W., Ding, C.: A simple stream cipher with proven properties. Cryptogr. Commun. 4(2), 79-04 (2012) CrossRef
  22. van Lint, J.H., Wilson, R.M.: On the minimum distance of cyclic codes. IEEE Trans. Inform. Theory 32(1), 23-0 (1986) CrossRef
  
• 作者单位：Chunming Tang (1)
  Yanfeng Qi (2) (3)
  Maozhi Xu (2)
  
  1. School of Mathematics and Information, China West Normal University, Nanchong, 637002, Sichuan, China
  2. LMAM, School of Mathematical Sciences, Peking University, Beijing, 100871, China
  3. Aisino Corporation Inc., Beijing, 100195, China
  
• ISSN：1432-0622

文摘

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-994, 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-994, 2013), Ding and Zhou (Discret Math, 2014).