Czy możliwe jest istnienie metody szyfrowania, której nie można złamać, nawet przy użyciu komputerów kwantowych?

Wiadomo, że komputery kwantowe potrafią złamać w czasie wielomianowym szeroki zakres algorytmów kryptograficznych, które wcześniej uważano za możliwe do rozwiązania tylko dzięki zasobom rosnącym wykładniczo wraz z wielkością bitu klucza. Przykładem tego jest algorytm Shora .

Ale, o ile wiem, nie wszystkie problemy należą do tej kategorii. O robieniu trudnych problemów dla komputerów kwantowych możemy przeczytać

Naukowcy opracowali algorytm komputerowy, który nie rozwiązuje problemów, lecz tworzy je w celu oceny komputerów kwantowych.

Czy nadal możemy spodziewać się nowego algorytmu kryptograficznego, który będzie trudny do złamania nawet przy użyciu komputera kwantowego ? Dla jasności: pytanie dotyczy konkretnie projektowania nowych algorytmów .

W tytule pytania pytasz o techniki, których nie da się złamać, na które One Time Pad (OTP) jest prawidłową odpowiedzią, jak wskazano w innych odpowiedziach. OTP jest teoretycznie bezpieczny, co oznacza, że ​​zdolności obliczeniowe przeciwników nie mają zastosowania, jeśli chodzi o znalezienie wiadomości.

Jednak pomimo tego, że teoretycznie są całkowicie bezpieczne , OTP ma ograniczone zastosowanie we współczesnej kryptografii. Bardzo trudno jest z powodzeniem stosować w praktyce .

Ważne pytanie to:

Czy nadal możemy spodziewać się nowego algorytmu kryptograficznego, który będzie trudny do złamania nawet przy użyciu komputera kwantowego?

Kryptografia asymetryczna

Kryptografia asymetryczna obejmuje szyfrowanie klucza publicznego (PKE), podpisy cyfrowe i schematy uzgadniania kluczy. Techniki te są niezbędne do rozwiązania problemów związanych z dystrybucją i zarządzaniem kluczami. Dystrybucja kluczy i zarządzanie kluczami są nie mniej istotnymi problemami, w dużej mierze uniemożliwiającymi zastosowanie OTP w praktyce. Internet, jaki znamy dzisiaj, nie działałby bez możliwości stworzenia bezpiecznego kanału komunikacyjnego z niepewnego kanału komunikacyjnego, co jest jedną z funkcji oferowanych przez algorytmy asymetryczne.

Algorytm Shora

Algorytm Shora jest przydatny do rozwiązywania problemów faktoryzacji liczb całkowitych i logarytmów dyskretnych. Te dwa problemy stanowią podstawę bezpieczeństwa powszechnie stosowanych schematów, takich jak RSA i Diffie-Hellman .

NIST obecnie ocenia wnioski dotyczące algorytmów post-kwantowych - algorytmów opartych na problemach uważanych za odporne na komputery kwantowe. Te problemy obejmują:

• Problemy oparte na kratach
  • Najkrótszy problem wektorowy (SVP)
  • Najbliższy problem wektorowy (CVP)
• Równania wielowymiarowe
  • Wielowymiarowe równania wielomianowe
• Schematy oparte na kodzie
  • Na podstawie twardości dekodowania kodów liniowych
• Supersingular Isogeny Diffie-Hellman (SIDH)

Należy zauważyć, że mogą istnieć klasyczne algorytmy rozwiązywania powyższych problemów , po prostu czas działania / dokładność tych algorytmów jest przeszkodą w rozwiązywaniu dużych instancji w praktyce. Problemy te nie wydają się być możliwe do rozwiązania, gdy daje się im możliwość rozwiązania problemu znajdowania porządku , co właśnie robi kwantowa część algorytmu Shora.

Kryptografia symetryczna

Algorytm Grovera zapewnia kwadratowe przyspieszenie podczas przeszukiwania nieposortowanej listy. Jest to faktycznie problem brutalnego wymuszania symetrycznego klucza szyfrowania.

Obchodzenie się z algorytmem Grovera jest względnie łatwe w porównaniu do obchodzenia się z algorytmem Shora: wystarczy podwoić rozmiar klucza symetrycznego . 256-bitowy klucz oferuje 128-bitowy opór przeciwko brutalnej sile przeciwnikowi, który korzysta z algorytmu Grovera.

Algorytm Grovera nadaje się również do funkcji haszujących . Ponowne rozwiązanie jest proste: Podwój wielkość wyjściowego skrótu (i pojemność, jeśli używasz skrótu opartego na konstrukcji gąbki ).

Przypuszczam, że istnieje pewien rodzaj szyfrowania, którego nie da się złamać przy użyciu komputerów kwantowych: jednorazowa podkładka, taka jak szyfr Vigenère . Jest to szyfr z klawiaturą, który ma co najmniej długość zakodowanego ciągu i będzie używany tylko raz. Tego szyfru nie da się złamać nawet przy pomocy komputera kwantowego.

Wyjaśnię dlaczego:

Załóżmy, że nasz zwykły tekst to ABCD. Odpowiednim kluczem może być 1234. Jeśli go zakodujesz, otrzymasz XYZW. Teraz możesz użyć, 1234aby uzyskać ABCDlub 4678uzyskać EFGHrównież poprawne zdanie.

Problem polega na tym, że nikt nie może zdecydować, czy miałeś na myśli klucz, ABCDczy EFGHnie.

Jedynym powodem złamania tego rodzaju szyfrowania jest to, że użytkownicy są leniwi i używają klucza dwukrotnie. A potem możesz spróbować go złamać. Inne problemy to, jak stwierdził @peterh, że jednorazowe pady wymagają udostępnienia tajnego kanału

Tak, istnieje wiele propozycji post-kwantowych algorytmów kryptograficznych , które zapewniają prymitywne elementy kryptograficzne, do których jesteśmy przyzwyczajeni (w tym szyfrowanie asymetryczne kluczami prywatnymi i publicznymi).

Kontynuacja odpowiedzi Elli Rose: większość praktycznych schematów szyfrowania stosowanych obecnie (np. Diffie-Hellman, RSA, krzywa eliptyczna, oparta na sieci) koncentruje się wokół trudności rozwiązania problemu ukrytej podgrupy (HSP). Jednak pierwsze trzy są skupione wokół HSP dla grup abelowych . HSP dla grup abelowych można skutecznie rozwiązać za pomocą kwantowej transformacji Fouriera , która jest implementowana np. Przez algorytm Shora. Są zatem podatne na atak komputera kwantowego. Z drugiej strony większość metod opartych na sieciach kręci się wokół HSP dla dwuściennegogrupy nieabelowe. Uważa się, że komputery kwantowe nie są w stanie skutecznie rozwiązać nieabelowego HSP, więc algorytmy te powinny być w stanie zaimplementować kryptografię kwantową.