6.06.14: Prywatne Pozyskiwanie Informacji

Omówiliśmy protokoły Prywatnego Pozyskiwania Informacji (ang. Private Information Retrieval, PIR). Wykład i ćwiczenia odbyły się na podstawie Rozdziałów 2, 3.1, 3.2 i 5.1 pracy:

Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan
Private Information Retrieval[link]

oraz całości pracy:

Eyal Kushilevitz and Rafail Ostrovsky
Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval[link]

30.05.14: Kryptografia oparta na przekształceniach wieloliniowych

Wykład poświęciliśmy przekształceniom wieloliniowym (ang. multilinear forms) i ich zastosowaniom w kryptografii. Początek wykład prowadzony był według Rozdziałów 1-4 i 6 pracy:

D. Boneh and A. Silverberg
Applications of Multilinear Forms to Cryptography
[link] 

 Potem omówiliśmy (bez pokazywania dowodów) Rozdziały 1-5 pracy:

Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters
Witness Encryption and its Applications 
[link]

Na ćwiczeniach pokazaliśmy schemat szyfrowania rozgłaszanego (ang. broadcast encryption) na podstawie Rozdziałów 2 i 3 pracy:

Dalit Naor and Moni Naor, and Jeff Lotspiech
Revocation and Tracing Schemes for Stateless Receivers
[link]

23.05.14: Public-Key Deniable Encryption (gościnny wykład Vincenzo Iovino)

We introduced the concept of public-key deniable encryption explaining for which settings is achievable and for which is not (not achievable in general). We discussed that a public key encryption scheme with perfect correctness cannot deniable so it has to have non-perfect correctness.

Then we presented simple construction of schemes with non-negligible distinguishing advantage (rather than negligible as usual). In particular we presented simple schemes for sender deniability with 1/poly advantage given in Section 3 in this paper (the schemes based on translucent sets and constructions of translucent sets).

Then we said that even though full deniability is in general impossible the researchers found a new clever model called multi-distributional deniability and we started to present this paper. We discussed the philosophical implication of multi-distributional deniability. Then I presented their construction based on simulatable PKE.

We skipped the construction based on bitranslucent sets and we concluded saying that the construction extends easily to the IBE setting. We did not give full proofs for the security but only intuition.

16.05.14: Kryptografia oparta na parowaniu dwuliniowym

Tematem wykładu była kryptografia oparta na parowaniu dwuliniowym (pairing-based cryptography). Pokazaliśmy:

• schemat trzystronnego uzgadniania klucza autorstwa Joux,
• schemat szyfrowania opartego na tożsamości autorstwa Boneha i Franklina
• schemat szyfrowania z wyszukiwaniem słów kluczowych.

Literatura: [link,link,link]

25.04.14: Optimal Asymmetric Encryption Padding

Opowiedzieliśmy o tym jak w praktyce uzyskać szyfrowanie bezpieczne w sensie CCA2 używając założenia o istnieniu losowej wyroczni. Skoncentrowaliśmy się na schemacie OAEP. Pokazaliśmy dlaczego wersja OAEP zaproponowana w oryginalnej pracy Bellare i Rogaway'a nie jest bezpieczna i nakreśliliśmy jak ją naprawić.

Literatura znajduje się tu.

11.04.14: Kryptosystem Cramera i Shoupa

Wykład rozpoczęliśmy przypomnieniem co to jest problem logarytmu dyskretnego, założenie DDH, schemat Diffiego-Hellmana i szyfrowanie ElGamala. Robiliśmy to według [4] (bez Rozdziału 2).

Następnie przedstawiliśmy kryptosystem Cramera i Shoupa według [9,10] (Rozdział 3 z [10] bez dowodu).

4.04.14: Szyfrowanie bezpieczne w sensie CCA przy użyciu protokołów NIZK

Przedstawiliśmy wynik Naora i Yunga zawierający kontstrukcję schematu szyfrowania asymetrycznego bezpiecznego w sensie CCA1 oraz Doleva, Dwork i Naora pokazujący jak tę konstrukcję ulepszyć żeby była bezpieczna w sensie CCA2 (tu daliśmy tylko szkic dowodu). Podstawowymi składnikami tej konstrukcji były: (a) schemat szyfrowania asymetrycznego bezpiecznego w sensie CPA i (b) protokoły Non-Interactive Zero Knowledge.

Wykład prowadzony był z notatek Jonathana Katza: [5,6,7]

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

21.02.14: Teorio-informacyjnie bezpieczne obliczenia wielopodmiotowe

Zajęcia zaczęliśmy od krótkiego powtórzenia zagadnień związanych z obliczeniami dwu-podmiotowymi, patrz:

• Two-Party Computation Protocols [pptx,pdf] (slajdy 3-5)

Potem mówiliśmy o obliczeniach wielopodmiotowych, patrz:

• Multiparty Computation Protocols [pptx,pdf] (w zasadzie całość, choć w trochę innej kolejności), oraz
• wykład Benny'ego Pinkasa [pdf,video] (slajdy 1-20, bez dowodów).

Znacznie formalniej i dokładniej materiał ten jest przedstawiony w 

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

Potem zrobilśmy zadanie, które można z grubsza streścić: 

Pokaż przykład protokołu obliczeń wielopodmiotowych który jest bezpieczny nieadaptywnie, ale nie jest bezpieczny adaptywnie.

A następnie pokazaliśmy, że funkcji AND nie da się teorio-informacyjnie bezpiecznie policzyć przy $t=n/2$ korupcjach, dla dowolnego $n$, o ile ten fakt zachodzi dla $n=2$. Przypadek $n=2$ został jako zadanie domowe.