Zagrożenie kwantowe: Która kryptografia umiera, a która przeżywa? (Albo: Dlaczego ZK-STARKs są bezpieczne w erze PQ?) Wcześniej wyjaśniłem, jak działa komputer kwantowy: Wyobraź sobie rozwiązywanie problemu jako próbę ucieczki z labiryntu. Jest wiele możliwych ścieżek i musisz sprawdzić każdą z nich, aż znajdziesz wyjście. Tak działa klasyczny (niekwantowy) komputer. Jednak prawa mechaniki kwantowej pozwalają na lepsze rozwiązania. Pozwalają systemowi (grupie cząstek) równolegle badać *wszystkie* różne ścieżki w labiryncie. Ścieżki, które prowadzą do wyjścia, pozostają możliwe, podczas gdy te, które prowadzą do ślepego zaułka, znikają. Następnie wszechświat losowo wybiera jedną z pozostałych możliwych ścieżek (to jest ta część, której Einstein nie lubił, mówiąc "Bóg nie gra w kości", tylko on naprawdę to robi). Tak komputer kwantowy rozwiązuje problemy, które zajęłyby klasycznemu komputerowi miliony lat. Jednak istnieją rodzaje prymitywów kryptograficznych, które mogą być złamane przez komputer kwantowy, oraz takie, które pozostają bezpieczne. Jak to możliwe? W moim poprzednim wyjaśnieniu pominąłem kluczowy element: Nie wszystkie labirynty są takie same. Są takie labirynty, w których ścieżki prowadzące do ślepych zaułków znikają, pozostawiając wszechświatowi tylko dobrą ścieżkę prowadzącą do wyjścia. Nazywam je "labiryntami łatwymi dla kwantów", ponieważ gdy wszechświat próbuje wybrać ścieżkę dla takiego labiryntu, zawsze będzie to ścieżka prowadząca do wyjścia. Łatwo dotrzeć do końca labiryntu oznacza łatwość w złamaniu. Jednak w "labiryntach trudnych dla kwantów" wszystkie ścieżki pozostają "żywe", niezależnie od tego, czy prowadzą do ślepego zaułka, czy do wyjścia. Dla takiego labiryntu komputer kwantowy nie jest lepszy od klasycznego komputera. Gdy Bóg rzuca kostką i wybiera ścieżkę, wszystkie ścieżki – dobre i złe – mają równe szanse na pojawienie się. Więc komputer kwantowy wykonuje analogię klasycznego komputera, losowo sprawdzając jedną ścieżkę w labiryncie. Teraz prawdopodobnie się zastanawiasz: Które labirynty są łatwe dla kwantów, a które nie? ...