Experimentelle Mathematik; Durchrechnen von Beispielen (mit
Computerhilfe), Gewinnen und evtl. Beweisen von Gesetzmäßigkeiten.
Evtl. Ergänzung durch Literatur-Aufarbeitung.
Problembereich:
Bei fester Dimension n des Urbildraums und q des Bildraums
ist das minimale lineare bzw. differenzielle Potenzial von BOOLEschen
Abbildungen von F2n nach
F2q nur in manchen Fällen bekannt.
Die »kleinsten« unbekannten Fälle sind
für das lineare Potenzial: (n,q) = (3,5), (4,3), (5,6),
(6,4),
für das differenzielle Potenzial: (n,q) = (5,1) bis (5,4),
(6,4), (7,1).
Ansatz für »ganz kleine« n und q: Wie weit kommt
man mit Exhaustion, d. h. vollständigem Durchrechnen aller
Abbildungen mit Hilfe des Programms bma?
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?
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?
Zeichnen sich beim Durchrechnen der Beispiele allgemeine
Gesetzmäßigkeiten ab? Lassen sich diese beweisen?
Bei festem n: Ab welchem q ist das lineare Potenzial
=1?
Wie sehen die Minima aus, wenn man sich auf balancierte Abbildungen
beschränkt?
Vermutung von MATSUI: Im Fall n = q ist für bijektive
Abbildungen sowohl das lineare als auch das differenzielle Potenzial
mindestens gleich 1/2n-2. Falls n gerade ist,
gilt das auch für das lineare Potenzial beliebiger Abbildungen.
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.
Patterson/Wiedemann (IEEE Transactions on Information Theory 29 (1983)
und 36 (1990)): Rekord der Nichtlinearität im Fall n = 15,
q = 1.
Wadayama u. a. (Designs, Codes and Cryptography 2001):
Aktuelle »Weltrekorde« für die Nichtlinearität
(also implizit auch für das lineare Potenzial) bei n, q <= 8.
![[JoGu]](../JOGUUNM1-opti.gif)