Motywujące rozmowy na temat podstaw kryptografii

10

To pytanie jest w tym samym duchu, co inspirująca rozmowa dla uczniów ostatniej klasy liceum . Mój doktorat doradca poprosił mnie o przeprowadzenie inspirującej rozmowy dla nowego mgr inż. studenci Tematem są podstawy kryptografii , co najlepiej ilustruje książka Goldreicha . Rozmowa zajmie około godziny, a ja chcę zapoznać studentów z głównymi konstrukcjami (takimi jak funkcje / permutacje jednokierunkowe, generatory pseudolosowe, losowe dowody zerowej wiedzy, schematy szyfrowania / podpisu itp.) Oraz rozwiązane i nierozwiązane problemy w terenie.

Chcę, aby rozmowa była bardzo motywująca . Główny problem jest dwojaki:

  1. Podstawy kryptografii wymagają bardzo dobrego zrozumienia teorii złożoności obliczeniowej . Niestety, mgr inż. studenci nie zaliczyli żadnego przedmiotu związanego z tą teorią.
  2. Muszę przedstawić niektóre problemy, jak to możliwe, dla mgr inż. Praca dyplomowa. Podczas gdy istnieje wiele nierozwiązanych problemów w terenie, większość z nich jest zbyt trudna dla magistra. student.

Sugestie są mile widziane. Ponadto jestem bardzo zainteresowany wskazówkami do podobnych rozmów.


Edit: Znalazłem listy studentów Goldreich za niezwykle inspirujące. Będę szukał innych takich list, ale możesz mi pomóc, jeśli znasz podobne listy. Zobacz także: Demystifying the Master Thesis and Research in General: The Story of Some Master Theses .

MS Dousti
źródło

Odpowiedzi:

12

Ponieważ nie możesz polegać na znajomości teorii złożoności, musisz podkreślić zmianę paradygmatu z bezpieczeństwa przez niejasność na bezpieczeństwo przez trudność, poprzez postawienie poglądu, że niektóre problemy są trudne do skutecznego rozwiązania. To oczywiście pomija wiele problemów związanych ze światem impagliazzo trudności, ale daje posmak działania współczesnego krypto.

w przypadku ZKP, które są naprawdę niesamowite, istnieje wiele sposobów intuicyjnego przekazywania podstawowych pomysłów. Zobacz na przykład moją odpowiedź na temat MO , a także zabawną historię Ali Baby i 40 złodziei . Choć pierwotnie zostały zaprojektowane dla młodszego tłumu, działają dobrze w każdym wieku, aby przekazać właściwą intuicję.

Suresh Venkat
źródło
@Suresh: Wielkie dzięki. Jakieś pomysły na drugą kwestię (motywowanie nierozwiązanych problemów na poziomie mgr)?
MS Dousti,
1
Dwa linki są takie same.
Tsuyoshi Ito,
to trudne. nie ma wielu problemów, które można rozwiązać na tym poziomie bez znajomości złożoności.
Suresh Venkat,
@Suresh: Tak, to był mój problem, odkąd zacząłem mówić na ten temat. W każdym razie muszę iść na kompromis; więc możesz bezpiecznie założyć, że ludzie dobrze rozumieją złożoność! W jaki sposób mogę im dać motywujące problemy dla mgr inż. Praca dyplomowa?
MS Dousti,
Bardzo mało wiem o kryptografii, więc :(. W geometrii jest ładna lista otwartych problemów. Może powinieneś przejrzeć listę otwartych pytań, która została tu opublikowana jakiś czas temu.
Suresh Venkat
4

Szczerze mówiąc, wydaje mi się, że wykład na poziomie (z naciskiem) książki Goldreicha będzie poza przybywającym studentem mgr. (Nazywanie zerowej wiedzy „główną konstrukcją” kryptografii, pomijając szyfrowanie kluczem prywatnym, jest z pewnością niestandardowym punktem widzenia.)

Sugerowałbym (nieco) bardziej skoncentrowany nacisk na linijki książki Katz-Lindell.

użytkownik686
źródło