Motivierender Vortrag über Grundlagen der Kryptographie

10

Diese Frage entspricht dem inspirierenden Gespräch für Schüler des letzten Schuljahres . Mein Ph.D. Der Berater bat mich, einen inspirierenden Vortrag für den neuen M.Sc. Studenten. Das Thema sind Grundlagen der Kryptographie , die am besten durch Goldreichs Buch veranschaulicht werden . Der Vortrag wird ungefähr eine Stunde dauern, und ich möchte die Schüler mit den Hauptkonstrukten vertraut machen (wie Einwegfunktionen / Permutationen, Pseudozufallsgeneratoren, wissensfreie Beweise, Verschlüsselungs- / Signaturschemata usw.) und gelöst und ungelöste Probleme auf dem Gebiet.

Ich möchte das Gespräch sehr motivierend halten . Das Hauptproblem ist zweierlei:

  1. Grundlagen der Kryptographie erfordern ein sehr gutes Verständnis der Theorie der rechnerischen Komplexität . Leider ist der M.Sc. Studenten haben keinen Kurs im Zusammenhang mit dieser Theorie bestanden.
  2. Ich muss einige Probleme als mögliche Themen für einen M.Sc. These. Während es auf dem Gebiet viele ungelöste Probleme gibt, sind die meisten für einen M.Sc. Schüler.

Vorschläge sind herzlich willkommen. Außerdem bin ich sehr an Hinweisen auf ähnliche Gespräche interessiert.


Edit: Ich fand die Liste der Goldreich-Studenten äußerst inspirierend. Ich werde nach anderen solchen Listen suchen, aber Sie können mir helfen, wenn Sie ähnliche Listen kennen. Siehe auch: Entmystifizierung der Masterarbeit und Forschung im Allgemeinen: Die Geschichte einiger Masterarbeiten .

MS Dousti
quelle

Antworten:

12

Da Sie sich nicht auf Kenntnisse der Komplexitätstheorie verlassen können, müssen Sie den Paradigmenwechsel von Sicherheit durch Dunkelheit zu Sicherheit durch Unlösbarkeit hervorheben, indem Sie die Idee vertreten, dass einige Probleme schwer effizient zu lösen sind. Dies beseitigt natürlich die vielen Probleme, die mit den Impagliazzo-Welten der Unlösbarkeit verbunden sind, aber es gibt einen Eindruck von der Funktionsweise moderner Krypto.

Für ZKP, die wirklich großartig sind, gibt es viele Möglichkeiten, die Grundideen intuitiv zu vermitteln. Siehe zum Beispiel meine Antwort auf MO sowie die lustige Geschichte von Ali Baba und den 40 Dieben . Während diese ursprünglich für eine jüngere Menge konzipiert wurden, funktionieren sie in jedem Alter gut, um die richtige Intuition zu vermitteln.

Suresh Venkat
quelle
@ Suresh: Vielen Dank. Irgendwelche Ideen zum zweiten Thema (Motivation ungelöster Probleme auf M.Sc.-Ebene)?
MS Dousti
1
Die beiden Links sind gleich.
Tsuyoshi Ito
das ist eine schwierige Frage. Es gibt nicht viele Probleme, die auf dieser Ebene gelöst werden können, ohne die Komplexität zu kennen.
Suresh Venkat
@Suresh: Ja, das war mein Problem, seit ich anfing, Vorträge zu diesem Thema zu halten. Wie auch immer, ich muss Kompromisse eingehen; Sie können also davon ausgehen, dass die Leute die Komplexität irgendwie gut verstehen! Wie kann ich ihnen dann motivierende Probleme für M.Sc. These?
MS Dousti
Ich weiß sehr wenig über Krypto, also :(. In der Geometrie gibt es eine schöne Liste offener Probleme. Vielleicht sollten Sie die Liste der offenen Fragen durchgehen, die hier vor einiger Zeit veröffentlicht wurde.
Suresh Venkat
4

Ehrlich gesagt scheint es mir, dass ein Vortrag auf der Ebene (und mit dem Schwerpunkt) von Goldreichs Buch über einen ankommenden MSc-Studenten hinausgehen wird. (Nullwissen als "Hauptkonstrukt" der Kryptographie zu bezeichnen, während die Verschlüsselung mit privatem Schlüssel weggelassen wird, ist sicherlich ein nicht standardmäßiger Gesichtspunkt.)

Ich würde einen (etwas) stärker angewandten Fokus auf die Linien des Katz-Lindell-Buches vorschlagen.

user686
quelle