Перестановка без когтей
В математики и информатики области криптографии группа из трех чисел ( x , y , z ) называется клешней двух перестановок f 0 и f 1, если
- ж 0 ( Икс ) знак равно ж 1 ( y ) знак равно z .
Пара перестановок f 0 и f 1 называется свободной от клешней, если не существует эффективного алгоритма вычисления клешни.
Терминология «без когтей» была введена Голдвассером , Микали и Ривестом в их статье 1984 года «Парадоксальное решение проблемы сигнатуры» (а позже и в более полной журнальной статье), где они показали, что существование пар без когтей Перестановки с лазейками подразумевают существование схем цифровой подписи, защищенных от атак с использованием адаптивного выбранного сообщения . [1] [2] Позже эта конструкция была заменена созданием цифровых подписей из любой односторонней перестановки с люком. [3] Существование перестановок с люками само по себе не означает, что существуют перестановки без когтей; [4] однако было показано, что перестановки без клешней действительно существуют, если факторизация затруднена. [5]
Общее понятие перестановки без клешней (не обязательно люка) было дополнительно изучено Иваном Дамгордом в его докторской диссертации «Применение функций без клешней в криптографии» (Орхусский университет, 1988), где он показал, как построить Устойчивые к коллизиям хеш-функции из перестановок без когтей. [5] Понятие отсутствия когтей тесно связано с понятием устойчивости к коллизиям в хеш-функциях. Разница в том, что перестановки без когтей представляют собой пары функций, в которых трудно создать коллизию между ними, тогда как устойчивая к коллизиям хеш-функция представляет собой одну функцию, в которой трудно найти коллизию, т. е. функция H является коллизией. устойчив, если трудно найти пару различных значений x , y таких, что
- ЧАС ( Икс ) знак равно ЧАС ( y ).
В литературе по хеш-функциям это обычно называется хеш-коллизией . Говорят, что хеш-функция, в которой трудно обнаружить коллизии, обладает устойчивостью к коллизиям .
Битовое обязательство
[ редактировать ]Имея пару перестановок f 0 и f 1 без клешней , легко создать схему обязательств . Чтобы зафиксировать бит b, отправитель выбирает случайное значение x и вычисляет f b ( x ). Поскольку и f 0 , и f 1 используют один и тот же домен (и диапазон), бит b статистически скрыт от получателя. Чтобы открыть обязательство, отправитель просто отправляет случайность x получателю. Отправитель привязан к своему биту, поскольку открытие обязательства по 1 − b в точности эквивалентно нахождению клешни. Обратите внимание, что, как и конструкция устойчивых к столкновению хэш-функций, эта конструкция не требует, чтобы функции без когтей имели люк.
Ссылки
[ редактировать ]- ^ Гольдвассер, Шафи ; Микали, Сильвио ; Ривест, Рональд Л. (1984). «Парадоксальное решение проблемы подписи». Материалы FOCS (PDF) . стр. 441–448.
- ^ Гольдвассер, Шафи ; Микали, Сильвио ; Ривест, Рональд Л. (апрель 1988 г.). «Схема цифровой подписи, защищенная от атак с использованием адаптивного выбранного сообщения». СИАМ Дж. Компьютер . 17 (2): 281–308. CiteSeerX 10.1.1.20.8353 . дои : 10.1137/0217017 .
- ^ Белларе, Михир ; Микали, Сильвио (1992). «Как подписать любую перестановку люка» . Журнал АКМ . 39 : 214–233. дои : 10.1145/147508.147537 . S2CID 628275 .
- ^ Додис, Евгений; Рейзин, Леонид (2002). «О силе перестановок без когтей»: 55–73. CiteSeerX 10.1.1.19.6331 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Перейти обратно: а б Дамгорд, Иван Бьерре (1988). «Хеш-функции без конфликтов и схемы подписи с открытым ключом». Достижения криптологии – EUROCRYPT' 87 . Конспекты лекций по информатике. Том. 304. Спрингер. стр. 203–216. дои : 10.1007/3-540-39118-5_19 .
Дальнейшее чтение
[ редактировать ]- Косиба, Такеши (1996). «Самоопределяемые функции без когтей» .