14.1.4 Гипотеза о существовании односторонних функций

В теоретической криптографии рассматриваются два типа стойкости криптографических схем. Теоретико-информационная стойкость означает, что противник, атакующий схему, не получает достаточной информации для того, чтобы угрожать безопасности ее использования. Примерами могут служить одноразовые ключи Вернама, схемы разделения секрета и некоторые другие схемы. Если же задача противника в принципе разрешима, но является, предположительно, вычислительно трудной, то говорят о теоретико-сложностной стойкости. Все криптографические схемы с открытым ключом могут быть стойкими лишь в теоретико-сложностном смысле, поскольку, как отмечали еще Диффи и Хеллман [DH], задача противника никогда не выводит за пределы класса NP.

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

В работе Импальяццо и Луби [IL] предложен общий метод доказательства необходимости односторонних функций для существования стойких криптографических схем различных типов.

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

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