Квантовый алгоритм для решения задачи поиска коллизий: различия между версиями

Функция F называется функцией типа «r к 1», если если каждый элемент ее образа имеет ровно r различных прообразов.

'''Требуется:''' найти такие x1 и x2, что F(x1) = F(x2).

Представленный здесь алгоритм находит коллизии в произвольной функции F типа «r к 1», выполнив всего O(3N/r) ожидаемых оценок F. Алгоритм использует функцию как «черный ящик», то есть единственное, что требуется алгоритму – это способность оценить функцию. В предположении, что функция задается черным ящиком, алгоритм является оптимальным [1] и более эффективным, чем наилучший возможный классический алгоритм, имеющий сложность в запросах Q(\/N/r). Этот результат точно сформулирован в следующей теореме и следствии.

Теорема 1. Пусть дана функция типа «r к 1» F: X ! Y, r > 2, и целое число 1 < k < N = jXj. Алгоритм Collision(F, k) возвращает коллизию после ожидаемого числа O(k+pN/(rk)) оценок F с использованием 0(k) ячеек памяти. В частности, при k = p3N/r алгоритм Collision(F, k) использует O(3N/r) ожидаемых оценок и ячеек памяти.

Следствие 2. Существует квантовый алгоритм, способный найти коллизию в произвольной функции F: X ! Y для любого значения r > 2, используя объем памяти S и ожидаемое число O(T) оценок F для каждого 1 < S < T при условии, что

ST2 > jF(X)j,

где F(X) обозначает образ F.

Алгоритм использует в качестве процедуры версию алгоритма поиска Гровера. Если дана функция H с размером области n и цель y, Grover(H, y) возвращает x, такой, что H(x) = y, за ожидаемое число O(pn) оценок H.

Collision (F,k)

1. Выбрать произвольное подмножество K С X мощности k. Построить таблицу L размера k, каждый элемент которой содержит отдельную пару (x, F(x)), x 2 K.

3. Проверить, содержит ли L коллизию – то есть существуют ли отдельные элементы (X0;F(X0));(X1;F(X1)) 2 L, для которых F(X0) = F(x1). Если да, перейти к шагу 6.

4. Вычислить x1 = Grover(H; 1), где H:X!f0;1g обозначает функцию, определяемую следующим образом: H(x) = 1 тогда и только тогда, когда существует X0 2 K так, что (x0; F(x)) 2 L, но x =6x0.  (Заметим, что x0 является уникальным, если таковой существует, поскольку мы уже проверили, что в L нет коллизий).

5. Find(x0;F(x1)) 2 L.

6. Вывести результат в виде коллизии FX0; X1G.

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