Jak uzasadnić bezpieczeństwo po szyfrowaniu kwantowym?

Czy istnieje jakaś definicja lub twierdzenie o tym, co komputer kwantowy może osiągnąć, dzięki którym postkrystaliczne schematy kryptograficzne (np. Kryptografia sieci, ale nie kryptografia kwantowa) mogą uzasadniać ich bezpieczeństwo? Wiem, że funkcja znajdowania okresu jest w stanie złamać RSA i dyskretne dzienniki, ale czy jest to jedyny algorytm mający znaczenie dla zerwania schematów szyfrowania? Czy mogę powiedzieć, że jeśli schemat nie jest podatny na funkcję znajdowania okresu, nie jest podatny na obliczenia kwantowe? Jeśli nie, to czy istnieje podobne, alternatywne zdanie w formie „jeśli schemat szyfrowania nie może zostać złamany przez algorytm X, nie można go złamać za pomocą obliczeń kwantowych”?

Na przykład, czy wystarczy udowodnić, że schemat szyfrowania można złamać tylko poprzez wypróbowanie wszystkich możliwych kluczy, a najlepszym sposobem, jaki obliczenia kwantowe mogą zrobić w tym zakresie, jest czas wyszukiwania pierwiastka kwadratowego z algorytmem Grovera?

Jest to zasadniczo dziedzina klas złożoności obliczeniowej. Na przykład klasę BQP można z grubsza opisać jako zbiór wszystkich problemów, które można skutecznie rozwiązać na komputerze kwantowym. Trudność z klasami złożoności polega na tym, że trudno jest udowodnić rozdzielenie między wieloma klasami, tj. Istnienie problemów, które występują w jednej klasie, ale nie w innej.

W pewnym sensie wystarczy powiedzieć „jeśli ten algorytm kwantowy go nie złamie, jest bezpieczny”, wystarczy użyć właściwego algorytmu. Potrzebujesz algorytmu pełnego BQP, takiego jak znajdowanie pierwiastków wielomianu Jonesa - dowolny algorytm kwantowy można rzutować jako instancję algorytmu pełnego BQP. Jednak sposób wykorzystania tego algorytmu do krakowania jest całkowicie niejasny i nietrywialny. Nie wystarczy przekonać się, że nie można bezpośrednio brutalizować sił. Takie podejście prawdopodobnie nie jest tak pomocne.

Czego oczekujemy od post-kwantowego scenariusza kryptograficznego? Potrzebujemy:

• funkcja $y=f(x)$ które możemy łatwo obliczyć dla celów szyfrowania.
• dla którego odwrotność $f^{-1}(y)$ nie można go łatwo obliczyć na komputerze kwantowym, tzn. klasa problemów znajduje się poza BQP.
• mając jakiś sekret $z$, istnieje klasycznie wydajnie obliczalna funkcja $g(y,z)=x$, tj. z dodatkowymi informacjami, funkcja $f(x)$można odwrócić. Dzieje się tak, aby właściwa osoba (która ma klucz prywatny,$z$) może odszyfrować wiadomość.

Ten ostatni punkt jest (zasadniczo) definicją klasy złożoności NP: problemy, dla których znalezienie rozwiązania może być trudne, ale dla którego rozwiązanie można łatwo zweryfikować po otrzymaniu dowodu (odpowiadającego w naszym przypadku kluczowi prywatnemu) .

Zatem szukamy problemów w NP, ale nie w BQP. Ponieważ nie wiemy, czy NP = BQP, nie wiemy, że takie rzeczy istnieją. Jest jednak dobra droga do szukania rozwiązań: rozważamy problemy z NP-zupełnością. Są to najtrudniejsze przypadki problemów w NP, więc jeśli BQP$\neq$NP (jak się powszechnie uważa), problemy z kompletnością NP z pewnością nie są w BQP. (Jeśli problem jest kompletny dla klasy złożoności, oznacza to, że jeśli możesz go rozwiązać skutecznie, możesz skutecznie rozwiązać wszystkie instancje klasy.) Jest to więc rodzaj wskazówek, w których można szukać algorytmów kwantowych .

