Motywujące rozmowy na temat podstaw kryptografii

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 .

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ę.

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.