S-Boxen mit herausragenden Eigenschaften in Bezug auf Kryptographische Stärke und Implementierung

• Antragsteller: Dr. Christof Beierle; Professor Dr. Gregor Leander
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme ; Theoretische Informatik
• Förderung: Förderung von 2018 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 411879806

• Erstellungsjahr: 2022

Zusammenfassung der Projektergebnisse

Up to equivalence, we found 19,289 new functions with optimal differential uniformity (i.e., APN functions) over F8 , 35 new APN functions over F9 , and 5 new APN functions over F10 . To put 2 2 2 those numbers into context, as an example, there were 8,192 APN functions in dimension eight (up to equivalence) known before the start of our project. For the majority of those functions, we exploited the existence of non-trivial linear self-equivalences in order to find them. Surprisingly, besides functions with low linearity, we found new APN and differentially 4-uniform functions with extremely high linearity. In particular, in dimension n = 8, we found 4 quadratic APN functions (up to equivalence) with the theoretically highest possible value on its linearity, i.e., 2n−1 . We further found new examples of differentially 4-uniform permutations with linearity 2n . Although such functions are not relevant for cryptographic applications, they are quite interesting from a theoretical point of view. So far, we only knew the existence of quadratic APN functions with linearity 2n−1 in dimension n ≤ 6. For n = 8, we managed to obtain a full classification of quadratic APN functions with linearity 2n−1 . Two out of the 35 APN functions in dimension n = 9 are permutations and those are the first new APN permutations (up to equivalence) found since 2010. We found a simple trivariate representation of the two new APN permutations. More precisely, we showed that the two permutations can be represented (within their equivalence classes) as permutations Cu : (F2m )3 → (F2m )3 , (x, y, z) → (x3 + uy 2 z, y 3 + uxz 2 , z 3 + ux2 y), where m = 3 and u ∈ F23 \ {0, 1} such that the two permutations correspond to different choices of u. We then proved that, for m ≥ 3 being a multiple of 3 and u ∈ F2m not being a 7-th power, the differential uniformity of Cu is bounded above m by 8 and linearity is bounded above by 81+⌊ 2 ⌋ . Because of its rather simple form only involving arithmetic operations on the smaller field F23 , we expect that our new APN permutations in dimension n = 9 allow for a more efficient implementation compared to power APN functions, making those suitable candidates for cryptographic S-boxes to be used in a block cipher or cryptographic permutation.

Projektbezogene Publikationen (Auswahl)

• 4-uniform permutations with null nonlinearity. Cryptography and Communications, 12(6), 1133-1141.
  Beierle, Christof & Leander, Gregor
  
• Alzette: A 64-Bit ARX-box. Lecture Notes in Computer Science, 419-448. Springer International Publishing.
  Beierle, Christof; Biryukov, Alex; Cardoso, dos Santos Luan; Großschädl, Johann; Perrin, Léo; Udovenko, Aleksei; Velichkov, Vesselin & Wang, Qingju
  
• Linearly Self-Equivalent APN Permutations in Small Dimension. IEEE Transactions on Information Theory, 67(7), 4863-4875.
  Beierle, Christof; Brinkmann, Marcus & Leander, Gregor
  
• A further study of quadratic APN permutations in dimension nine. Finite Fields and Their Applications, 81, 102049.
  Beierle, Christof; Carlet, Claude; Leander, Gregor & Perrin, Léo
  
• New Instances of Quadratic APN Functions. IEEE Transactions on Information Theory, 68(1), 670-678.
  Beierle, Christof & Leander, Gregor
  
• Trims and extensions of quadratic APN functions. Designs, Codes and Cryptography, 90(4), 1009-1036.
  Beierle, Christof; Leander, Gregor & Perrin, Léo