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

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

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

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

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

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

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

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

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

RSA

Возьмем число , где и принадлежат множеству простых чисел. Считается, что для данного числа вычисление и является математически трудной задачей. Функция шифрования RSA — , где — взаимнопростое с . Числа и являются потайным входом, зная которые вычислить обратную функцию легко. На сегодняшний день лучшей атакой на RSA является факторизация числа ^[9][10].