Equivalence problems of almost perfect nonlinear functions and disjoint difference families

Abstract

In der vorliegenden Arbeit untersuchen wir Äquivalenzprobleme zweier Objekte aus der diskreten Mathematik: disjunkte Differenzfamilien und fast perfekt-nichtlineare Funktionen (APN-Funktionen, aus dem Englischen: almost perfect nonlinear). Eine disjunkte Differenzfamilie ist eine Sammlung disjunkter Teilmengen gleicher Kardinalität einer Gruppe G, sodass jedes Nichtnullelement aus G gleich häufig als Differenz zweier Elemente derselben Teilmenge auftritt. Differenzfamilien spielen eine wichtige Rolle in der Designtheorie, finden aber auch in der Kodierungstheorie Anwendung. Wird eine neue Differenzfamilienkonstruktion vorgestellt, so stellt sich natürlicherweise die Frage, ob die resultierenden Objekte wirklich neu sind oder ob sie isomorph zu bereits bekannten Differenzfamilien sind. In dieser Arbeit untersuchen wir drei solche Isomorphieprobleme: Wir vergleichen eine klassische Konstruktion in endlichen Körpern (Wilson 1972) mit drei Konstruktionen in Galoisringen – zwei davon sind bekannt (Davis, Huczynska und Mullen 2017, sowie Momihara 2017), die dritte führen wir neu ein. Diese Isomorphieprobleme sind besonders interessant, da alle drei Galoisring-Konstruktionen auf demselben Ansatz wie Wilsons Konstruktion basieren. Indem wir ausgewählte Schnittzahlen der assoziierten kombinatorischen Designs bestimmen, zeigen wir, dass die beiden bekannten Differenzfamilien und Wilsons Differenzfamilien in fast allen Fällen nichtisomorph sind. Für unsere neuen Differenzfamilien geben wir eine partielle Lösung des Isomorphieproblems an. APN-Funktionen sind vektorielle Boolesche Funktionen von Fn2nach Fn2 mit optimalen differenziellen Eigenschaften. Sie wurden 1994 von Nyberg eingeführt. Die Auseinandersetzung mit diesen Funktionen wird primär aus der Kryptographie heraus motiviert, denn APN-Funktionen bieten den bestmöglichen Schutz gegen differenzielle Kryptoanalyse. Weitere Anwendungen finden sich in der Kodierungstheorie und in der endlichen Geometrie. Obwohl APN-Funktionen seit ihrer Einführung intensiv untersucht wurden, sind bisher nur wenige inäquivalente APN-Funktionen bekannt: einige sporadische Beispiele, mehrere APN-Potenzfunktionen und gegenwärtig 13 unendliche Familien von APN-Nichtpotenzfunktionen. Gänzlich offen ist die Frage, wie viele inäquivalente APN-Funktionen es auf Fn2 für ein gegebenes n gibt. Auch Computersuchen liefern nur für n 8 zufriedenstellende Resultate. In der vorliegenden Arbeit präsentieren wir die erste nichttriviale untere Schranke für die Anzahl der inäquivalenten APN-Funktionen auf Fn2 für gerade n = 2m. Für zwei sorgfältig ausgewählte unendliche Familien von APN-Funktionen, die auf Zhou und Pott (2013) und Taniguchi (2019) zurückgehen, ermitteln wir jeweils exakt, unter welchen Bedingungen die Funktionen jeder dieser Klassen äquivalent sind. Aus diesen Resultaten leiten wir ab, dass es auf F2m 2 mindestens '(m) 2 l 2m+1 3m m inäquivalente APN-Funktionen gibt, wobei ' die Eulersche Phi-Funktion bezeichne. Darüber hinaus präsentieren wir einige Resultate über Gold APN-Funktionen und über eine unendliche Familie von APN-Funktionen, die von Carlet (2011) eingeführt wurde. Zudem bestimmen wir die Automorphismengruppen aller genannten APNFunktionen.

In this thesis, we study equivalence problems of two objects from discrete mathematics: disjoint difference families and almost perfect nonlinear (APN) functions. Disjoint difference families are collections of same-sized disjoint subsets of a group G such that each nonzero element of G occurs equally often as the difference of two elements from the same subset. Difference families play an important role in design theory, and they also have applications in coding theory. Whenever a new construction of a difference family is presented, it is a natural question to ask whether the construction provides completely new objects or whether its instances are isomorphic to already known difference families. In this thesis, we study three such isomorphism problems: we compare each of three different constructions of difference families in Galois rings, two of which were introduced by Davis, Huczynska, and Mullen (2017) and by Momihara (2017), and one of which is new, with a classical construction in finite fields by Wilson (1972). These isomorphism problems are particularly intriguing as Wilson’s construction served as an inspiration for all three Galois ring constructions. To compare such difference families from different groups, we study the block intersection numbers of their associated combinatorial designs. For both known difference families, we show that they are in almost all cases nonisomorphic to Wilson’s difference families. For our new difference family, we present a partial solution to the isomorphism problem. APN functions are vectorial Boolean functions from Fn2 to Fn2 with optimal differential properties. They were introduced in 1994 by Nyberg. The main motivation to study these functions lies in cryptography as APN functions provide the strongest resistance against differential cryptanalysis, but they also have applications in coding theory and finite geometry. Although APN functions have been extensively studied since their introduction, only a limited number of inequivalent APN functions are known: except for some sporadic examples, we know several power APN functions and currently 13 infinite families of non-power APN functions. Up to now, it has been completely unknown, how many inequivalent APN functions exist on Fn2 for any given n. Satisfactory results from computer searches only exist for n 8. In this thesis, we present the first nontrivial lower bound on the total number of inequivalent APN functions on Fn2where n = 2m is even. We carefully pick two infinite families of non-power APN functions introduced by Zhou and Pott (2013) and Taniguchi (2019), and we completely determine the equivalence of the instances of these classes. We derive that on F2m 2 , there exist at least '(m) 2 l 2m+1 3m m inequivalent APN functions, where ' denotes Euler’s totient function. We add some results about Gold APN functions and about an infinite family of APN functions by Carlet (2011), and we determine the automorphism groups of all these APN functions.