28.03.14: Zero-Knowledge

Wykład prowadzony był według książki Odeda Goldreicha The Foundations of Cryptography (vol 1). Książka ta nie jest dostępna online, ale Goldreich zamieścił draft niektórych rozdziałów na swojej stronie. Rozdział o Zero Knowledge znajduj się tu. Poniżej używam numerów rozdziałów oraz stron odnosząc się do tego draftu.

Zaczęliśmy krótkim wstępem (Rozdziały 4.1- 4.3.3, Rozdział 4.4 do strony 162). Ponieważ większość tego materiału była na wykładzie z Kryptografii I, to nie potraktowaliśmy go dość pobieżnie.

Bardziej dokładnie przedstawiliśmy materiał z Rozdziału 4.10 (Non-Interactive Zero Knowledge). Dowód Faktu 4.10 był zostawiony na ćwiczenia i niestety nie poradziliśmy sobie z nim do końca.

Pokazaliśmy też dlaczego protokoły Zero-Knowledge nie są odporne na składanie "równoległe" (Rozdział 4.5.3.1)

21.03.14: Twierdzenie Goldreicha-Levina, konstrukcja Goldreicha, Goldwasser i Micali'ego

Wykład zaczęliśmy sformułowaniem twierdzenia (bez dowodu), że nieprzewidywalność kolejnego bitu jest równoważna pseuodolosowości.  Znajduje się ono w Pozdrozdziale 9.3.1 Rozdziału 9 ksiażki

Sanjeev Arora and Boaz Barak Computational Complexity: A Modern Approach.

Następnie pokazaliśmy Twierdzenie Goldreicha-Levina (z dowodem). Całość można znaleźć w Pozdrozdziale 9.3.2 tej samej książki.

Na ćwiczeniach pokazaliśmy konstrukcję funkcji pseudolosowej z generatora pseudolosowego (wraz z dowodem). Można ją znaleźć w Rozdziale 4 tych notatek autorstwa Yevgeniy'a Dodisa.

14.03.14: Funkcje jednokierunkowe i generatory pseudolosowe

Pokazaliśmy, że istnienie słabych funkcji jednokierunkowych implikuje istnienie mocnych funkcji jednokierunkowych. Zajęcia prowadzone były według Rozdziału 1 (Podrozdziały 1.1 i 1.5) notatek Thomasa Holensteina z ETH w Zurychu.

Następnie mówiliśmy o generatorach pseudolosowych i ich związkach z funkcjami jednokierunkowymi według Rozdziału 3 tych samych notatek (Podrozdziały 3.1, 3.2 i 3.3, przy czym pominęliśmy dużo szczegółów, zwłaszcza w ostatnim podrozdziale).

7.03.14: Gotówka elektroniczna

Najpierw przedstawiliśmy protokół e-cash Davida Chauma którego opis można znaleźć np. tu:

• S. Goldwasser and M. Bellare: Lecture Notes on Cryptography (Rozdział 12.5).

Obserwacja o tym, że e-cash może posłużyć do zrealizowania "zbrodni doskonałej" została po raz pierwszy opisana tu:

• S. von Solms and D. Naccache: On Blind Signatures and Perfect Crimes [pdf].

Potem przestawiliśmy opis Bitcoina. Informacje na jego temat znajdują się tu:

• Satoshi Nakamoto: Bitcoin: A Peer-to-Peer Electronic Cash System [pdf]
• Bitcoin wiki.

Opis transakcji Bitcoinowych znajduje się np. w:

• Marcin Andrychowicz and Stefan Dziembowski and Daniel Malinowski and Łukasz Mazurek: Secure Multiparty Computations on BitCoin.

Na block chain można popatrzeć np. na stronie blockexplorer.com. Kontrowersje dotyczące tego kim jest Satoshi Nakamoto ożyły po dzisiejszym artykule Newsweeka. Kłopoty giełdy Mt Gox są opisane np. w tym artykule w PC World.

Ponadto opisaliśmy pomysł aby utrudnić fałszowanie papierowych pieniędzy przy użyciu włosków zaszytych losowo w banknocie oraz podpisu elektronicznego. Wg. tego co udało mi się ustalić, idea ta pochodzi z pracy G. J. Simmons: Identification of data, devices, documents and individuals (niestety nie udało mi się jej odnaleźć w internecie). Same "włoski" są widoczne np. tu.

Na ćwiczeniach dokończyliśmy dowód faktu o wielomianie dwóch zmiennych z poprzedniego tygodnia.

28.02.14: Verifiable Secret Sharing

Głównym tematem zajęć była konstrukcja Verifiable Secret Sharing. Znajduje się ona w pracy:

• Gilad Asharov and Yehuda Lindell A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation [pdf] (Rozdział 5)

oraz (mniej formalnie) w materiałach z wykładu Benny'ego Pinkasa [pdf,video] (slajdy 28-38). W końcówce dowodu bezpieczeństwa (przypadek nieuczciwego Dealera) mieliśmy problemy i zostało to do dokończenia na przyszły tydzień.

Poza tym cały czas nie poradziliśmy sobie do końca z dowodem faktu, że funkcji AND nie da się teorio-informacyjnie bezpiecznie policzyć w dwie osoby. Szkic tego dowodu znajduje się w:

• Ronald Cramer Introduction to Secure Computation [ps] (strona 9).