Dodatkową subtelnością, która komplikuje sprawy, jest jednak z grubsza (nie jestem ekspertem), że klasy złożoności mówią o złożoności najgorszego przypadku, tj. Dla danego rozmiaru problemu, chodzi o to, jak trudny jest najtrudniejszy możliwy problem. Ale może istnieć tylko jeden taki problem, co oznaczałoby, że jeśli naprawimy rozmiar problemu (w standardzie, np. Możesz mówić o 1024 bitowym RSA; 1024 bity to rozmiar problemu), to będzie tylko jeden klucz prywatny. Jeśli to wiemy, podsłuchujący może po prostu użyć tego klucza prywatnego do odszyfrowania wiadomości. Tak naprawdę potrzebujemy, aby to rozumowanie złożoności obliczeniowej dotyczyło dużej części możliwych danych wejściowych. To wprowadza Cię w świat złożonej średniej wielkości przypadków, w którym, jak rozumiem, takie stwierdzenia stają się znacznie trudniejsze.

Może to pomóc w porównaniu z RSA, krypto-systemem klucza publicznego i ignorowaniem istnienia komputerów kwantowych. Opiera się na trudności faktorowania dużych liczb zespolonych. Ten problem nie jest (jak się uważa) w P, więc uważa się, że haker z klasycznym komputerem ma trudności z uzyskaniem odpowiedzi. Tymczasem jest w NP, ponieważ rozwiązanie jest łatwo weryfikowane (jeśli masz jeden czynnik, możesz łatwo sprawdzić, czy to czynnik). Oznacza to, że prawy odbiorca może go odszyfrować za pomocą klasycznego komputera.

Czy istnieje jakaś definicja lub twierdzenie o tym, co komputer kwantowy może osiągnąć, z których schematy kryptograficzne po kwantowej (np. Kryptografia sieciowa, ale nie kryptografia kwantowa) mogą uzasadniać ich bezpieczeństwo?

Nie. Tylko dlatego, że twój postkrytyczny schemat kryptograficzny działa dzisiaj, nie oznacza, że ​​Peter Shor nie znajdzie algorytmu kwantowego, aby go złamać jutro. ”

Wiem, że funkcja znajdowania okresu jest w stanie złamać RSA i dyskretne dzienniki, ale czy jest to jedyny algorytm mający znaczenie dla zerwania schematów szyfrowania?

Nie. Przykładem innego algorytmu jest algorytm Grovera, który jest istotny w przypadku łamania kryptosystemów w oparciu o problem z logarytmem transcendentalnym .

Czy mogę powiedzieć, że jeśli schemat nie jest podatny na funkcję znajdowania okresu, nie jest podatny na obliczenia kwantowe?

Nie. Schematy oparte na problemie logarytmu transcendentalnego nie są podatne na znalezienie okresu, ale są podatne na przyspieszenie kwantowe.

Jeśli nie, to czy istnieje podobne, alternatywne zdanie w formie „jeśli schemat szyfrowania nie może zostać złamany przez algorytm X, nie można go złamać za pomocą obliczeń kwantowych”?

Nie. Nie znamy każdego możliwego algorytmu kwantowego. Nawet jeśli schemat jest odporny na wyszukiwanie okresów i algorytm Grovera, możliwe byłoby użycie komputerów kwantowych do złamania go bardziej skutecznie niż klasyczne komputery. Być może będziemy musieli sprawić, by Peter Shor był wystarczająco zainteresowany, aby opracować dla niego schemat odszyfrowywania wzmocniony kwantowo.

Czy wystarczy udowodnić, że schemat szyfrowania można złamać tylko poprzez wypróbowanie wszystkich możliwych kluczy, a najlepszym sposobem, w jaki obliczenia kwantowe mogą to zrobić, jest czas wyszukiwania pierwiastka kwadratowego z algorytmem Grovera?

Nie. Tylko dlatego, że klasyczny komputer nie może złamać twojego schematu, chyba że wypróbuje wszystkie możliwe klucze, nie oznacza, że ​​komputer kwantowy nie może.

Oto pytanie, na które odpowiedź brzmi „ tak” :

Co możemy zrobić, aby udowodnić, że schemat szyfrowania jest bezpieczny przed komputerami kwantowymi?

Odpowiedź: Udowodnij, że odszyfrowanie kodu jest kompletnym QMA lub trudnym problemem QMA. Trudne problemy QMA to problemy trudne dla komputerów kwantowych, ponieważ trudne problemy NP są trudne dla klasycznych komputerów.

Zainspirowało mnie to do zadania tego pytania, na które nie znam odpowiedzi!