May  2017, 11(2): 389-396. doi: 10.3934/amc.2017033

Some new results on the conjecture on exceptional APN functions and absolutely irreducible polynomials: The gold case

1. 

Department of Mathematics, UPR-Cayey, Puerto Rico (PR), 00736 USA

2. 

Department of Mathematics, UPR-Rio Piedras, San Juan, PR 00931 USA

Received  February 2016 Revised  March 2016 Published  May 2017

An almost perfect nonlinear (APN) function $f:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n}$ (necessarily polynomial) is called exceptional APN if it is APN on infinitely many extensions of $\mathbb{F}_{2^n}$. Aubry, McGuire and Rodier conjectured that the only exceptional APN functions are the Gold and the Kasami-Welch monomial functions. They established that a polynomial function of odd degree is not exceptional APN provided the degree is not a Gold number $(2^k+1)$ or a Kasami-Welch number $(2^{2k}-2^k+1)$. When the degree of the polynomial function is a Gold number or a Kasami-Welch number, several partial results have been obtained by several authors including us. In this article we address these exceptions. We almost prove the exceptional APN conjecture in the Gold degree case when $\deg{(h(x))}$ is odd. We also show exactly when the corresponding multivariate polynomial $φ(x, y, z)$ is absolutely irreducible. Also, there is only one result known when $f(x)=x^{2^{k}+1} + h(x)$, and $\deg(h(x))$ is even. Here, we extend this result as well, thus making progress in this case that seems more difficult.

Citation: Moises Delgado, Heeralal Janwa. Some new results on the conjecture on exceptional APN functions and absolutely irreducible polynomials: The gold case. Advances in Mathematics of Communications, 2017, 11 (2) : 389-396. doi: 10.3934/amc.2017033
References:
[1]

Y. Aubry, G. McGuire and F. Rodier, A few more functions that are not APN infinitely often, in Finite Fields: Theory and Applications, 2010, 23-31. doi: 10.1090/conm/518/10193. Google Scholar

[2]

R. D. BakerJ. H. Van Lint and R. M. Wilson, On the preparata and goethals codes, IEEE Trans. Inf. Theory, 29 (1983), 342-345. doi: 10.1109/TIT.1983.1056675. Google Scholar

[3]

T. P. BergerA. CanteautP. Charpin and Y. Laigle-Chapuy, On almost perfect nonlinear functions over $F_{2n}$, IEEE Trans. Inf. Theory, 52 (2006), 4160-4170. doi: 10.1109/TIT.2006.880036. Google Scholar

[4] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968. Google Scholar
[5]

C. Blondeau and K. Nyberg, Perfect nonlinear functions and cryptography, Finite Fields Appl., 32 (2015), 120-147. doi: 10.1016/j.ffa.2014.10.007. Google Scholar

[6]

L. BudaghyanC. Carlet and G. Leander, Constructing new APN functions from known ones, Finite Fields Appl., 15 (2009), 150-159. doi: 10.1016/j.ffa.2008.10.001. Google Scholar

[7]

E. Byrne and G. McGuire, Quadratic binomial APN functions and absolutely irreducible polynomials, preprint, arXiv: 0810.4523Google Scholar

[8]

C. CarletP. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for des-like cryptosystems, Des. Codes Crypt., 15 (1998), 125-156. doi: 10.1023/A:1008344232130. Google Scholar

[9]

F. Caullery, Polynomial functions of degree 20 which are APN infinitely often, preprint, arXiv: 1212.4638Google Scholar

[10]

F. Caullery, A new large class of functions not APN infinitely often, Des. Codes Crypt., 73 (2014), 601-614. doi: 10.1007/s10623-014-9956-2. Google Scholar

[11]

M. Delgado and H. Janwa, On the conjecture on APN functions, preprint, arXiv: 1207.5528Google Scholar

[12]

M. Delgado and H. Janwa, Further results on exceptional APN functions, 2013.Google Scholar

[13]

M. Delgado and H. Janwa, On the conjecture on APN functions and absolute irreducibility of polynomials, Des. Codes Crypt., (2016), 1-11. doi: 10.1007/s10623-015-0168-1. Google Scholar

