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