Crypto 2013: dzień czwarty

Czwarty dzień zaczął się od prezentacji dra Macieja Obremskiego na temat pracy członków zespołu CryptoUW pt. "Non-malleable codes from two-source extractors" (współautorami są: dr hab. Stefan Dziembowski oraz niżej podpisany). Ponieważ pewnie nie wypada skupiać się właśnie na tym, napiszę co mnie zainteresowało poza tą prezentacją.

Moją uwagę przykuł referat "Optimal Coding for Streaming Authentication and Interactive Communication". Autorzy wracają w nim do znanego problemu przesyłania wiadomości przez zaszumiony kanał. Istotą komunikacji w takim warunkach jest automatycznia korekcja błędu wysyłanych komunikatów. Istnieją już dobre rozwiązania tego problemu: polegają na przesyłaniu pewnej redundantnej informacji, która ułatwia odczytanie częściowo (być może złośliwie) zmienionej informacji.

To, co nowego, zrobili autorzy, to rozwiązali problem przy ogólniejszych założeniach. Dotychczas zakładano, że długość wiadomości $n$ jest z góry znana, a wysyłający od razu wie, jaką wiadomość chce wysłać. W referowanej pracy, te założenia osłabiono: pokazano protokół dla komunikacji strumieniowej, potencjalnie nieskończonej.

Aby zachęcić do sięgnięcia po wersję papierową wystąpienia, dodam, że rozwiązanie jest wysoce nietrywialne. Łatwo chociażby zauważyć, że blokowe wysyłanie kolejnych fragmentów wiadomości długości $n$ jakimś znanym wcześniej kodowaniem nie może działać - zgubienie jednego bloku jest niewielkim (a więc dopuszczalnym) zaszumieniem, a przecież uniemożliwia odtworzenie całej wiadomości.

Na sam koniec pozwolę sobie (jak to ja) na uwagę natury bardziej filozoficznej. Tendencja, aby robić wyniki już znane, ale przy słabszych założeniach, jest zauważalna na całej konferencji. To chyba dobry kierunek. Przykładem takiego myślenia jest cała gałąź kryptografii, którą zajmuje się CryptoUW, tzn. wycieki (ang. leakage).

Crypto 2013: dzień drugi

Najciekawszą prezentacją drugiego dnia, moim zdaniem, była "Key Homomorphic PRFs and Their Applications".  Autorami pracy są Dan Boneh, Kevin Lewi, Hart Montgomery(prezentujący) i Ananth Raghunathan, wszyscy z Uniwerytetu Stanforda. 

Z trzech powodów było to niezwykle mile spędzone 20 minut: po pierwsze praca porusza niezmiernie ciekawe problemy, po drugie prezentowane rozwiązania są wyjątkowo eleganckie, w końcu po trzecie sama prezentacja była dobrze przemyślana i zrozumiała dla chyba wszystkich niezależnie od tematyki jaką się zajmują.

Nie chcę wchodzić zbytnio w szczegóły techniczne i nie zaprezentuję samej konstrukcji zamiast tego skupię się na jednym dość ciekawym zastosowaniu.

Niech $f(k,x)$ będzie funkcją pseudolosową, to znaczy, że jeśli nie znamy klucza $k$ wartości $f(k, \, )$ będą dla nas nieodróżnialne od kompletnie losowych. Na przykład jeśli poznamy $f(k,1)$, $f(k,2)$, $f(k,3)$ to bez znajomości klucza nie mamy szans na zgadnięcie $f(k,4)$.

Załóżmy, że chcemy połączyć się z jakimś serwerem. Zarówno serwer jak i my jesteśmy w posiadaniu tajnego klucza (ciągu bitów) $k$. Pierwszą fazą w nawiązywaniu połączenia jest udowodnienie serwerowi, że my to my (tj. że jesteśmy w posiadaniu klucza $k$). 

Jak to zrobić?

Może wyślijmy do serwera nasz klucz i serwer sprawdzi czy wszystko się zgadza? Niestety, jeśli ktoś podsłucha transmisje to wejdzie w posiadanie tajnego klucza. Potrzebujemy zatem lepszego rozwiązania.

Może niech serwer wybierze dowolną wartość $x$ i poprosi byśmy odpowiedzieli wartością $f(k,x)$? Nawet jeśli nasza transmisja zostanie podsłuchana przeciwnik pozna jedynie poprawną odpowiedź na jedno, konkretne, pytanie, jest niezwykle mało prawdopodobne, że serwer następnym razem zapyta o tę samą liczbę. Takie rozwiązanie jest poprawne.

Autorzy pracy dostrzegają jednak istotny minus takiej konstrukcji. Jeśli jakiś haker złamie zabezpieczenia serwera to za jednym zamachem otrzyma cały nasz klucz $k$ składowany na serwerze i będzie się mógł pod nas podszywać. Odpowiedzią na ten problem jest następujący pomysł autorów pracy.

Skonstruujmy trochę lepszą funkcję pseudolosową: jeśli $k=k_1+k_2$ to niech $f(k,x)=f(k_1,x)+f(k_2,x)$. Pomysł jest więc taki, by nasz klucz $k$ podzielić na wiele części $k_1, k_2, k_3,…,k_n$ i każdą z nich składować na innym serwerze.