[14]

M. Delgado and H. Janwa, Progress towards the conjecture on APN functions and absolutely irreducible polynomials, preprint, arXiv: 1602.02576Google Scholar

[15]

Y. EdelG. Kyureghyan and A. Pott, A new APN function which is not equivalent to a power mapping, IEEE Trans. Inf. Theory, 52 (2006), 744-747. doi: 10.1109/TIT.2005.862128. Google Scholar

[16]

E. Férard, R. Oyono and F. Rodier, Some more functions that are not APN infinitely often. The case of Gold and Kasami exponents, in Arithmetic, Geometry, Cryptography and Coding Theory, 2012, 27-36. doi: 10.1090/conm/574/11423. Google Scholar

[17]

W. Fulton, Algebraic Curves: An INTRODUCTION to Algebraic Geometry , 2008. Google Scholar

[18]

S. R. Ghorpade and G. Lachaud, Étale cohomology, lefschetz theorems and number of points of singular varieties over finite fields, Mosc. Math. J., 2 (2002), 589-631. Google Scholar

[19]

F. Hernando and G. McGuire, Proof of a conjecture on the sequence of exceptional numbers, classifying cyclic codes and APN functions, J. Algebra, 343 (2011), 78-92. doi: 10.1016/j.jalgebra.2011.06.019. Google Scholar

[20]

H. JanwaG. Mcguire and R. M. Wilson, Double-error-correcting cyclic codes and absolutely irreducible polynomials over gf (2), J. Algebra, 178 (1995), 665-676. doi: 10.1006/jabr.1995.1372. Google Scholar

[21]

H. Janwa and R. M. Wilson, Hyperplane sections of fermat varieties in p 3 in char. 2 and some applications to cyclic codes, in Int. Symp. Appl. Algebra Algebr. Algor. Error-Corr. Codes, Springer, 1993,180-194. doi: 10.1007/3-540-56686-4_43. Google Scholar

[22]

Y. Niho, Multi-Valued Cross-Correlation Functions between Two Maximal Linear Recursive Sequences, Ph. D thesis, Univ. Southern California, 1972.Google Scholar

[23]

K. Nyberg, Differentially uniform mappings for cryptography, in Worksh. Theory Appl. Crypt. Techn., Springer, 1993, 55-64. doi: 10.1007/3-540-48285-7_6. Google Scholar

[24]

A. Pott, Almost perfect and planar functions, Des. Codes Crypt., 78 (2016), 141-195. doi: 10.1007/s10623-015-0151-x. Google Scholar

[25]

F. Rodier, Borne sur le degré des polynômes presque parfaitement non-linéaires, Contemp. Math., 14 (2009), 169. doi: 10.1090/conm/487/09531. Google Scholar

[26]

F. Rodier, Some more functions that are not APN infinitely often. the case of Kasami exponents, preprint, arXiv: 1101.6033Google Scholar

show all references

References:
[1]

Y. Aubry, G. McGuire and F. Rodier, A few more functions that are not APN infinitely often, in Finite Fields: Theory and Applications, 2010, 23-31. doi: 10.1090/conm/518/10193. Google Scholar

[2]

R. D. BakerJ. H. Van Lint and R. M. Wilson, On the preparata and goethals codes, IEEE Trans. Inf. Theory, 29 (1983), 342-345. doi: 10.1109/TIT.1983.1056675. Google Scholar

[3]

T. P. BergerA. CanteautP. Charpin and Y. Laigle-Chapuy, On almost perfect nonlinear functions over $F_{2n}$, IEEE Trans. Inf. Theory, 52 (2006), 4160-4170. doi: 10.1109/TIT.2006.880036. Google Scholar

[4] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968. Google Scholar
[5]

C. Blondeau and K. Nyberg, Perfect nonlinear functions and cryptography, Finite Fields Appl., 32 (2015), 120-147. doi: 10.1016/j.ffa.2014.10.007. Google Scholar

[6]

L. BudaghyanC. Carlet and G. Leander, Constructing new APN functions from known ones, Finite Fields Appl., 15 (2009), 150-159. doi: 10.1016/j.ffa.2008.10.001. Google Scholar

