Односторонняя функция с потайным входом

Односторонняя функция с потайным входом (англ. trapdoor function) - это функция, которая легко вычисляется в одном направлении, но трудно вычисляется в обратном без специальной информации (секрета), называемой «лазейкой» или «потайным входом». Односторонние функции с потайным входом широко используются в криптографии.

Говоря математическим языком, если F - односторонняя функция с потайным входом, тогда существует секретная информация Y, такая, что при известных F(х) и Y легко вычислить x. Рассмотрим замок и его ключ. Можно изменить состояние замка с открытого на закрытое, не прибегая к использованию ключа, защелкнув дужку замка. Это простая задача. В данном примере ключом является «лазейкой».

Определение

Функция

$F:\{0,1\}^{l(n)}\times \{0,1\}^{n}{\xrightarrow[{}]{}}\{0,1\}^{m(n)}$

называется односторонней с потайным входом, если

1. Она является односторонней.
2. Существует эффективный алгоритм, который при заданных открытом ключе Y, сообщении M и значении функции вычисляет M‘ такое, что F(M) = F(M‘) для некоторого ключа Z.
3. Для данного сообщения M и функции F(M) трудно найти сообщение M‘≠M такое, что F(M) = F(M‘).

История

Понятие односторонней функции с потайным входом было введено в середине 1970-х годов после публикации Уитфилдом Диффи, Мартином Хеллманом и Ральфом Меркле статьи об асимметричных методах шифрования (шифрование с открытым ключом). Именно Диффи и Хеллман ввели данный термин. Было предложено несколько классов функций, но скоро стало понятно, что подходящие функции труднее найти, чем считалось изначально. Например, сначала предполагалось использовать функции, основанные на задаче суммы подмножества. Вскоре выяснилось, что этот способ неприемлим.

В 2005 году самыми подходящими кандидатами в односторонние функции с потайным входом являлись функции из классов RSA и Рабина . Эти функции используют возведение в степень по модулю составного числа, и обе они основаны на задаче факторизации целых чисел.

Развитие односторонних функций с потайным входом

Односторонние функции с потайным входом, допускающие потери

Данную функцию впервые ввели Chris Peikert и Brent Waters. Они основаны на идее повреждения значительной части информации.

Такие функции имеют два свойства:

1. Повторяют работу обычной односторонней функции с потайным входом, т.е. при наличии «лазейки» позволяет эффективно вычислить x по значению F(x).
2. Теряют часть информации о входе, тогда у выхода F(x) существует много прообразов.

Основная особенность в том, что эти два свойства становятся фактически неразличимыми. Зная только зашифрованное сообщение F(x), ни один криптоаналитик не может сказать, какая функция была использована – с потерями или без.

Односторонние функции с потайным входом, допускающие потери применяются во многих схемах шифрования. В их число входят: детерминированное шифрование с открытым ключом, защита от атак выборочного открытого текста и другие.

Односторонние функции с потайным входом «Все, кроме одного»

Для исследований атак, проводимых на основе подобранного шифротекста, были введены односторонние функции с потайным входом "Все, кроме одного".

Каждая функция имеет дополнительный аргумент, называемый ветвью. Все ветви являеются односторонними функциями с потайным входом с одной «лазейкой», за исключением одной - которая является ветвью с потерями. Данная ветвь определяется как параметр функции, причём его значение - скрыто (с точки зрения вычисления) описанием полученной функции.

Применение односторонних функций с потайным входом

RSA

Возьмем число $K=p*q$, где p и q принадлежат множеству простых чисел. Считается, что вычисление числа K является математически трудной задачей. Функция RSA — $F(x)=x^{e}mod(K)$, где е - взаимнопростое с $(p-1)(q-1)$. Числа p и q являются потайным входом, зная которые вычисленить обратную функцию $f^{-1}$ легко. На сегодняшний день лучшей атакой на RSA является попытка факторизовать число K.

Фунция Рабина

Рассмотрим функцию $F(x,n)=x^{2}mod(n)$, где $n=p*q$, а p и q принадлежат множеству простых чисел. Рабин показал, что вычислить функцию $f^{-1}$ легко тогда и только тогда, когда разложение на множители составного числа из двух простых является простой задачей.

Другие примеры

Известно, что функции, связанные с задачей дискретного логарифмирования, не являются односторонними функциями с потайным входом, потому что нет никакой информации о «лазейке», которая позволила бы эффективно вычислять дискретный логарифм. Однако, задача дискретного логарифмирования может использоваться в качестве основы «лазейки», например, вычислительная задача Диффи-Хеллмана (CDH) и его разновидности. Семантически безопасная версия схемы Эль-Гамаля опирается на задачу принятия решений Диффи-Хеллмана (DDH). Алгоритм цифровой подписи основан на CDH.

Односторонние функции с потайным входом имеют очень специфическое применение в криптографии и их не нужно путать с бэкдором (часто одно понятие подменяется другим, но это неправильно). Бэкдор - механизм, который намеренно добавляется к шифровальному алгоритму (например, алгоритм генерации ключевых пар, алгоритм цифровой подписи, и т.д.) или к операционным системам, позволяя одному или нескольким посторонним лицам обходить или подрывать безопасность системы.

См. также

• Односторонняя функция

Литература

• Xavier Boyen, Xiaofeng Chen. General Construction of Chameleon All-But-One Trapdoor Functions // Provable Security: 5th International Conference. — Springer, 2011. — P. 257—261. — ISBN 9783642243158.
• Giuseppe Longo. Section 4.2: Cryptographic functions // Secure digital communications. — 1983. — P. 29—30. — ISBN 0-387-81784-0.
• Chris Peikert, Brent Waters. Lossy Trapdoor Functions and Their Applications. — 2008.
• Julien Cathalo, Christophe Petit. One-time trapdoor one-way functions : [англ.]. — Springer, 2011. — ISBN 9783642181771.