|
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 F2n nach
F2q 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:
-
- 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?
- Insbesondere für den Fall (n,q) = (4,2):
Existieren krumme Abbildungen?
- 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.
- 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.
Vorlesungen Datenschutz und Datensicherheit,
Kryptologie I - III
Wintersemester 2001/2002 - Sommersemester 2003, Fachbereich Mathematik
Johannes-Gutenberg-Universität Mainz
Klaus Pommerening, letzte Änderung: 16. Februar 2003.
E-Mail an
Pommerening@imsd.uni-mainz.de.