Проблема с поиском когтей

— Задача поиска когтей классическая задача теории сложности , имеющая несколько приложений в криптографии . Короче говоря, для данных двух функций f , g , рассматриваемых как оракулы , проблема состоит в том, чтобы найти x и y , такие как f ( x ) = g ( y ). Пара ( x , y ) тогда называется клешней . Некоторые проблемы, особенно в криптографии, лучше всего решаются, если рассматривать их как задачу поиска когтей, поэтому любое алгоритмическое улучшение решения проблемы поиска когтей обеспечивает лучшую атаку на криптографические примитивы, такие как хэш-функции .

Определение

Позволять $A,B,C$ быть конечными множествами, и $f:A\to C$ , $g:B\to C$ две функции. Пара $(x,y)\in A\times B$ называется клешней, если $f(x)=g(y)$ . Задача поиска клешни определяется как найти такую клешню, если она существует.

Если мы посмотрим $f,g$ как случайные функции, мы ожидаем, что клешня существует тогда и только тогда, когда $|A|\cdot |B|\geq |C|$ . Точнее, есть именно $|A|\cdot |B|$ пары формы $(x,y)$ с $x\in A,y\in B$ ; вероятность того, что такая пара является клешней, равна $1/|C|$ . Итак, если $|A|\cdot |B|\geq |C|$ , ожидаемое количество клешней не менее 1.

Алгоритмы

Если используются классические компьютеры, лучший алгоритм аналогичен атаке « Встреча посередине» , впервые описанной Диффи и Хеллманом . ^[1] Алгоритм работает следующим образом: предположим $|A|\leq |B|$ . Для каждого $x\in A$ , сохрани пару $(f(x),x)$ в хеш-таблице, индексированной $f(x)$ . Тогда для каждого $y\in B$ , посмотрите таблицу на $g(y)$ . Если такой индекс существует, мы нашли коготь. Этот подход требует времени $O(|A|+|B|)$ и память $O(|A|)$ .

Если использовать квантовые компьютеры , Сейитиро Тани показал, что коготь можно найти по сложности

${\sqrt[{3}]{|A|\cdot |B|}}$ если $|A|\leq |B|<|A|^{2}$ и

${\sqrt {|B|}}$ если $|B|\geq |A|^{2}$ . ^[2]

Шэнъюй Чжан показал, что асимптотически эти алгоритмы являются наиболее эффективными из возможных. ^[3]

Приложения

Как уже отмечалось, большинство приложений задачи поиска когтей встречаются в криптографии . Примеры включают в себя:

коллизий Обнаружение в криптографических хеш-функциях .
Атаки «встреча посередине» : с помощью этой техники можно найти k бит раундовых ключей примерно за 2 времени. ^к/2+1. Здесь f — шифрование на полпути, а g — расшифровка на полпути. Вот почему Triple DES применяет DES три раза, а не только два.

Ссылки

^ Диффи, Уитфилд; Хеллман, Мартин Э. (июнь 1977 г.). «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF) . Компьютер . 10 (6): 74–84. дои : 10.1109/CM.1977.217750 .
^ Тани, Сейитиро (ноябрь 2009 г.). «Алгоритмы поиска когтей с использованием квантовой прогулки». Теоретическая информатика . 410 (50): 5285–5297. arXiv : 0708.2584 . дои : 10.1016/j.tcs.2009.08.030 .
^ Чжан, Шэнъюй (2005). «Обещанный и распределенный квантовый поиск». Вычисления и комбинаторика . Конспекты лекций по информатике. Том. 3595. Шпрингер Берлин Гейдельберг. стр. 430–439. дои : 10.1007/11533719_44 . ISBN 978-3-540-28061-3 .

[1] Диффи, Уитфилд; Хеллман, Мартин Э. (июнь 1977 г.). «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF) . Компьютер . 10 (6): 74–84. дои : 10.1109/CM.1977.217750 .

[2] Тани, Сейитиро (ноябрь 2009 г.). «Алгоритмы поиска когтей с использованием квантовой прогулки». Теоретическая информатика . 410 (50): 5285–5297. arXiv : 0708.2584 . дои : 10.1016/j.tcs.2009.08.030 .

[3] Чжан, Шэнъюй (2005). «Обещанный и распределенный квантовый поиск». Вычисления и комбинаторика . Конспекты лекций по информатике. Том. 3595. Шпрингер Берлин Гейдельберг. стр. 430–439. дои : 10.1007/11533719_44 . ISBN 978-3-540-28061-3 .

[1]

[2]

[3]