Jaka jest różnica między krypto klasycznym a krypto postkwantowym?

Czy będzie potrzeba zmiany definicji bezpieczeństwa, jeśli mamy komputery kwantowe? Jakie konstrukcje kryptograficzne się zepsują? Czy znasz ankietę lub artykuł wyjaśniający, co będzie potrzebne do zmiany?

Streszczenie tego artykułu zawiera (częściową) odpowiedź.

Istnieją dwa rodzaje tradycyjnych metod kryptograficznych z kluczem publicznym: metody oparte na faktoryzacji liczb całkowitych i metody oparte na dyskretnym logarytmie, w tym metody oparte na krzywej eliptycznej. Modele te uważa się za trudne w modelach klasycznych, ale wykazano, że żaden z nich nie jest trudny w modelu kwantowym.

Chociaż Grover opracował algorytm kwantowy zapewniający kwadratowe przyspieszenie wyszukiwania, Bennet, Bernstein, Brassard i Vazirani wykazali, że model kwantowy nie pozwala na wykładnicze przyspieszenie problemów wyszukiwania. Sugeruje to, że algorytmy szyfrowania symetrycznego, funkcje jednokierunkowe i skróty kryptograficzne powinny być odporne na ataki kwantowe. Dlatego należy skupić się na opracowaniu bezpiecznych metod klucza publicznego.

Podpisy Lamport mogą stanowić mechanizm jednorazowego podpisu zabezpieczony przed atakami kwantowymi. Problemy z kratą mogą stanowić podstawę metod klucza publicznego odpornych na ataki kwantowe; w szczególności problemy z najkrótszym wektorem i najbliższym wektorem NP są trudne. Zarówno w przypadku modeli klasycznych, jak i kwantowych uważa się, że problemy te są trudne dla sieci o dużych wymiarach. NTRU rodzina algorytmów kryptograficznych, na podstawie kratowych problemów może dostarczyć praktycznych sposobów osiągnięcia klucza publicznego odporny na ataki kwantowej kryptografii. Kolejnym problemem, który może służyć jako podstawa bezpiecznych metod klucza publicznego, jest problem dekodowania syndromu. System szyfrowania McEliece opiera się na tym problemie, a warianty mogą stanowić krok naprzód.

W żadnym wypadku nie jestem ekspertem (ani nawet blisko tego) na ten temat, ale z tego co wiem:

Klasyczna kryptografia zależy od trudnej faktoryzacji (lub problemu z logiem dyskretnym). Jednak faktoring nie jest uważany za kompletny NP i rzeczywiście jest on do rozwiązania w czasie wielomianowym przez komputery kwantowe. Tak więc każda kryptografia, która zależy od tych operacji, zostałaby zerwana (czyli każdy rodzaj kryptografii używany tam, o którym wiem).

Kryptografia kwantowa zależy od mechaniki kwantowej i teoretycznie nie można jej złamać. To wcale nie jest kwestia czasu - po prostu opiera się na przypadkowości, a fakt, że stan mierzy się po zmierzeniu, więc bez odpowiednich informacji najlepszym wyborem jest po prostu „odgadnięcie” wiadomości… co jest bezużyteczne .