Boolean and vectorial functions : a design-theoretic point of view

Abstract

In der vorliegenden Arbeit untersuchen wir verschiedene Klassen kryptografisch bedeutsamer Funktionen wie beispielsweise bent, plateaued und differentially uni-form Funktionen sowie aus diesen Funktionen konstruierte Inzidenzstrukturen. Zunächst untersuchen wir vektorielle bent Funktionen in wenigen Variablen. Wir klassifizieren und enumerieren alle vektoriellen bent Funktionen in sechs Variablen. Damit vervollständigen wir die Klassifizierung perfekter nichtlinea-rer Funktionen in sechs Variablen vom algebraischen Grad höchstens drei und die Liste der bent Funktionen in sechs Variablen. Darüber hinaus zeigen wir, dass im Gegensatz zu Booleschen bent Funktionen nicht alle vektoriellen bent Funktionen in sechs Variablen bis auf EA-Äquivalenz durch Maiorana-McFarland und Desarguesian partial spread Konstruktionen beschrieben werden können. Wir untersuchen ferner, ob sich bestimmte Eigenschaften von Booleschen und vektoriellen bent Funktionen sowie deren Verallgemeinerungen in den zugehö-rigen Inzidenzstrukturen widerspiegeln, die in einigen Fällen zur gut erforsch-ten Klasse der kombinatorischen Designs gehören. In diesem Zusammenhang stellen wir eine neue Konstruktion von Inzidenzstrukturen aus Booleschen und vektoriellen Funktionen vor und präsentieren zwei Anwendungen dieser Objek-te zur Untersuchung von bent Funktionen. Die erste Anwendung ist eine de-signtheoretische Charakterisierung von bent Funktionen innerhalb der plateau-ed Funktionen, die zweite ist eine kombinatorische Interpretation des Erweiter-barkeitsproblems für bent Funktionen. Wir stellen ferner eine große Klasse fast perfekt-nichtlinearer Funktionen (APN-Funktionen) vor, deren lineare Codes 2-Designs tragen. Aus diesem Ergebnis entwickeln wir eine neue hinreichende Bedingung für die CCZ-Nichtäquivalenz von APN-Funktionen mit dem klassi-schen Walsh-Spektrum zu quadratischen Funktionen. Zum Abschluss untersuchen wir kubische Boolesche bent Funktionen. Wir beweisen, dass im Gegensatz zu den Fällen mit n = 6 und n = 8 Variablen die Maiorana-McFarland Konstruktion für alle n ≥ 10 nicht die gesamte Klasse der kubischen bent Funktionen in n Variablen beschreiben kann. Außerdem zeigen wir für unendlich viele n ≥ 10 die Existenz kubischer bent Funktionen in n Variablen, die homogen sind, keine affinen Ableitungen haben und nicht in der abgeschlossenen Maiorana-McFarland Klasse sind.

Abstract In this thesis, we investigate various classes of cryptographically significant func-tions, including bent, plateaued and differentially uniform functions, as well as the incidence structures constructed from these mappings. First, we investigate vectorial bent functions in a small number of variables. We classify and enumerate all vectorial bent functions in six variables. Thereby, we complete the classification of perfect nonlinear functions in six variables of algebraic degree at most three and the enumeration of bent functions in six vari-ables. Moreover, we show that all vectorial bent functions in six variables, in con-trast to the Boolean bent functions, cannot be described, up to EA-equivalence, by Maiorana-McFarland and Desarguesian partial spread constructions. Furthermore, we investigate whether certain properties of Boolean and vecto-rial bent functions, as well as their generalizations, may be reflected by the asso-ciated incidence structures, which in some cases, fall into the well-studied class of combinatorial designs. In particular, we introduce a new construction of inci-dence structures from Boolean and vectorial functions called nonvanishing flats and provide two applications of this object to study bent functions. The first is a design-theoretic characterization of bent functions among plateaued functions, and the second is a combinatorial interpretation of the extendability problem for bent functions. We also provide a large class of APN functions, whose linear codes support 2-designs. Using this result, we give a new sufficient condition for APN functions with the classical Walsh spectrum to be CCZ-inequivalent to quadratic functions. Finally, we investigate cubic Boolean bent functions. We prove that, in con-trast to the cases of n = 6 and n = 8 variables, the Maiorana-McFarland con-struction does not describe the whole class of cubic bent functions in n variables for all n ≥ 10. Moreover, we show that cubic bent functions in n variables that are homogeneous, have no affine derivatives and are not in the completed Maiorana-McFarland class exist for infinitely many n ≥ 10.