Введение
В математической и компьютерной науке, в области криптографии, тройка чисел (x, y, z) называется когтем двух перестановок f0 и f1, если f0(x) = f1(y) = z. Пара перестановок f0 и f1 считается свободной от когтей, если не существует эффективного алгоритма для нахождения когтя. Термин "свободная от когтей" был введен Голдвассером, Микали и Ривестом в их статье 1984 года "Парадоксальное решение проблемы цифровой подписи" (а позднее в более полной публикации в журнале), где они показали, что существование пар перестановок с ловушкой, свободных от когтей, влечет за собой существование схем цифровой подписи, устойчивых к адаптивным атакам с выбором сообщений. Эта конструкция впоследствии была заменена построением цифровых подписей на основе любой односторонней перестановки с ловушкой. Существование перестановок с ловушкой само по себе не гарантирует существование перестановок, свободных от когтей; однако было показано, что перестановки, свободные от когтей, существуют, если задача факторизации является сложной. Общее понятие перестановки, свободной от когтей (не обязательно с ловушкой), было далее исследовано Иваном Дамгардом в его диссертации "Применение функций, свободных от когтей, в криптографии" (Орхусский университет, 1988), где он показал, как строить хеш-функции, устойчивые к коллизиям, на основе перестановок, свободных от когтей. Понятие свободы от когтей тесно связано с понятием устойчивости к коллизиям в хеш-функциях. Различие заключается в том, что перестановки, свободные от когтей, – это пары функций, для которых сложно создать коллизию между ними, в то время как хеш-функция, устойчивая к коллизиям, – это одна функция, в которой сложно найти коллизию, то есть функция H устойчива к коллизиям, если сложно найти пару различных значений x и y, таких что H(x) = H(y). В литературе по хеш-функциям это обычно называют коллизией хеша. Хеш-функция, для которой сложно найти коллизии, считается обладающей устойчивостью к коллизиям.
f0(x) = f1(y) = z. A pair of permutations f0 and f1 are said to be claw free if there is no efficient algorithm for computing a claw. The terminology claw free was introduced by Goldwasser, Micali, and Rivest in their 1984 paper, "A Paradoxical Solution to the Signature Problem" (and later in a more complete journal paper), where they showed that the existence of claw free pairs of trapdoor permutations implies the existence of digital signature schemes secure against adaptive chosen message attack. This construction was later superseded by the construction of digital signatures from any one way trapdoor permutation. The existence of trapdoor permutations does not by itself imply claw free permutations exist; however, it has been shown that claw free permutations do exist if factoring is hard. The general notion of claw free permutation (not necessarily trapdoor) was further studied by Ivan Damgård in his PhD thesis The Application of Claw Free Functions in Cryptography (Aarhus University, 1988), where he showed how to construct
Collision Resistant Hash Functions from claw free permutations. The notion of claw freeness is closely related to that of collision resistance in hash functions. The distinction is that claw free permutations are pairs of functions in which it is hard to create a collision between them, while a collision resistant hash function is a single function in which it's hard to find a collision, i. e. a function H is collision resistant if it's hard to find a pair of distinct values x,y such that
H(x) = H(y). In the hash function literature, this is commonly termed a hash collision. A hash function where collisions are difficult to find is said to have collision resistance.
Битовая приверженность
При наличии пары пермутаций, свободных от «когтей» (claw-free), f0 и f1, создание схемы коммитов является простым. Чтобы закоммититься на бит b, отправитель выбирает случайное значение x и вычисляет fb(x). Поскольку f0 и f1 имеют одинаковую область определения (и область значений), бит b статистически скрыт от получателя. Чтобы раскрыть коммит, отправитель просто отправляет случайное значение x получателю. Отправитель связан со своим битом, поскольку раскрытие коммита к 1 − b эквивалентно обнаружению «когтя». Важно отметить, что, как и при построении криптографических хеш-функций, устойчивых к коллизиям, данная конструкция не требует наличия «черного хода» (trapdoor) в пермутациях, свободных от «когтей».