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.

[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.

[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.

[4] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.
[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.

[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.

[7]

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

[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.

[9]

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

[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.

[11]

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

[12]

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

[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.

[14]

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

[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.

[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.

[17]

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

[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.

[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.

[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.

[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.

[22]

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

[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.

[24]

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

[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.

[26]

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

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.

[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.

[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.

[4] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.
[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.

[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.

[7]

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

[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.

[9]

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

[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.

[11]

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

[12]

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

[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.

[14]

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

[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.

[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.

[17]

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

[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.

[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.

[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.

[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.

[22]

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

[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.

[24]

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

[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.

[26]

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

[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]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (6)
  • HTML views (7)
  • Cited by (0)

Other articles
by authors

[Back to Top]