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

Материал из WEGA
Перейти к навигации Перейти к поиску

Постановка задачи

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

Дано: функция F типа «r к 1».

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

Основные результаты

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


Теорема 1. Пусть дана функция типа «r к 1» F:XY,r2, и целое число 1kN=|X|. Алгоритм Collision(F, k) возвращает коллизию после ожидаемого числа O(k+N/(rk)) оценок F с использованием Θ(k) ячеек памяти. В частности, при k=N/r3 алгоритм Collision(F, k) использует O(N/r3) ожидаемых оценок F и Θ(N/r3) ячеек памяти.


Следствие 2. Существует квантовый алгоритм, способный найти коллизию в произвольной функции типа «r к 1» F:XY для любого r2, используя объем памяти S и ожидаемое число O(T) оценок F для каждого 1ST при условии ST2|F(X)|, где F(X) обозначает образ F.


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


Collision (F, k)

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

2. Отсортировать L в соответствии со второй записью в каждом элементе L.

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

4. Вычислить x1=Grover(H,1), где H:X{0,1} обозначает функцию, определяемую следующим образом: H(x) = 1 тогда и только тогда, когда существует x0K, такой, что (x0,F(x))L, но xx0. (Заметим, что если x0 существует, то он является уникальным, поскольку мы уже проверили, что в L нет коллизий).

5. Найти (x0,F(x1))L.

6. Вывести результат в виде коллизии {x0,x1}.

Применение

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

См. также

Литература

1. Aaronson, S., Shi, Y.: Quantum Lower Bounds for the Collision and the Element Distinctness Problems. J. ACM 51 (4), 595-605 (2004)

2. Boyer, M., Brassard, G., Hayer, P., Tapp A.: Tight bounds on quantum searching. Fortschr. Phys. 46(4-5), 493-505 (1998)

3. Brassard, G., Hayer, P., Mosca, M., Tapp A.: Quantum Amplitude Amplification and Estimation. In: Lomonaco, S.J. (ed.) Quantum Computation & Quantum Information Science, AMS Contemporary Mathematics Series Millennium Volume, vol. 305, pp. 53-74. American Mathematical Society, Providence (2002)

4. Brassard, G., Hayer, P., Tapp, A.: Quantum Algorithm for the Collision Problem. 3rd Latin American Theoretical Informatics Symposium (LATIN'98). LNCS, vol. 1380, pp. 163-169. Springer (1998)

5. Carter, J.L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143-154 (1979)

6. Grover, L.K.: A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212-219. ACM (1996)

7. Stinson, D.R.: Cryptography: Theory and Practice, CRC Press, Inc (1995)

8. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)