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

Материал из WEGA
Перейти к навигации Перейти к поиску
 
(не показаны 4 промежуточные версии этого же участника)
Строка 10: Строка 10:




'''Теорема 1. Пусть дана функция типа «r к 1» <math>F: X \to Y, r \ge 2</math>, и целое число <math>1 \le k \le N = |X|</math>. Алгоритм Collision(F, k) возвращает коллизию после ожидаемого числа <math>O(k + \sqrt{N/(rk)})</math> оценок F с использованием <math>\Theta(k)</math> ячеек памяти. В частности, при <math>k = \sqrt[3]{N/r}</math> алгоритм Collision(F, k) использует <math>O(\sqrt[3]{N/r})</math> ожидаемых оценок и <math>\Theta(\sqrt[3]{N/r})</math> ячеек памяти.'''
'''Теорема 1. Пусть дана функция типа «r к 1» <math>F: X \to Y, r \ge 2</math>, и целое число <math>1 \le k \le N = |X|</math>. Алгоритм Collision(F, k) возвращает коллизию после ожидаемого числа <math>O(k + \sqrt{N/(rk)})</math> оценок F с использованием <math>\Theta(k)</math> ячеек памяти. В частности, при <math>k = \sqrt[3]{N/r}</math> алгоритм Collision(F, k) использует <math>O(\sqrt[3]{N/r})</math> ожидаемых оценок F и <math>\Theta(\sqrt[3]{N/r})</math> ячеек памяти.'''




Следствие 2. Существует квантовый алгоритм, способный найти коллизию в произвольной функции F: X ! Y для любого значения r > 2, используя объем памяти S и ожидаемое число O(T) оценок F для каждого 1 < S < T при условии, что
'''Следствие 2'''. Существует квантовый алгоритм, способный найти коллизию в произвольной функции типа «r к 1» <math>F: X \to Y</math> для любого <math>r \ge 2</math>, используя объем памяти S и ожидаемое число O(T) оценок F для каждого <math>1 \le S \le T</math> при условии <math>S T^2 \ge |F(X)|</math>, где F(X) обозначает образ F.
ST2 > jF(X)j,
где F(X) обозначает образ F.




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




Collision (F,k)
'''Collision (F, k)'''


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


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


3. Проверить, содержит ли L коллизию – то есть существуют ли отдельные элементы (X0;F(X0));(X1;F(X1)) 2 L, для которых F(X0) = F(x1). Если да, перейти к шагу 6.
3. Проверить, содержит ли L коллизию – то есть существуют ли различные элементы <math>(x_0,F(x_0)),(x_1, F(x_1)) \in L</math>, для которых <math>F(x_0) = F(x_1)</math>. Если да, перейти к шагу 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 нет коллизий).
4. Вычислить <math>x_1 = Grover(H, 1)</math>, где <math>H: X \to \{ 0, 1 \}</math> обозначает функцию, определяемую следующим образом: H(x) = 1 тогда и только тогда, когда существует <math>x_0 \in K</math>, такой, что <math>(x_0, F(x)) \in L</math>, но <math>x \ne x_0</math>.  (Заметим, что если <math>x_0</math> существует, то он является уникальным, поскольку мы уже проверили, что в L нет коллизий).


5. Find(x0;F(x1)) 2 L.
5. Найти <math>(x_0, F(x1)) \in L</math>.


6. Вывести результат в виде коллизии FX0; X1G.
6. Вывести результат в виде коллизии <math> \{ x_0, x_1 \} </math>.


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


== См. также ==
== См. также ==

Текущая версия от 22:09, 14 января 2023

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

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

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

Требуется: найти такие [math]\displaystyle{ x_1 }[/math] и [math]\displaystyle{ x_2 }[/math], что [math]\displaystyle{ F(x_1) = F(x_2) }[/math].

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

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


Теорема 1. Пусть дана функция типа «r к 1» [math]\displaystyle{ F: X \to Y, r \ge 2 }[/math], и целое число [math]\displaystyle{ 1 \le k \le N = |X| }[/math]. Алгоритм Collision(F, k) возвращает коллизию после ожидаемого числа [math]\displaystyle{ O(k + \sqrt{N/(rk)}) }[/math] оценок F с использованием [math]\displaystyle{ \Theta(k) }[/math] ячеек памяти. В частности, при [math]\displaystyle{ k = \sqrt[3]{N/r} }[/math] алгоритм Collision(F, k) использует [math]\displaystyle{ O(\sqrt[3]{N/r}) }[/math] ожидаемых оценок F и [math]\displaystyle{ \Theta(\sqrt[3]{N/r}) }[/math] ячеек памяти.


Следствие 2. Существует квантовый алгоритм, способный найти коллизию в произвольной функции типа «r к 1» [math]\displaystyle{ F: X \to Y }[/math] для любого [math]\displaystyle{ r \ge 2 }[/math], используя объем памяти S и ожидаемое число O(T) оценок F для каждого [math]\displaystyle{ 1 \le S \le T }[/math] при условии [math]\displaystyle{ S T^2 \ge |F(X)| }[/math], где F(X) обозначает образ F.


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


Collision (F, k)

1. Выбрать произвольное подмножество [math]\displaystyle{ K \subseteq X }[/math] мощности k. Построить таблицу L размера k, каждый элемент которой содержит отдельную пару (x, F(x)), [math]\displaystyle{ x \in K }[/math].

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

3. Проверить, содержит ли L коллизию – то есть существуют ли различные элементы [math]\displaystyle{ (x_0,F(x_0)),(x_1, F(x_1)) \in L }[/math], для которых [math]\displaystyle{ F(x_0) = F(x_1) }[/math]. Если да, перейти к шагу 6.

4. Вычислить [math]\displaystyle{ x_1 = Grover(H, 1) }[/math], где [math]\displaystyle{ H: X \to \{ 0, 1 \} }[/math] обозначает функцию, определяемую следующим образом: H(x) = 1 тогда и только тогда, когда существует [math]\displaystyle{ x_0 \in K }[/math], такой, что [math]\displaystyle{ (x_0, F(x)) \in L }[/math], но [math]\displaystyle{ x \ne x_0 }[/math]. (Заметим, что если [math]\displaystyle{ x_0 }[/math] существует, то он является уникальным, поскольку мы уже проверили, что в L нет коллизий).

5. Найти [math]\displaystyle{ (x_0, F(x1)) \in L }[/math].

6. Вывести результат в виде коллизии [math]\displaystyle{ \{ x_0, x_1 \} }[/math].

Применение

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

См. также

Литература

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)