Можно ли в конечном итоге использовать квантовые вычисления, чтобы сделать современное хэширование тривиальным?

Проще говоря, если бы нужно было создать квантовое вычислительное устройство с мощностью, скажем, 20 кубитов, мог бы такой компьютер быть использован для того, чтобы сделать любой современный алгоритм хеширования бесполезным?

Возможно ли даже использовать мощь квантовых вычислений в традиционных компьютерных приложениях?

Квантовые компьютеры могут иметь некоторые преимущества перед классическими компьютерами в некоторых случаях. Самым замечательным примером является алгоритм Шора, который может множить большое число за полиномиальное время (в то время как классически, самый известный алгоритм занимает экспоненциальное время). Это полностью нарушает схемы типа RSA, основанные на сложности факторизации.

Это не обязательно относится к хеш-функциям. Во-первых, нам нужно определить, что означает разрыв хеш-функции. Один из способов сломать это называется атака перед изображением : вы даете мне значение хеша , и мне нужно найти сообщение m такое, что hash ( m ) = v . Еще одна атака - это столкновительная атака , в которой вы мне ничего не даете, и мне нужно придумать два разных сообщения m 1 , m 2, которые имеют одинаковый хэш ( m 1 ) = hash ( m 2$v$$m$$\operatorname{hash}(m)=v$$m_1, m_2$$\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$, Это проще, чем найти прообраз, так как я не связан с конкретным .$v$

Что могут сделать компьютеры Quantum? Основным результатом является алгоритм поиска Гровера : метод квантового компьютера для поиска в несортированной базе данных размера со временем O ( $N$(хотя классически это займет ожидаемое времяN/2).$O(\sqrt{N})$$N/2$

С помощью алгоритма Гровера нахождение прообраза хеш-функции с выходным значением бит занимает O ( 2 k / 2 ) времени, а не O ( 2 k ) .$k$$O(2^{k/2})$$O(2^k)$

Это проблема ? Не обязательно. Хеш-функции спроектированы таким образом, что время считается «безопасным» (другими словами, конструкторы хеш-функции всегда удваивают к ). Это связано с парадоксом Дня Рождения, с которым нахождение столкновения возможно со временем O ( 2 k / 2 ) на классическом компьютере.$2^{k/2}$$k$$O(2^{k/2})$

Хорошая особенность алгоритма Гровера в том, что он оптимален - любой другой квантовый алгоритм для нахождения элемента в несортированной базе данных будет выполняться за время .$\Omega(\sqrt{N})$

Могут ли квантовые компьютеры лучше атаковать при столкновении ? На самом деле я не уверен в этом. Алгоритм Гровера может быть расширен, так что если имеется элементов (то есть прообразов), время на их поиск сокращается до O ( $t$. Но это не дает столкновения - повторный запуск алгоритма может вернуть тот же прообраз. С другой стороны, если мы выберемm1случайным образом, а затем воспользуемся алгоритмом Гровера, вполне вероятно, что он вернет другое сообщение. Я не уверен, дает ли это лучшие атаки.$O(\sqrt{N/t})$$m_1$

_{(это отвечает на более общий вопрос, не ограничивая компьютер 20 кубитами, которых будет недостаточно для взлома текущих 1024-битных хэшей).}

Из того, что я понимаю, квантовые вычисления способны легко сломать современные алгоритмы хеширования. Однако в долгосрочной перспективе мы также сможем использовать более сложные алгоритмы хеширования, и, как правило, их легче зашифровать, чем что-то расшифровать. Я думаю, что самые большие проблемы, которые следует рассмотреть, - это когда квантовые вычисления доступны только избранным, предоставляя им легкий доступ к вещам, защищенным современными алгоритмами, задолго до того, как распространятся более продвинутые алгоритмы или даже осознание угрозы.

Смотрите здесь, чтобы получить технический ответ на вопрос о переполнении стека.