Financial Crypto '14 - dzień drugi

Drugiego dnia wykłady rozpoczęły się od prezentacji pracy Mehdi Tibouchi "Elligator Squared: Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings". Praca jest ciekawa, ponieważ porusza temat, który zazwyczaj jest pomijany przy konstrukcji kryptosystemów a mianowicie ukrycie samego faktu, że dane są szyfrowane. Dlaczego ktoś chciałby ukryć, że korzysta z szyfrowania? Rządy niektórych krajów, jak np. Chiny, czy Iran nie życzą sobie, żeby ich obywatele korzystali z anonimowości w internecie jaką daje technnologia Tor, ponieważ uniemożliwia to cenzurę. W tym celu filtrują połączenia internetowe wychodzące za granicę kraju i jeśli nabiorą podejrzeń, że dane połączenie jest połączeniem sieci Tor to zostaje ono przerwane. Z tego względu ważne jest, aby takie połączenia były możliwie trudne do odróżnienia od innych typów połączeń.

Połączenia Tor można odróżnić od innych połączeń, m.in. dzięki temu, że są one zaszyfrowane za pomocą szyfrów bazujących na krzywych eliptycznych. W szyfrach tych przesyłane wiadomości szyfrowane są jako ciągi punktów na takich krzywych, które są następnie kodowane jako ciągi bitów i przesyłane przez internet. Okazuje się, że opisy punktów na krzywych eliptycznych nie są do końca losowe i łatwo odróżnić je od innego typu danych. Z tego względu korzystne byłoby istnienie kodowania dla którego opis punktu na krzywej eliptycznej byłby zupełnie losowym ciągiem bitów (tzn. o rozkładzie jednostajnym). Dotychczas takie kodowania znane były tylko dla niektórych krzywych i to akurat takich, które do wykorzystania w kryptografii z pewnych względów często się nie nadają. Autor we wspomnianej pracy rozwiązuje ten problem i pokazuje algorytm kodowania punktów, który dla dowolnej krzywej generuje zupełnie losowe ciągi bitów.

Warto też wspomnieć o pracy "Scaling Private Set Intersection to Billion-Element Sets" (autorzy: Seny Kamara, Payman Mohassel, Mariana Raykova, Saeed Sadeghian). Postawiony w pracy problem jest następujący. Dwie osoby mają pewne zbiory danych, np. pacjentów szpitala lub klientów firmy i chcieliby policzyć przecięcie tych zbiorów. Nie ufają sobie jednak nawzajem i nie mogą po prostu przesłać sobie swoich zbiorów. Znane są rozwiązania dla tego problemu bazujące na tzw. Two Party Protocols, ale są one zbyt mało wydajne. Autorzy proponują inne rozwiązania przy założeniu, że możemy skorzystać z pomocy dodatkowego serwera, który może dokonywać obliczeń, ale nie powinien dowiedzieć się niczego o samych zbiorach.

Najprostsze rozwiązanie działa w następujący sposób. Strony ustalają między sobą klucz K i szyfrują za pomocą niego elementy swoich zbiorów a następnie przesyłają je do serwera. Serwer może wówczas policzyć przecięcie otrzymanych zaszyfrowanych zbiorów i przesłać je obu stronom, sam jednak nie dowiaduje się niczego o przetwarzanych zbiorach oprócz ich rozmiaru i rozmiaru przecięcia. Przy takim rozwiązaniu serwer może jednak oszukać i dodać lub odjąć jakiś element do przecięcia. Autorzy prezentują w pracy szereg algorytmów, które pozwalają uniknąć takiej sytuacji i wykryć modyfikacje dokonane przez serwer.