Czy obliczenia kwantowe mogłyby zostać ostatecznie wykorzystane do tego, aby współczesne hashowanie stało się banalne?

Mówiąc najprościej, gdyby zbudować kwantowe urządzenie obliczeniowe o mocy, powiedzmy, 20 kubitów, czy takiego komputera można by użyć do tego, aby jakikolwiek współczesny algorytm mieszający był bezużyteczny?

Czy byłoby możliwe wykorzystanie mocy obliczeń kwantowych w tradycyjnej aplikacji obliczeniowej?

Komputery kwantowe mogą w niektórych przypadkach mieć pewną przewagę nad komputerami klasycznymi. Najbardziej niezwykłym przykładem jest algorytm Shora, który może uwzględniać dużą liczbę w czasie wielomianowym (podczas gdy klasycznie najbardziej znany algorytm zajmuje czas wykładniczy). To całkowicie łamie schematy, takie jak RSA, oparte na twardości faktoryzacji.

Nie jest tak w przypadku funkcji skrótu. Najpierw musimy zdefiniować, co to znaczy przerwać funkcję skrótu. Jeden ze sposobów na przełamanie to atak przed obrazem : dajesz mi wartość skrótu , a ja muszę znaleźć komunikat m taki, że hash ( m ) = v . Kolejnym atakiem jest atak kolizyjny , w którym nic mi nie dajesz, a ja muszę wymyślić dwie różne wiadomości m 1 , $v$$m$$\operatorname{hash}(m)=v$ które mają ten sam skrót hash ( m 1 ) = hash ( m 2$m_1, m_2$$\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$. Jest to łatwiejsze niż znalezienie preimage, ponieważ nie jestem związany z konkretnym .$v$

Co mogą zrobić komputery kwantowe? Głównym rezultatem jest algorytm wyszukiwania Grovera : metoda wyszukiwania przez komputer kwantowy nieposortowanej bazy danych o rozmiarze z czasem O ( $N$(choć klasycznie zajmie to oczekiwany czasN/2).$O(\sqrt{N})$$N/2$

W przypadku algorytmu Grovera znalezienie pierwiastka z funkcji skrótu, którego wyjściem jest bit, zajmuje O ( 2 $k$, a nieO(2k).$O(2^{k/2})$$O(2^k)$

Czy to jest problem ? Niekoniecznie. Funkcje skrótu są zaprojektowane tak, że czas jest uważany za „bezpieczny” (innymi słowy, projektanci skrótu zawsze podwajają k ). Wynika to z paradoksu urodzinowego, przy pomocy którego klasyczny kolizja jest możliwa do znalezienia w czasie O ( 2 k / 2 ) .$2^{k/2}$$k$$O(2^{k/2})$

Zaletą algorytmu Grovera jest to, że jest optymalny - każdy inny algorytm kwantowy do znalezienia elementu w nieposortowanej bazie danych będzie działał w czasie .$\Omega(\sqrt{N})$

Czy komputery kwantowe mogą przeprowadzać lepsze ataki zderzeniowe ? Właściwie nie jestem tego pewien. Algorytm Grovera można rozszerzyć, tak aby w przypadku elementów (czyli obrazów wstępnych) czas na znalezienie jednego został skrócony do O ( $t$. Ale to nie powoduje kolizji - ponowne uruchomienie algorytmu może zwrócić ten sam obraz. Z drugiej strony, jeśli wybierzemym1losowo, a następnie użyjemy algorytmu Grovera, prawdopodobne jest, że zwróci on inny komunikat. Nie jestem pewien, czy to daje lepsze ataki.$O(\sqrt{N/t})$$m_1$

_{(odpowiada to na bardziej ogólne pytanie, bez ograniczania komputera do 20 kubitów, co nie wystarczy do zerwania obecnych 1024-bitowych skrótów).}

Z tego, co rozumiem, obliczenia kwantowe mają moc łatwego łamania dzisiejszych algorytmów mieszających. Jednak w dłuższej perspektywie będziemy mogli również używać bardziej złożonych algorytmów mieszających i ogólnie łatwiej jest zaszyfrować niż coś odszyfrować. Myślę, że największe problemy należy wziąć pod uwagę, gdy obliczenia kwantowe są dostępne tylko dla nielicznych wybranych, zapewniając im łatwy dostęp do rzeczy chronionych przez dzisiejsze algorytmy na długo przed rozpowszechnieniem bardziej zaawansowanych algorytmów lub nawet świadomości zagrożenia.

Zobacz tutaj faktycznie techniczną odpowiedź na pytanie dotyczące przepełnienia stosu.