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

18

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

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

hakusaro
источник
Смежный, но не повторяющийся вопрос: cs.stackexchange.com/questions/356/… (обратите внимание, что пока у нас нет эффективных алгоритмов для решения NP-сложных задач с квантовым компьютером)
Кен Ли,
Можете ли вы указать на результаты, которые вызывают у вас это подозрение? Почему квантовые биты должны иметь какое-либо влияние в этом сценарии?
Рафаэль

Ответы:

13

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

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

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

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

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

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

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

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

Ран Г.
источник
Нитпик: время выполнения GNFS является субэкспоненциальным.
CodesInChaos
1

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

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

Рахул Гупта-Ивасаки
источник
2
AFAIK большинство симметричных крипто примитивов все еще будет безопасным, даже когда квантовые вычисления станут жизнеспособными. В некоторых сценариях он вдвое уменьшает эффективную длину блока или ключа, но крипто-примитивы с текущим уровнем безопасности 256 бит или более будут по-прежнему безопасными, поскольку работа порядка 128 бит невозможна. Большинство асимметричных примитивов, используемых в настоящее время, будут полностью разрушены. Но не только с 20 кубитами. Для этого вам понадобится несколько тысяч кубитов.
CodesInChaos