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

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

Пусть — конечные множества и , две функции. Пара называется клешней , если . Задача поиска когтей определяется как поиск такого когтя при условии, что он существует. ${\ Displaystyle А, В, С}$ ${\ Displaystyle е: А \ в С}$ ${\ Displaystyle г: В \ в С}$ ${\ Displaystyle (х, у) \ в А \ раз В}$ ${\ Displaystyle е (х) = г (у)}$

Если мы рассматриваем случайные функции, мы ожидаем, что коготь будет существовать тогда и только тогда . Точнее, есть ровно пары вида с ; вероятность того, что такая пара является когтем, равна . Итак, если , ожидаемое количество клешней не менее 1. ${\ Displaystyle е, г}$ ${\ Displaystyle | А | \ cdot | B | \ geq | C |}$ ${\ Displaystyle | А | \ cdot | В |}$ ${\ Displaystyle (х, у)}$ ${\ Displaystyle х \ в А, у \ в В}$ ${\ Displaystyle 1 / | С |}$ ${\ Displaystyle | А | \ cdot | B | \ geq | C |}$