S. Dziembowski - Cwiczenia z Teorii Informacji

S. Dziembowski: Ćwiczenia z Teorii Informacji
sem.letni, rok akad. 2004/05

Oto wykaz tematów "kryptograficznych", które poruszaliśmy na ćwiczeniach, a które nie pojawiły się na wykładzie (kolejność w miarę chronologiczna):

strona wykładu

Idealna tajność (perfect secrecy); Szyfr Vernama (one-time pad) i pesymistczne twierdzenie Shannona (o tym, że one-time pad jest optymalny w klasie szyfrów zapewiających idealną tajność)
(patrz np.: Stefan Wolf "Information-Theoretically and Computationally Secure Key Agreement in Cryptography" [ps], Chapter 3)
Protokół Shamira Podziału Sekretu (Shamir's Secret Sharing)
(to można znaleźć w wielu miejscach, np. [link])
Idealnie bezpieczny protokół uzgadaniania klucza:

Tw. Maurera
(patrz Ueli Maurer "Secret Key Agreement by Public Discussion" [ps, pdf], Theorem 3)
uzgadanianie klucza w Modelu z Ograniczoną Pamięcią

protokół uzgadaniania klucza (tego chyba nigdzie nie ma napisanego, chodzi o ten pomysł w którym randomizator jest przedstawiony jako macierz kwadratowa, jeden z graczy zapamiętuje kolumne, a drugi - wiersz).
wynik negatywny
(patrz Stefan Dziembowski and Ueli Maurer "On Generating the Initial Key in the Bounded-Storage Model" [link], Rozdział 3), to było zadanie, którego nie skończyliśmy

Ekstraktory losowości, min-entropia i statystyczny dystans między rozkładami (delta(P,Q)) i odległość od rozkladu jednostajnego (d(P)) (w literaturze używanych jest wiele różnych oznaczeń). Uniwersalne funkcje haszujące. Literatura:

R. Shaltiel "Recent developments in Extractors" [ps]
J. Håstad, R. Impagliazzo, L. Levin, and M. Luby "Construction of a pseudo-random generator from any one-way function" [ps], rozdział 6.1, (chciałem też zrobić 6.2, ale zabrakło czasu)

Teorio-informacyjnie bezpieczne kody uwierzytelniające wiadomości (ang.: Message Authentication Codes, MACs). Dyskutowaliśmy ich użyteczność oraz:
- pokazaliśmy, że w tej roli sprawdzają się uniwersalne funkcje haszujące i
- pokazaliśmy przykłady takich funkcji.
Zajęcia były prowadzone według książki D. Stinson "Cryptography: Theory and Practice, Second Edition" [link]. Niestety nie jest ona opublikowana na sieci, ale można się do mnie zgłosić jak ktoś chce zrobić ksero (odpowiedni rozdział ma parę stron). Jak ktoś chce się dowiedzieć jak się MACi robi w praktyce, to może zajrzeć tu oraz tu (w tej drugiej pozycji nawet jest o trochę o tych zagadnieniach, które poruszaliśmy na ćwiczeniach, ale oznaczenia są nieco inne).

Powyższa lista jest aktualizowana wraz z postępem zajęć. Data ostatniej aktualizacji: 23.04.04.

Czasami wysyłam emaile do uczestników zajęć. Ich listę pobrałem z USOSa. Jeśli ktoś chce, żeby go dodać do tej listy to proszę o kontakt (np. przez email).

S. Dziembowski : Dydaktyka : Teoria Informacji 04/05