[7]

E. Byrne and G. McGuire, Quadratic binomial APN functions and absolutely irreducible polynomials, preprint, arXiv: 0810.4523Google Scholar

[8]

C. CarletP. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for des-like cryptosystems, Des. Codes Crypt., 15 (1998), 125-156. doi: 10.1023/A:1008344232130. Google Scholar

[9]

F. Caullery, Polynomial functions of degree 20 which are APN infinitely often, preprint, arXiv: 1212.4638Google Scholar

[10]

F. Caullery, A new large class of functions not APN infinitely often, Des. Codes Crypt., 73 (2014), 601-614. doi: 10.1007/s10623-014-9956-2. Google Scholar

[11]

M. Delgado and H. Janwa, On the conjecture on APN functions, preprint, arXiv: 1207.5528Google Scholar

[12]

M. Delgado and H. Janwa, Further results on exceptional APN functions, 2013.Google Scholar

[13]

M. Delgado and H. Janwa, On the conjecture on APN functions and absolute irreducibility of polynomials, Des. Codes Crypt., (2016), 1-11. doi: 10.1007/s10623-015-0168-1. Google Scholar

[14]

M. Delgado and H. Janwa, Progress towards the conjecture on APN functions and absolutely irreducible polynomials, preprint, arXiv: 1602.02576Google Scholar

[15]

Y. EdelG. Kyureghyan and A. Pott, A new APN function which is not equivalent to a power mapping, IEEE Trans. Inf. Theory, 52 (2006), 744-747. doi: 10.1109/TIT.2005.862128. Google Scholar

[16]

E. Férard, R. Oyono and F. Rodier, Some more functions that are not APN infinitely often. The case of Gold and Kasami exponents, in Arithmetic, Geometry, Cryptography and Coding Theory, 2012, 27-36. doi: 10.1090/conm/574/11423. Google Scholar

[17]

W. Fulton, Algebraic Curves: An INTRODUCTION to Algebraic Geometry , 2008. Google Scholar

[18]

S. R. Ghorpade and G. Lachaud, Étale cohomology, lefschetz theorems and number of points of singular varieties over finite fields, Mosc. Math. J., 2 (2002), 589-631. Google Scholar

[19]

F. Hernando and G. McGuire, Proof of a conjecture on the sequence of exceptional numbers, classifying cyclic codes and APN functions, J. Algebra, 343 (2011), 78-92. doi: 10.1016/j.jalgebra.2011.06.019. Google Scholar

[20]

H. JanwaG. Mcguire and R. M. Wilson, Double-error-correcting cyclic codes and absolutely irreducible polynomials over gf (2), J. Algebra, 178 (1995), 665-676. doi: 10.1006/jabr.1995.1372. Google Scholar

[21]

H. Janwa and R. M. Wilson, Hyperplane sections of fermat varieties in p 3 in char. 2 and some applications to cyclic codes, in Int. Symp. Appl. Algebra Algebr. Algor. Error-Corr. Codes, Springer, 1993,180-194. doi: 10.1007/3-540-56686-4_43. Google Scholar

[22]

Y. Niho, Multi-Valued Cross-Correlation Functions between Two Maximal Linear Recursive Sequences, Ph. D thesis, Univ. Southern California, 1972.Google Scholar

[23]

K. Nyberg, Differentially uniform mappings for cryptography, in Worksh. Theory Appl. Crypt. Techn., Springer, 1993, 55-64. doi: 10.1007/3-540-48285-7_6. Google Scholar

[24]

A. Pott, Almost perfect and planar functions, Des. Codes Crypt., 78 (2016), 141-195. doi: 10.1007/s10623-015-0151-x. Google Scholar

[25]

F. Rodier, Borne sur le degré des polynômes presque parfaitement non-linéaires, Contemp. Math., 14 (2009), 169. doi: 10.1090/conm/487/09531. Google Scholar

[26]

F. Rodier, Some more functions that are not APN infinitely often. the case of Kasami exponents, preprint, arXiv: 1101.6033Google Scholar

