Dzięki nowemu algorytmowi komputery kwantowe mogą złamać szyfrowanie wcześniej, niż oczekiwano

Opublikowane ponownie przez Plato

Obserwuje: 0

Jednym z najbardziej ugruntowanych i przełomowych zastosowań przyszłego komputera kwantowego jest możliwość złamania szyfrowania. Nowy algorytm mógłby znacznie obniżyć barierę w osiągnięciu tego celu.

Pomimo całego szumu wokół obliczeń kwantowych, wokół nich wciąż pojawiają się istotne znaki zapytania do czego tak naprawdę przydadzą się komputery kwantowe. Istnieją nadzieje, że uda im się przyspieszyć wszystko, od procesów optymalizacji po uczenie maszynowe, ale w wielu przypadkach nie jest jasne, o ile będą one łatwiejsze i szybsze.

Jedno jest jednak pewne: wystarczająco mocny komputer kwantowy może sprawić, że nasze wiodące schematy kryptograficzne staną się bezwartościowe. Chociaż leżące u ich podstaw zagadki matematyczne są praktycznie nierozwiązywalne za pomocą klasycznych komputerów, byłyby one całkowicie wykonalne w przypadku wystarczająco dużego komputera kwantowego. Stanowi to problem, ponieważ systemy te zabezpieczają większość naszych informacji w Internecie.

Oszczędność polega na tym, że dzisiejsze procesory kwantowe są dalekie od wymaganej skali. Ale według A zgłoś w naukaInformatyk z Uniwersytetu Nowojorskiego Oded Regev odkrył nowy algorytm, który może znacznie zmniejszyć liczbę wymaganych kubitów.

Podejście to zasadniczo zmienia jeden z najskuteczniejszych dotychczas algorytmów kwantowych. W 1994 roku Peter Shor z MIT opracował sposób obliczenia, które liczby pierwsze należy pomnożyć przez siebie, aby otrzymać konkretną liczbę — problem znany jako faktoring pierwszy.

W przypadku dużych liczb jest to niezwykle trudny problem, który szybko staje się niemożliwy do rozwiązania na konwencjonalnych komputerach, dlatego wykorzystano go jako podstawę popularnego schematu szyfrowania RSA. Jednak wykorzystując zjawiska kwantowe, takie jak superpozycja i splątanie, algorytm Shora może rozwiązać te problemy nawet w przypadku niewiarygodnie dużych liczb.

Fakt ten wywołał panikę wśród ekspertów ds. bezpieczeństwa, między innymi dlatego, że hakerzy i szpiedzy mogą dziś odkurzać zaszyfrowane dane, a następnie po prostu czekać, aż wypracują wystarczająco wydajne komputery kwantowe, aby je złamać. I chociaż opracowano standardy szyfrowania postkwantowego, wdrożenie ich w Internecie może zająć wiele lat.

Prawdopodobnie będzie to jednak dość długie oczekiwanie. Większość implementacji RSA opiera się na kluczach o długości co najmniej 2048 bitów, co odpowiada liczbie o długości 617 cyfr. Badacze Fujitsu niedawno obliczone że całkowicie odporny na awarie komputer kwantowy z 10,000 104 kubitów potrzebowałby XNUMX dni na złamanie tak dużej liczby.

Jednak nowy algorytm Regeva, opisany w a preprint opublikowany w dn arXiv, mogłoby potencjalnie znacząco ograniczyć te wymogi. Regev zasadniczo przerobił algorytm Shora w taki sposób, że możliwe jest znalezienie czynników pierwszych liczby przy użyciu znacznie mniejszej liczby kroków logicznych. Wykonywanie operacji na komputerze kwantowym polega na tworzeniu małych obwodów z kilku kubitów, zwanych bramkami, które wykonują proste operacje logiczne.

W oryginalnym algorytmie Shora liczba bramek wymaganych do rozłożenia liczby na czynniki jest kwadratem liczby bitów użytych do jej przedstawienia, co oznacza się jako n². Podejście Regeva wymagałoby jedynie n^1.5 bramek, ponieważ wyszukuje czynniki pierwsze, wykonując mniejsze mnożenia wielu liczb, a nie bardzo duże mnożenia pojedynczej liczby. Zmniejsza także liczbę bramek wymaganych poprzez zastosowanie klasycznego algorytmu do dalszego przetwarzania wyników.

W artykule Regev szacuje, że w przypadku liczby 2048-bitowej mogłoby to zmniejszyć liczbę wymaganych bramek o dwa do trzech rzędów wielkości. Jeśli to prawda, mogłoby to umożliwić znacznie mniejszym komputerom kwantowym złamanie szyfrowania RSA.

Istnieją jednak praktyczne ograniczenia. Na początek Regev zauważa, że algorytm Shora korzysta z szeregu optymalizacji opracowanych przez lata, które zmniejszają liczbę kubitów wymaganych do jego uruchomienia. Nie jest jeszcze jasne, czy te optymalizacje sprawdzą się w przypadku nowego podejścia.

Powiedział także Martin Ekerå, badacz obliczeń kwantowych pracujący dla szwedzkiego rządu nauka że algorytm Regeva wydaje się potrzebować pamięci kwantowej do przechowywania wartości pośrednich. Zapewnienie, że pamięć będzie wymagać dodatkowych kubitów i wykorzysta całą przewagę obliczeniową, jaką posiada.

Niemniej jednak nowe badanie w odpowiednim czasie przypomina, że jeśli chodzi o zagrożenie, jakie informatyka kwantowa stanowi dla szyfrowania, słupki bramkowe są w ciągłym ruchu, a przejście na schematy postkwantowe nie może nastąpić wystarczająco szybko.

Kredytowych Image: Google