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.4523 Google 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.4638 Google 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.5528 Google 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.02576 Google 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.6033 Google 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.4523 Google 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.4638 Google 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.5528 Google 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.02576 Google 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.6033 Google Scholar

[1]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002

[2]

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

[3]

Zemer Kosloff, Terry Soo. The orbital equivalence of Bernoulli actions and their Sinai factors. Journal of Modern Dynamics, 2021, 17: 145-182. doi: 10.3934/jmd.2021005

[4]

Xinqun Mei, Jundong Zhou. The interior gradient estimate of prescribed Hessian quotient curvature equation in the hyperbolic space. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1187-1198. doi: 10.3934/cpaa.2021012

[5]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709

[6]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018

[7]

Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021, 16 (2) : 187-219. doi: 10.3934/nhm.2021004

[8]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[9]

Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019

[10]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070

[11]

Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020

[12]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011

[13]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[14]

Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $ \mathbb{F}_q $-linear $ \mathbb{F}_{q^t} $-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072

[15]

Christian Meyer, Stephan Walther. Optimal control of perfect plasticity part I: Stress tracking. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021022

[16]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007

[17]

Jia Li, Junxiang Xu. On the reducibility of a class of almost periodic Hamiltonian systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3905-3919. doi: 10.3934/dcdsb.2020268

[18]

Francisco Braun, Jaume Llibre, Ana Cristina Mereu. Isochronicity for trivial quintic and septic planar polynomial Hamiltonian systems. Discrete & Continuous Dynamical Systems, 2016, 36 (10) : 5245-5255. doi: 10.3934/dcds.2016029

[19]

Montserrat Corbera, Claudia Valls. Reversible polynomial Hamiltonian systems of degree 3 with nilpotent saddles. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3209-3233. doi: 10.3934/dcdsb.2020225

[20]

Raphaël Côte, Frédéric Valet. Polynomial growth of high sobolev norms of solutions to the Zakharov-Kuznetsov equation. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1039-1058. doi: 10.3934/cpaa.2021005

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (134)
  • HTML views (60)
  • Cited by (0)

Other articles
by authors

[Back to Top]