Nawet w 2016 r. artykuły na temat komputerów kwantowych wywołały niepewność co do bezpieczeństwa danych w przypadku możliwości zbudowania komputerów kwantowych o wystarczającej mocy. W tym artykule postaramy się rzucić nieco światła na tę sytuację.
Co to są obliczenia kwantowe?
Obliczenia kwantowe to zastosowanie zasad mechaniki kwantowej do wykonywania obliczeń. W szczególności obliczenia kwantowe wykorzystują stany kwantowe cząstek subatomowych, takie jak superpozycja i splątanie, do tworzenia komputerów kwantowych. Po zastosowaniu w komputerach kwantowych o wystarczającej mocy określone algorytmy mogą wykonywać obliczenia znacznie szybciej niż klasyczne komputery, a nawet rozwiązywać problemy będące poza zasięgiem obecnej technologii obliczeniowej. W rezultacie wzrasta zainteresowanie rządów i gałęzi przemysłu na całym świecie rozwojem komputerów kwantowych. Najnowsze osiągnięcia w dziedzinie obliczeń kwantowych, takie jak procesor IBM Quantum Heron, znacznie poprawiły redukcję błędów, co świadczy o szybkim postępie w tej dziedzinie. Wprowadzenie IBM Quantum System Two, wyposażonego w te zaawansowane procesory, oznacza krok w kierunku praktycznych superkomputerów kwantocentrycznych.
Obliczenia klasyczne a kwantowe
Klasyczne obliczenia w celu rozwiązywania złożonych problemów opierają się na bitach reprezentujących jedynki i zera poprzez prądy elektryczne w obwodach. Obliczenia kwantowe, wykorzystujące kubity takie jak te w IBM Quantum Heron, przewyższają klasyczne obliczenia pod względem mocy obliczeniowej dzięki ulepszonej korekcji błędów i stabilności kubitów. Kubity, w przeciwieństwie do bitów, mogą istnieć w superpozycji, ucieleśniając jednocześnie jedynkę i zero. Ta zdolność pozwala pojedynczemu kubitowi reprezentować dwa stany na raz, a przy każdym dodatkowym kubicie reprezentowalne stany podwajają się wykładniczo („2^n” dla n kubitów). Na przykład komputer kwantowy z dziesięcioma kubitami może reprezentować 1024 stany, w przeciwieństwie do 10 bitów w klasycznym przetwarzaniu. Splątanie kwantowe, złożone i nie do końca poznane zjawisko, umożliwia łączenie kubitów, zwiększając wydajność obliczeniową. Wykorzystując zarówno superpozycję, jak i splątanie, komputery kwantowe działają w przestrzeniach wielowymiarowych, wykonując obliczenia równoległe, w przeciwieństwie do podejścia sekwencyjnego w klasycznym przetwarzaniu. Ta zaawansowana moc obliczeniowa umożliwia komputerom kwantowym rozwiązywanie problemów wykraczających poza możliwości komputerów klasycznych, takich jak dokładne symulowanie interakcji molekularnych w reakcjach chemicznych. Ma to daleko idące konsekwencje dla nauki i technologii, w tym możliwość rozwiązywania problemów znacznie szybciej niż klasyczne komputery, wpływając na takie obszary jak kryptografia.Jak obliczenia kwantowe mogą wpływać na kryptografię?
Jak omówiono powyżej, kryptografia opiera się na istnieniu nierozwiązywalnych problemów matematycznych, co nie oznacza, że są one nierozwiązywalne, ale że czas i zasoby wymagane do ich rozwiązania sprawiają, że są one praktycznie bezpieczne.
Obliczenia kwantowe zmieniają ten ekosystem, minimalizując czas potrzebny na rozwiązanie takich problemów poprzez zastosowanie określonych algorytmów.
Na przykład algorytm odkryty przez , wraz z implikacjami algorytmów takich jak algorytm Shora w kontekście zaawansowanych procesorów kwantowych, takich jak Quantum Heron firmy IBM, podkreślają bezpośrednie zapotrzebowanie na systemy kryptograficzne odporne na kwanty.
„W 1994 roku Peter Shor z Bell Laboratories wykazał, że komputery kwantowe, nowa technologia wykorzystująca fizyczne właściwości materii i energii do wykonywania obliczeń, mogą skutecznie rozwiązać każdy z tych problemów, czyniąc w ten sposób bezsilnymi wszystkie kryptosystemy klucza publicznego oparte na takich założeniach. Zatem wystarczająco wydajny komputer kwantowy narazi na niebezpieczeństwo wiele form współczesnej komunikacji – od wymiany kluczy, przez szyfrowanie, po uwierzytelnianie cyfrowe”.
Krótko mówiąc, komputer kwantowy o wystarczającej mocy może całkowicie spowodować awarię infrastruktury klucza publicznego, stwarzając potrzebę przeprojektowania całego ekosystemu cyberbezpieczeństwa.
W przestrzeni konsumenckiej można dostrzec najnowsze zastosowania kryptografii postkwantowej, jak np. obsługa algorytmu PQC w przeglądarce Chrome, co wskazuje na praktyczny wpływ obliczeń kwantowych na obecne systemy kryptograficzne.
Ale to nie wszystko. Inny algorytm, tym razem ” może stanowić zagrożenie dla kryptografii symetrycznej, choć nie tak poważne jak w przypadku Shora. Algorytm Grovera zastosowany do wystarczająco wydajnego komputera kwantowego pozwala na łamanie kluczy symetrycznych z czterokrotnie większą szybkością w porównaniu z obliczeniami klasycznymi. Znacząca poprawa, której przeciwdziała zastosowanie większych kluczy i utrzymanie obecnego poziomu bezpieczeństwa.
Czy wkrótce pojawią się obliczenia kwantowe?
Fizyka udowodniła, że obliczenia kwantowe są wykonalne. Teraz jest to problem inżynieryjny, choć bardzo trudny. Budowa komputerów kwantowych wiąże się z wdrażaniem najnowocześniejszych technologii, takich jak m.in. nadcieki i nadprzewodniki. Wyzwanie polegające na stworzeniu stabilnego i skalowalnego systemu kwantowo-mechanicznego jest ogromne i prowadzi zespoły na całym świecie do podążania różnymi ścieżkami. Istnieje kilka rodzajów komputerów kwantowych, w tym model obwodu kwantowego, kwantowa maszyna Turinga, adiabatyczny komputer kwantowy, jednokierunkowy komputer kwantowy i różne kwantowe automaty komórkowe. Najszerzej stosowanym jest obwód kwantowy.
Istotnym problemem w przypadku każdego modelu komputerów kwantowych jest to, że kubity z natury tracą swój status superpozycji po zmierzeniu i w konsekwencji są bardzo wrażliwe na zakłócenia z zewnątrz. Dlatego kubity mają trudności z utrzymaniem swoich stanów kwantowych. Niektóre rozwiązania obejmują zastosowanie pułapek jonowych, ale całkowita eliminacja zakłóceń zewnętrznych jest prawdopodobnie nieosiągalna. W rezultacie jednym z najważniejszych problemów przy tworzeniu komputerów kwantowych jest solidny mechanizm korekcji błędów.
Dzięki niedawnym przełomom, takim jak postęp IBM w dziedzinie obliczeń kwantowych, dziedzina ta wyszła poza modele teoretyczne i zajęła się bardziej praktycznymi i wydajnymi systemami kwantowymi, przybliżając erę kwantową bardziej, niż wcześniej przewidywano.
Cały obraz jest taki, że przełom może nastąpić właśnie teraz lub może minąć kilka lat, zanim powstanie działający prototyp o wystarczającej mocy obliczeniowej. Istnieje już kilka prototypów, z których najbardziej znany jest IBM Q System One, ale ich moc obliczeniowa jest wciąż zbyt mała, aby stanowić problem dla systemów kryptograficznych. W żadnym wypadku nie wolno oczywiście odpoczywać społeczności zajmującej się cyberbezpieczeństwem. Nawet gdybyśmy mieli skuteczny schemat bezpieczeństwa post-kwantowego, migracja całego ekosystemu do tego nowego standardu jest ogromnym zadaniem. W związku z tym podejmuje się szereg wysiłków, aby przygotować się na erę post-kwantową.
Obiecujące technologie dla ery postkwantowej
W miarę jak zbliżamy się do powszechnego zastosowania technologii kwantowej, czego dowodem są takie osiągnięcia, jak Quantum System Two firmy IBM, zapotrzebowanie na technologię kwantową PKI staje się coraz pilniejsze wraz z pojawieniem się powszechnej technologii obliczeń kwantowych. Poniżej postaramy się podsumować najbardziej obiecujące technologie i dokonać krótkiego przeglądu realizowanych zbiorowych projektów mających na celu ustanowienie kryptografii postkwantowej wraz z wyzwaniami, jakie przed nimi stoją.
Rodziny algorytmów post-kwantowych
Badania z ostatnich 15-20 lat dowiodły istnienia algorytmów odpornych na ataki kwantowe. Poniżej przedstawiamy krótki opis najbardziej obiecujących rodzin algorytmów, które mogą zapewnić rozwiązanie zapewniające bezpieczeństwo w post-kwantowym świecie.
Kryptografia oparta na kodzie
Najnowsze osiągnięcia w tej dziedzinie kryptografia oparta na kodzie wykorzystuje kody korygujące błędy do tworzenia kryptografii klucza publicznego. Został on po raz pierwszy zaproponowany przez Roberta McEliece’a w 1978 roku i jest jednym z najstarszych i najlepiej zbadanych algorytmów szyfrowania asymetrycznego. Schemat podpisu można zbudować w oparciu o schemat Niederreitera, podwójny wariant schematu McEliece’a. Kryptosystem McEliece’a jak dotąd opierał się kryptoanalizie. Głównym problemem oryginalnego systemu jest duży rozmiar klucza prywatnego i publicznego.
Kryptografia oparta na hashu
Wraz z rosnącą liczbą zastosowań praktycznych kryptografia oparta na skrótach stanowi obiecujące podejście do podpisów cyfrowych w ramach kryptografii postkwantowej. Funkcje mieszające to funkcje, które odwzorowują ciągi o dowolnej długości na ciągi o stałej długości. Są to jedne ze starszych schematów kryptografii klucza publicznego, a ich oceny bezpieczeństwa przed atakami klasycznymi i kwantowymi są dobrze poznane. Funkcje skrótu są już jednym z najpowszechniej stosowanych narzędzi kryptograficznych. Już od dawna było wiadomo, że mogą one służyć jako jedyne narzędzie do budowy kryptografii klucza publicznego. Ponadto kryptografia oparta na skrótach jest elastyczna i może spełniać różne oczekiwania dotyczące wydajności. Wadą schematów podpisów opartych na skrótach jest głównie stanowość, co oznacza, że klucz prywatny wymaga aktualizacji po każdym użyciu; w przeciwnym razie bezpieczeństwo nie jest gwarantowane. Istnieją schematy oparte na skrótach, które są bezstanowe, ale wiążą się one z dłuższymi podpisami, dłuższym czasem przetwarzania i koniecznością śledzenia przez osobę podpisującą niektórych informacji, np. tego, ile razy klucz został użyty do utworzenia podpisu.
Kryptografia sieciowa
Obecnie rozważana pod kątem bardziej zaawansowanych rozwiązań kryptograficznych Kryptografia oparta na sieciach jest szczególnym przypadkiem kryptografii opartej na problemach z sumą podzbiorów i została po raz pierwszy wprowadzona w 1996 roku przez Ajtai. Jest to ogólny termin określający prymitywy kryptograficzne zbudowane przy użyciu krat. Niektóre z tych konstrukcji wydają się być odporne zarówno na ataki komputerów kwantowych, jak i klasycznych. Dodatkowo mają inne atrakcyjne cechy, takie jak najgorsza trudność w zakresie twardości. Charakteryzują się także prostotą i równoległością oraz są na tyle wszechstronne, że można konstruować solidne schematy kryptograficzne. Wreszcie są jedyną rodziną algorytmów zawierającą wszystkie trzy rodzaje prymitywów wymaganych do zbudowania postkwantowej infrastruktury klucza publicznego: szyfrowanie kluczem publicznym, wymianę kluczy i podpis cyfrowy.
Kryptografia wielowymiarowa
Kryptografia wielowymiarowa odnosi się do kryptografii z kluczem publicznym, której klucze publiczne reprezentują wielomianową i nieliniową (zwykle kwadratową) mapę wielomianową. Udowodniono, że rozwiązanie tych systemów jest NP-kompletne, co czyni tę rodzinę algorytmów dobrymi kandydatami do kryptografii post-kwantowej. Obecnie wielowymiarowe schematy szyfrowania okazały się mniej wydajne niż inne schematy, ponieważ wymagają znacznych kluczy publicznych i długich czasów odszyfrowywania. Z drugiej strony okazały się bardziej odpowiednie do budowania schematów sygnatur, ponieważ zapewniają najkrótsze rozmiary sygnatur wśród algorytmów post-kwantowych, chociaż wiążą się z dość dużymi kluczami publicznymi.
Kryptografia oparta na izogenii
Kryptografia oparta na izogenii wykorzystuje mapy między krzywymi eliptycznymi do tworzenia kryptografii z kluczem publicznym. Algorytm, który jest kandydatem do kryptografii post-kwantowej, to supersingularna izogeniczna wymiana kluczy Diffiego-Hellmana (SIDH) wprowadzona w 2011 r., co czyni ten schemat najnowszym spośród kandydatów. SIDH wymaga jednego z najmniejszych kluczy spośród proponowanych schematów wymiany kluczy i obsługuje doskonałe utajnienie przekazywania. Jednak jego stosunkowo młody wiek sprawia, że nie ma wielu schematów opartych na tej koncepcji i nie było zbyt wiele do sprawdzenia ich możliwych podatności.
Projekty dla kryptografii post-kwantowej
Istnieją różne grupy robocze zajmujące się schematami kryptografii postkwantowej, takie jak projekt Open Quantum Safe (OQS) i ENISA. Jednak najbardziej spójną inicjatywą jest projekt standaryzacji kryptografii postkwantowej NIST, w ramach którego poczyniono znaczne postępy od 2021 r., a nowe algorytmy stały się liderami standaryzacji branżowej w erze postkwantowej. Proces rozpoczął się od 69 kandydatów na algorytmy, z których 26 przeszło do drugiej rundy oceny. W lipcu 2020 r. ogłoszono kandydatów w III turze, co przedstawia poniższa tabela. W sumie jest siedmiu finalistów i ośmiu alternatywnych kandydatów. W tabeli zapisano, czy są one brane pod uwagę w przypadku schematów szyfrowania lub podpisu, rodzinę algorytmów i trudny problem, na którym się opierają.
| Schemat | Enc/Sig | Rodzina | Trudny problem |
|---|---|---|---|
| Klasyczny McEliece | Inc | Oparte na kodzie | Dekodowanie losowych kodów binarnych Goppa |
| Kryształy-Kyber | Inc | Oparte na siatce | Moduł cyklotomiczny-LWE |
| NTRU | Inc | Oparte na siatce | Cyklotomiczny problem NTRU |
| szabla | Inc | Oparte na siatce | Moduł cyklotomiczny-LWR |
| Kryształy-Dilithium | Sig | Oparte na siatce | Moduł cyklotomiczny-LWE i Moduł-SIS |
| sokół | Sig | Oparte na siatce | Pierścień cyklotomiczny-SIS |
| Tęcza | Sig | Oparte na wielu odmianach | Pułapka na olej i ocet |
Alternatywni kandydaci rundy 3
| Schemat | Zał./sygn | Rodzina |
|---|---|---|
| ROWER | Inc | Oparte na kodzie |
| HQC | Inc | Oparte na kodzie |
| Frodo-KEM | Inc | Oparte na siatce |
| NTRU-Prime | Inc | Oparte na siatce |
| TAK | Inc | Oparte na izogenii |
| GeMSS | Sig | Oparte na wielu odmianach |
| piknik | Sig | Symetryczny krypto |
| SPHINCS + | Sig | Oparte na hashu |
Ocena algorytmu została oparta na trzech kryteriach przedstawionych poniżej.
-
Bezpieczeństwo: To jest najważniejsze kryterium. NIST ustalił kilka czynników, które należy wziąć pod uwagę przy ocenie bezpieczeństwa zapewnianego przez każdy kandydat na algorytm. Oprócz kwantowej odporności algorytmów, NIST zdefiniował także dodatkowe parametry bezpieczeństwa, które nie są częścią obecnego ekosystemu cyberbezpieczeństwa. Są to doskonała tajemnica przekazu,
-
Koszt i wydajność: Algorytmy są oceniane na podstawie wskaźników wydajności, takich jak rozmiary kluczy, wydajność obliczeniowa operacji i generowania kluczy publicznych i prywatnych oraz błędy w deszyfrowaniu.
-
Charakterystyka algorytmiczna i implementacyjna: Zakładając, że algorytmy zapewniają dobre ogólne bezpieczeństwo i wydajność, są oceniane na podstawie ich elastyczności, prostoty i łatwości przyjęcia (np. istnienia lub nie własności intelektualnej obejmującej algorytm).
Sprawność kryptograficzna
Ważnym paradygmatem w projektowaniu protokołów bezpieczeństwa informacji jest elastyczność kryptograficzna. Nakazuje, aby protokoły obsługiwały wiele prymitywów kryptograficznych, umożliwiając systemom wdrażającym określony standard wybór odpowiedniej kombinacji prymitywów. Podstawowym celem elastyczności kryptograficznej jest umożliwienie szybkiej adaptacji wrażliwych prymitywów i algorytmów kryptograficznych do solidnych, bez wprowadzania zakłócających zmian w infrastrukturze systemu. Paradygmat ten okazuje się kluczowy w projektowaniu kryptografii postkwantowej i wymaga przynajmniej częściowej automatyzacji. Na przykład przeciętne przedsiębiorstwo posiada ponad setki tysięcy certyfikatów i kluczy, a liczba ta stale rośnie. Przy tak dużej liczbie certyfikatów organizacje muszą wdrożyć zautomatyzowane metody, aby szybko je zastąpić, jeśli kryptografia, na której polegają, stanie się niepewna.
Doskonałym pierwszym środkiem dla organizacji jest rozpoczęcie wdrażania kryptografii hybrydowej, w której obok tradycyjnych algorytmów klucza publicznego (takich jak RSA lub krzywe eliptyczne) używane są bezpieczne kwantowo algorytmy klucza publicznego, tak aby rozwiązanie było co najmniej nie mniej bezpieczne niż istniejące tradycyjne kryptografia.
Patrząc w przyszłość
Obliczenia kwantowe przechodzą od teoretycznej możliwości do praktycznej rzeczywistości, czego przykładem są najnowsze osiągnięcia w procesorach i systemach kwantowych. W związku z tym dziedzina cyberbezpieczeństwa będzie musiała szybko dostosować się do tych zmian.