Uwierzytelnianie (dowodzenie, że ja to ja) będzie wtedy wyglądało następująco. Serwer prosi o wartość funkcji w $x$, my odpowiadamy $f(k,x)$ teraz serwer prosi o kolejne wartości $f(k_i,x)$ kolejne serwery (w żadnym momencie klucze nie opuszczają serwerów na których są składowane), teraz wystarczy że serwer sprawdzi czy przesłane przez nas $f(k,x)$ jest równe $f(k_1,x)+f(k_2,x)+ f(k_3,x)+…+f(k_n,x)$.

Przewagą tego rozwiązania nad poprzednim jest to, że teraz haker musi włamać się do wszystkich serwerów by móc podszywać się pod nas co jest niewątpliwie znacznie trudniejsze niż włamanie do pojedynczego serwera. 

Wszystko pięknie, tylko czy taka funkcja istnieje? Nie tylko istnieje. Dzięki "Key Homomorphic PRFs and Their Applications" znamy jej konstrukcję!

Autor: dr Maciej Obremski

Uwaga: artykuł ma charakter popularnonaukowy i zawiera pewne uproszenia

Crypto 2013: dzień trzeci

Dzisiaj swój wykład miał zwycięzca konkursu na najlepszą pracę konferencji. Wygrał Gologlu et al z pracą "One the Function Field Sieve and the Impact of Higher Splitting". Praca dotyczyła teorii liczb, ogólnie była chwalona. Nie jest to jednak moja działka, więc nie chcę wypowiadać się ekspercko na temat tego rezultatu.

Dla mnie największe wrażenie zrobiła sesja nr 13, czyli zagadnienia obliczeń wielopodmiotowych. Zaczął Yuval Ishai. To jedna z tych osób, które ma zawsze świetne przygotowane wystąpienia. Jednoczeście wykład był wyjątkowy interesujący dla mnie. Autor mówił jak zrobić gadżet podobny do obwodu Yao, ale bardziej skompresowany. To jest o tyle ciekawe, że obwody Yao wykorzystywałem osobiście w pracy "One-Time Programs with Limited Memory". Mogę więc teraz zastanowić się, czy nie da się zastąpić tej nowo zaproponowanej konstrukcji w swej starej pracy. Dzięki temu pewnie poprawią się parametry. Po takich wykładach dokładnie rozumie się, co to znaczy "środowisko naukowe". Badania to praca zespołowa!

Jako drugi w tej sesji swą pracę przedstawiał Ron Rothblum. Wynik znowu ciekawy. Idea jest taka: ile trzeba "przekupić" osób, żeby czegoś się dowiedzieć w jakimś obliczeniu wielopodmiotowym? Ogólne oszacowania są znane. Ale co, gdy ograniczymy np. głębokość drzewiastą funkcji, którą obliczamy? Wtedy da się zrobić to lepiej.

Crypto 2013: dzień pierwszy

Za nami pierwszy dzień bodaj najlepszej konferencji kryptograficznej, CRYPTO. Jak zawsze w Santa Barbara, w Południowej Kalifornii.

Tutaj każdy kryptograf czuje się jak w raju: przez kilka dni w jednym miejscu obcować można z pięknym miejscem, na pięknym kampusie, wśród pięknej fauny i flory, słuchając pięknych referatów. Surferzy na deskach na wysokich falach, szyfry symetryczne, wyrafinowane własności twierdzenia min-max, pelikany, szopy, kody niekowalne, podział sekretu, pelikany, szopy... Wszystko to miesza się jak w kalejdoskopie, a dusza i ciało mają ucztę w każdym sensie. Wszystkie poziomy potrzeb w kryteriach Maslowa wydają się być jednocześnie zaspakajane.

Może piszę trochę rzewnie, ale przecież inaczej się nie da. Żeby poczuć CRYPTO, trzeba zrozumieć, że tutaj wszystko się przeplata: rano śniadanie na tarasie De La Guerra, potem pospiesznie na pierwszą sesję wykładów. A tam Fully Homomorphic Encryption, czyli coś bardzo świeżego i aktualnego. Mi podobał się wykład Micciancio na temat swoich wyników z SIS i LWE - poprawił trochę parametry i pokazał pewne związki z Lossy Function Families. Nie mniej ciekawy był Alwen opowiadający o Learning with Rounding. Świetne tempo i balans między jasnością opisu a jego głębokością. Kluczowa definicja jest następująca:

$x\in Z_q, \lfloor x \rfloor_p := \lfloor \frac{xp}{q} \rfloor$.

Czemu to służy? Zachęcam do sięgnięcia po pełną pracę.

A dalej? A dalej spacer klifem wzdłuż brzegu oceanu. Krótki, bo zaraz kolejne wykłady.

Duże zainteresowanie wzbudził pierwszy duży wykład zaproszonego gościa - Cindy Cohn. Tematyka ocierała się o politykę, a więc o powszechne podsłuchiwane wszystkiego przez tajne służby. Dużo by pisać, na sali czuło się czasem gęstą atmosferę sprzeciwu przeciw niektórym praktykom agencji NSA. Nie będę rozwodził się na temat szczegółów technicznych. Zwrócę tylko uwagę, że to, co mnie osobiście najbardziej uderzyło to fakt, że politycy zdają się nie rozumieć, o co "w tym wszystkim chodzi". A NSA trochę działa jak państwo w państwie. Jak powiedziała prelegentka: w NSA jest dużo geeków, a po stronie polityków - mało. Jej zdaniem potrzeba jest zaangażować więcej geeków także po "jasnej stronie mocy". Sądzę, że wielu słuchaczy CRYPTO z tym się zgodziło.