Алгоритм Гровера
На английском языке: 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-2012, как правило, используемые в связке с симметричными.
Уже в ближайшей перспективе потребуется переход на алгоритмы постквантовой криптографии.
Уже в ближайшей перспективе потребуется переход на алгоритмы постквантовой криптографии.
Какие меры следует предпринять для защиты ваших систем информационной безопасности от квантовой угрозы?
Для того, чтобы использовать постквантовую криптографию уже сегодня, вы можете воспользоваться нашим программным решением — библиотекой квантово-устойчивых алгоритмов PQLR SDK.
Для того, чтобы использовать постквантовую криптографию уже сегодня, вы можете воспользоваться нашим программным решением — библиотекой квантово-устойчивых алгоритмов PQLR SDK.