Алгоритм Гровера
На английском языке: Grover's Search Algorithm
Коротко
Алгоритм Гровера — это квантовый алгоритм для решения задачи перебора, то есть нахождения решения уравнения вида f(x)=y, где f — булева функция от n переменных. Алгоритм Гровера основан на физическом эффекте «усиления амплитуды» целевого состояния и достигает квадратичного уменьшения оценки трудоемкости задачи поиска решения, то есть вместо O(N) операций, требующихся для полного перебора в классическом случае, квантовый компьютер способен решить эту задачу за O(N1/2) операций. Алгоритм Гровера может быть эффективно применен к задачам криптоанализа. Так, для блочных шифров (AES, Кузнечик и других), квадратичное ускорение взлома методом перебора, достигаемое алгоритмом Гровера, требует увеличения размера ключа в 2 раза для сохранения того же уровня стойкости.
Алгоритм Гровера — это квантовый алгоритм для решения задачи перебора, то есть нахождения решения уравнения вида f(x)=y, где f — булева функция от n переменных. Алгоритм Гровера основан на физическом эффекте «усиления амплитуды» целевого состояния и достигает квадратичного уменьшения оценки трудоемкости задачи поиска решения, то есть вместо O(N) операций, требующихся для полного перебора в классическом случае, квантовый компьютер способен решить эту задачу за O(N1/2) операций. Алгоритм Гровера может быть эффективно применен к задачам криптоанализа. Так, для блочных шифров (AES, Кузнечик и других), квадратичное ускорение взлома методом перебора, достигаемое алгоритмом Гровера, требует увеличения размера ключа в 2 раза для сохранения того же уровня стойкости.
Подробно
Квантовый алгоритм обращения функции методом перебора (также иногда называемый алгоритмом поиска в базе данных), разработанный американским математиком Ловом Гровером в 1996 году, нашел применение в задачах криптоанализа. Для заданной булевой функции f от n переменных алгоритм Гровера способен найти решение уравнения вида f(x)=y за O(N1/2) операций, в то время как классический алгоритм полного перебора требует O(N) операций.
Квантовый алгоритм обращения функции методом перебора (также иногда называемый алгоритмом поиска в базе данных), разработанный американским математиком Ловом Гровером в 1996 году, нашел применение в задачах криптоанализа. Для заданной булевой функции f от n переменных алгоритм Гровера способен найти решение уравнения вида f(x)=y за O(N1/2) операций, в то время как классический алгоритм полного перебора требует O(N) операций.
Если рассматривать задачу дешифрования блочного шифра с длиной ключа n битов как задачу обращения булевой функции, то алгоритм Гровера способен решить эту задачу за 2n/2 операций, в отличие от классической оценки в 2n операций. Таким образом, для сохранения заданного уровня стойкости блочного шифра относительно атак с использованием квантового компьютера, необходимо увеличить длину ключа в 2 раза.
Аналогично, если рассмотреть задачу нахождения прообраза хэш-функции, то для сохранения заданного уровня стойкости потребуется увеличение размера хэш-кода в 2 раза. Отметим, впрочем, что квантовый алгоритм BHT, применяемый для поиска коллизий, является более эффективным и требует увеличения размера хэш-кода в 3 раза.
Аналогично, если рассмотреть задачу нахождения прообраза хэш-функции, то для сохранения заданного уровня стойкости потребуется увеличение размера хэш-кода в 2 раза. Отметим, впрочем, что квантовый алгоритм BHT, применяемый для поиска коллизий, является более эффективным и требует увеличения размера хэш-кода в 3 раза.
Лов Кумар Гровер
Алгоритм Гровера может быть применен и к анализу асимметричных криптографических систем, но в этом случае он, как правило, уступает специализированным алгоритмам, например, полиномиальному квантовому алгоритму Шора для факторизации.
Используемые в настоящее время симметричные криптографические алгоритмы, такие как блочные шифры AES-256 и Кузнечик, хэш-функции SHA-512 и Стрибог, обладают достаточным запасом стойкости относительно алгоритма Гровера. Слабым звеном современных систем информационной безопасности относительно квантовой угрозы являются асимметричные криптографические алгоритмы, такие как RSA, (EC)DSA, ГОСТ Р 34.10-2018, как правило, используемые в связке с симметричными.
Уже в ближайшей перспективе потребуется переход на алгоритмы постквантовой криптографии.
Уже в ближайшей перспективе потребуется переход на алгоритмы постквантовой криптографии.