[1]

Yves Edel, Alexander Pott. A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications, 2009, 3 (1) : 59-81. doi: 10.3934/amc.2009.3.59

[2]

Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Advances in Mathematics of Communications, 2010, 4 (1) : 69-81. doi: 10.3934/amc.2010.4.69

[3]

Kathy Horadam, Russell East. Partitioning CCZ classes into EA classes. Advances in Mathematics of Communications, 2012, 6 (1) : 95-106. doi: 10.3934/amc.2012.6.95

[4]

Wen-ming He, Jun-zhi Cui. The estimate of the multi-scale homogenization method for Green's function on Sobolev space $W^{1,q}(\Omega)$. Communications on Pure & Applied Analysis, 2012, 11 (2) : 501-516. doi: 10.3934/cpaa.2012.11.501

[5]

Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Addendum. Advances in Mathematics of Communications, 2011, 5 (3) : 543-546. doi: 10.3934/amc.2011.5.543

[6]

Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465

[7]

Katherine Morrison. An enumeration of the equivalence classes of self-dual matrix codes. Advances in Mathematics of Communications, 2015, 9 (4) : 415-436. doi: 10.3934/amc.2015.9.415

[8]

Liangjun Weng. The interior gradient estimate for some nonlinear curvature equations. Communications on Pure & Applied Analysis, 2019, 18 (4) : 1601-1612. doi: 10.3934/cpaa.2019076

[9]

Jyrki Lahtonen, Gary McGuire, Harold N. Ward. Gold and Kasami-Welch functions, quadratic forms, and bent functions. Advances in Mathematics of Communications, 2007, 1 (2) : 243-250. doi: 10.3934/amc.2007.1.243

[10]

Wacław Marzantowicz, Justyna Signerska. Firing map of an almost periodic input function. Conference Publications, 2011, 2011 (Special) : 1032-1041. doi: 10.3934/proc.2011.2011.1032

[11]

David Grant, Mahesh K. Varanasi. The equivalence of space-time codes and codes defined over finite fields and Galois rings. Advances in Mathematics of Communications, 2008, 2 (2) : 131-145. doi: 10.3934/amc.2008.2.131

[12]

Keonhee Lee, Kazuhiro Sakai. Various shadowing properties and their equivalence. Discrete & Continuous Dynamical Systems - A, 2005, 13 (2) : 533-540. doi: 10.3934/dcds.2005.13.533

[13]

Pankaj Kumar, Monika Sangwan, Suresh Kumar Arora. The weight distributions of some irreducible cyclic codes of length $p^n$ and $2p^n$. Advances in Mathematics of Communications, 2015, 9 (3) : 277-289. doi: 10.3934/amc.2015.9.277

[14]

Yongsheng Jiang, Huan-Song Zhou. A sharp decay estimate for nonlinear Schrödinger equations with vanishing potentials. Communications on Pure & Applied Analysis, 2010, 9 (6) : 1723-1730. doi: 10.3934/cpaa.2010.9.1723

[15]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[16]

Luis Barreira, Liviu Horia Popescu, Claudia Valls. Generalized exponential behavior and topological equivalence. Discrete & Continuous Dynamical Systems - B, 2017, 22 (8) : 3023-3042. doi: 10.3934/dcdsb.2017161

[17]

Andres del Junco, Daniel J. Rudolph, Benjamin Weiss. Measured topological orbit and Kakutani equivalence. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 221-238. doi: 10.3934/dcdss.2009.2.221

[18]

Wenxiong Chen, Congming Li. A priori estimate for the Nirenberg problem. Discrete & Continuous Dynamical Systems - S, 2008, 1 (2) : 225-233. doi: 10.3934/dcdss.2008.1.225

[19]

Zhiyou Wu, Fusheng Bai, Guoquan Li, Yongjian Yang. A new auxiliary function method for systems of nonlinear equations. Journal of Industrial & Management Optimization, 2015, 11 (2) : 345-364. doi: 10.3934/jimo.2015.11.345

[20]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (9)
  • HTML views (10)
  • Cited by (0)

Other articles
by authors

[Back to Top]