Diplomthema Kryptologie Optimierung der Nichtlinearität

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Typ der Arbeit:

Experimentelle Mathematik; Durchrechnen von Beispielen (mit Computerhilfe), Gewinnen und evtl. Beweisen von Gesetzmäßigkeiten. Evtl. Ergänzung durch Literatur-Aufarbeitung. [Mit dieser Ergänzung auch für zwei Arbeiten ausreichend.]

Problembereich:

Bei fester Dimension n des Urbildraums und q des Bildraums ist das minimale lineare bzw. differenzielle Potenzial von BOOLEschen Abbildungen von F₂ⁿ nach F₂^q nur in manchen Fällen bekannt. Die »kleinsten« unbekannten Fälle sind

• für das lineare Potenzial: (n,q) = (3,4), (4,2), (4,4), (5,1),
• für das differenzielle Potenzial: (n,q) = (4,2), (4,3), (5,1).

Einstieg:

Skriptum »Linearitätsmaße für BOOLEsche Funktionen«, siehe Vorlesung Kryptologie II.

Literatur:

Siehe das genannte Skriptum.

Fragen und Aufgaben:

1. Ansatz für kleine n und q: Klassifikation der Abbildungen bis auf affine Äquivalenz; explizite Bestimmung des linearen und differenziellen Potenzials für jeweils eine »Normalform« pro Äquivalenzklasse (= Bahn der Gruppenoperation). Lässt sich die Klassifikation durch ein Programm unterstützen?
2. Insbesondere für den Fall (n,q) = (4,2): Existieren krumme Abbildungen?
3. Falls die Menge der Äquivalenzklassen nicht mehr beherrschbar ist: Wie sieht es für ausgewählte spezielle und für zufällig gewählte Abbildungen aus?
4. Zeichnen sich beim Durchrechnen der Beispiele allgemeine Gesetzmäßigkeiten ab? Lassen sich diese beweisen?
5. Bei festem n: Ab welchem q ist das lineare Potenzial =1?
6. Wie sehen die Minima aus, wenn man sich auf balancierte Abbildungen beschränkt?
7. Vermutung von MATSUI: Im Fall n = q ist für bijektive Abbildungen sowohl das lineare als auch das differenzielle Potenzial mindestens gleich 1/2^n-2. Falls n gerade ist, gilt das auch für das lineare Potenzial beliebiger Abbildungen.
8. Evtl. Ergänzung durch Literatur-Aufbereitung:
   • Dobbertin (FSE 94): Maximale Nichtlinearität balancierter Funktionen im Fall n = 6, 8, 9.
   • Millan u. a. (SAC 97): Maximale Nichtlinearität im Fall n = 3, 5, 7, q = 1.
   • siehe auch Filiol/Fontaine (EUROCRYPT 98).
   • Sarkar/Maitra (EUROCRYPT 2000): Konstruktion balancierter Funktionen für n ³ 15, q = 1, mit hoher Nichtlinearität.
   • Cheon/Chee/Park (EUROCRYPT 99): Untere Schranke der Nichtlinearität (also obere Schranke für das lineare Potenzial) rationaler Abbildungen durch Zählen von Punkten auf elliptischen Kurven im Fall n = q.

E-Mail an Pommerening@imsd.uni-mainz.de.