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

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

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

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

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

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

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

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

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

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

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