1978 Cryptosystem opiera się atakowi kwantowemu

Nikt nie zbudował komputera kwantowego o wiele potężniejszego niż kalkulator kieszonkowy, ale to nie powstrzymało ludzi od zamartwiania się implikacjami świata po obliczeniach kwantowych. Najbardziej zmartwieni są ludzie, którzy polegają na kodach kryptograficznych w celu ochrony poufnych informacji. Po włączeniu pierwszego komputera kwantowego o przyzwoitych rozmiarach, wcześniej bezpieczne kody, takie jak powszechnie używany algorytm RSA, staną się natychmiast możliwe do złamania.

Właśnie dlatego kryptografowie biegają w poszukiwaniu kodów, które będą bezpieczne w świecie post-kwantowym. Dzisiaj Hang Dinh z University of Connecticut i kilku kumpli pokazują, że kryptografowie przez cały czas się na niego gapili. Mówią, że mało używany kod opracowany przez matematyka CalTech Roberta McEliece'a w 1978 roku jest w stanie oprzeć się wszystkim znanym atakom komputerów kwantowych.

Najpierw rozróżnijmy kody symetryczne i asymetryczne. Kody symetryczne używają identycznych kluczy do szyfrowania i odszyfrowywania wiadomości. Komputery kwantowe mogą radykalnie przyspieszyć atak na tego rodzaju kody. Jednak kody symetryczne mają pewną ochronę. Podwojenie rozmiaru klucza przeciwdziała temu przyspieszeniu. Dlatego twórcy kodu mogą wyprzedzić łamaczy, przynajmniej teoretycznie. (Chociaż w praktyce bezpieczne pieniądze byłyby na drapieżniku w tej grze w kotka i myszkę).

Kody asymetryczne używają różnych kluczy do szyfrowania i odszyfrowywania wiadomości. W tak zwanych systemach szyfrowania klucza publicznego, takich jak popularny algorytm RSA, klucz publiczny jest dostępny dla każdego, kto może go użyć do zaszyfrowania wiadomości. Ale tylko osoby posiadające klucz prywatny mogą odszyfrować wiadomości, co oczywiście jest utrzymywane w tajemnicy.

Bezpieczeństwo tych systemów opiera się na tak zwanych funkcjach zapadni: matematycznych kroków, które są łatwe do wykonania w jednym kierunku, ale trudne do wykonania w drugim. Najbardziej znanym przykładem jest mnożenie. Łatwo jest pomnożyć dwie liczby, aby uzyskać trzecią, ale trudno zacząć od trzeciej liczby i ustalić, które dwie liczby ją wygenerowały, proces zwany faktoryzacją.

Ale w 1994 roku matematyk Peter Shor wymyślił algorytm kwantowy, który mógłby rozkładać na czynniki znacznie szybciej niż jakikolwiek klasyczny odpowiednik. Taki algorytm działający na przyzwoitym komputerze kwantowym mógłby złamać wszystkie znane systemy szyfrowania klucza publicznego, jak 4-letni amok w Legolandzie.

Oto sens tego, jak to działa. Problem faktoryzacji polega na znalezieniu liczby, która dzieli się dokładnie na inną. Matematycy robią to posługując się ideą okresowości: obiekt matematyczny o dokładnie odpowiedniej okresowości powinien dokładnie podzielić liczbę, inne nie.

Jednym ze sposobów badania okresowości w świecie klasycznym jest zastosowanie analizy Fouriera, która może rozbić sygnał na fale składowe. Kwantowym odpowiednikiem tego jest kwantowe próbkowanie Fouriera, a triumfem Shora było znalezienie sposobu na wykorzystanie tego pomysłu do znalezienia okresowości obiektu matematycznego, który ujawnia czynniki.

Dzięki Shorowi każdy kod, który opiera się na tego rodzaju asymetrii (tj. prawie wszystkie popularne systemy szyfrowania klucza publicznego) może zostać złamany za pomocą kwantowego ataku Fouriera.

Kryptosystem McEliese jest inny. On również jest asymetryczny, ale jego bezpieczeństwo opiera się nie na faktoryzacji, ale na pewnej wersji zagadki, którą matematycy nazywają ukrytym problemem nadgrupy. Dinh i jego koledzy wykazali, że tego problemu nie da się rozwiązać za pomocą kwantowej analizy Fouriera. Innymi słowy, jest odporny na atak algorytmu Shora. W rzeczywistości jest odporny na każdy atak oparty na kwantowym próbkowaniu Fouriera.

To wielka sprawa. Oznacza to, że wszystko zakodowane w ten sposób będzie bezpieczne, gdy następna generacja komputerów kwantowych zacznie grzebać w bardziej konwencjonalnych kryptosystemach z kluczem publicznym. Jednym z takich systemów jest Entropy, sieć komunikacyjna typu peer-to-peer zaprojektowana, aby oprzeć się cenzurze opartej na kryptosystemie McEliese.

Ale Entropia jest mało używana i istnieją dobre powody, dla których inni opierają się systemowi szyfrowania McEliese. Główny problem polega na tym, że zarówno klucz publiczny, jak i prywatny są nieco nieporęczne: standardowy klucz publiczny to duża macierz opisana przez nie mniej niż 2^19 bitów.

Teraz może się to wydawać mniejszym problemem. Możliwe, że system McEleise nagle stanie się przedmiotem znacznie większej uwagi ponad 30 lat po jego wynalezieniu.

Warto jednak zauważyć, że chociaż nowa praca gwarantuje bezpieczeństwo przed wszystkimi znanymi atakami kwantowymi, nie robi nic podobnego dla przyszłych ataków kwantowych. Całkiem możliwe, że ktoś opracuje algorytm kwantowy, który rozerwie go na strzępy tak łatwo, jak Shora za pomocą algorytmu RSA. Nasze wyniki nie wykluczają innych ataków kwantowych (lub klasycznych), mówi Dinh i spółka.

Bardziej prawdopodobny scenariusz przyszłych badań jest taki, że kryptografowie wznowią swoje wysiłki w jednym z kilku innych kierunków, które wydają się owocne, takich jak algorytmy oparte na sieciach kratowych i kryptografia wielowymiarowa.

Tak czy inaczej, spodziewaj się, że usłyszysz dużo więcej o kryptografii post-kwantowej – pod warunkiem, że możesz pozwolić.

Nr ref.: arxiv.org/abs/1008.2390 : Kryptosystem McEliece jest odporny na ataki kwantowego próbkowania Fouriera

ukryć