14.1.5 Функции с секретом

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

Неформально функцию с секретом можно определить как одностороннюю, т. е., трудно инвертируемую, функцию, у которой, тем не менее, имеется некоторый секрет (trapdoor), знание которого позволяет выполнять операцию инвертирования эффективно. Известным примером функции с секретом (гипотетической) является функция RSA. Для ее инвертирования требуется алгоритм вычисления корней по составному модулю, что считается вычислительно трудной задачей. Однако, знание разложения модуля на простые множители позволяет решать эту задачу эффективно [RSA]. Противник, не знающий секрета, может попытаться найти его, решая задачу факторизации. Но последняя также считается вычислительно трудной.

Единственное известное нам формальное определение функции с секретом содержится в работе Беллара и Микали [BeMi]. В этом определении обозначает строку из двоичных единиц.

• для всякого на входе машина выдает пару -битовых строк ;

• для всякой такой пары и для любого
  

• для любого полиномиального алгоритма , любого полинома и всех достаточно больших
  
  где для . Вероятность берется по выбору пары алгоритмом , выбору и по случайным величинам алгоритма , если последний является вероятностной машиной Тьюринга.

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

Никаких результатов о необходимых и достаточных условиях существования функций с секретом на настоящий момент не известно. Специалисты склоняются к мнению, что предположение о существовании функций с секретом сильнее предположения о существовании односторонних функций. Имеются некоторые результаты (см. [IR]), которые можно рассматривать как косвенные свидетельства в поддержку этой точки зрения. Поэтому в теоретической криптографии гипотеза о существовании функций с секретом используется, наряду с гипотезой о существовании односторонних функций, для доказательства существования стойких криптографических схем различных типов. Примером здесь могут служить криптосистемы с открытым ключом.

Что касается конкретных примеров функций, которые предположительно являются функциями с секретом, то на данный момент функция RSA остается единственной известной "настоящей" функцией с секретом. Под термином "настоящая" мы понимаем следующее. В основе конструкции всякой функции с секретом лежит некоторая известная математическая задача, которая считается вычислительно трудной. Если противник найдет эффективный алгоритм решения этой задачи, то он сможет инвертировать функцию. Замечательное свойство RSA состоит в том, что задача поиска секрета -- это и есть в точности задача факторизации. Такой секрет мы называем настоящим. В задаче РЮКЗАК, по-видимому, нет присущего ей настоящего секрета. Поэтому, все попытки построить на основе этой задачи функцию с секретом состояли в выделении некоторой легко решаемой подзадачи и в "маскировке" ее под трудную. При этом некоторая информация о способе маскировки и становится секретом. Но для таких функций задача поиска секрета, вообще говоря, никак не связана с исходной задачей, в данном случае -- с задачей РЮКЗАК. Другими словами, если противник найдет эффективный алгоритм отыскания секрета, то это будет означать только то, что маскировка выбрана неудачно (или, что требуемая маскировка вообще не существует). По-видимому, именно отсутствие в задаче настоящего секрета и явилось основной причиной нестойкости многочисленных криптосистем с открытым ключом, построенных на основе задачи РЮКЗАК. Аналогичные соображения применимы и к другим попыткам построить функции с секретом методом маскировки.