The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is still unknown. Those of Kasami, Niho and Welch functions are known, but not the precise values of their Walsh transform, with rare exceptions. One promising approach that could lead to the resolution of these problems is to consider alternative representations of the functions in questions. We derive alternative representations for the infinite APN monomial families. We show how the Niho, Welch, and Dobbertin functions can be represented as the composition xi x1/j of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can be used to represent the functions in this way. We investigate compositions x i L x1/j for a linear polynomial L , show how the Kasami functions in odd dimension can be expressed in this way with i=j being a Gold exponent and compute all APN functions of this form for n ≤ 9 and for L with binary coefficients, thereby showing that our theoretical constructions exhaust all possible cases. We present observations and data on power functions with exponent sum i = 1 k-1 2 2ni - 1 which generalize the inverse and Dobbertin families. We present data on the Walsh spectrum of the Dobbertin function for n ≤ 35 , and conjecture its exact form. As an application of our results, we determine the exact values of the Walsh transform of the Kasami function at all points of a special form. Computations performed for n≤q 21 show that these points cover about 2/3 of the field.

On Two Fundamental Problems on APN Power Functions / Budaghyan, L.; Calderini, M.; Carlet, C.; Davidova, D.; Kaleyski, N. S.. - In: IEEE TRANSACTIONS ON INFORMATION THEORY. - ISSN 0018-9448. - 68:5(2022), pp. 3389-3403. [10.1109/TIT.2022.3147060]

On Two Fundamental Problems on APN Power Functions

Calderini M.;
2022-01-01

Abstract

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is still unknown. Those of Kasami, Niho and Welch functions are known, but not the precise values of their Walsh transform, with rare exceptions. One promising approach that could lead to the resolution of these problems is to consider alternative representations of the functions in questions. We derive alternative representations for the infinite APN monomial families. We show how the Niho, Welch, and Dobbertin functions can be represented as the composition xi x1/j of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can be used to represent the functions in this way. We investigate compositions x i L x1/j for a linear polynomial L , show how the Kasami functions in odd dimension can be expressed in this way with i=j being a Gold exponent and compute all APN functions of this form for n ≤ 9 and for L with binary coefficients, thereby showing that our theoretical constructions exhaust all possible cases. We present observations and data on power functions with exponent sum i = 1 k-1 2 2ni - 1 which generalize the inverse and Dobbertin families. We present data on the Walsh spectrum of the Dobbertin function for n ≤ 35 , and conjecture its exact form. As an application of our results, we determine the exact values of the Walsh transform of the Kasami function at all points of a special form. Computations performed for n≤q 21 show that these points cover about 2/3 of the field.
2022
5
Budaghyan, L.; Calderini, M.; Carlet, C.; Davidova, D.; Kaleyski, N. S.
On Two Fundamental Problems on APN Power Functions / Budaghyan, L.; Calderini, M.; Carlet, C.; Davidova, D.; Kaleyski, N. S.. - In: IEEE TRANSACTIONS ON INFORMATION THEORY. - ISSN 0018-9448. - 68:5(2022), pp. 3389-3403. [10.1109/TIT.2022.3147060]
File in questo prodotto:
File Dimensione Formato  
On_Two_Fundamental_Problems_on_APN_Power_Functions.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 812.3 kB
Formato Adobe PDF
812.3 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/352985
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact