4.6.2.1 Основная теорема

Мы будем в основном рассматривать однородную модель вычислений (т. е. когда противник является полиномиальной вероятностной машиной Тьюринга), хотя формулируемые результаты верны (с соответствующими изменениями в определении стойкости) в неоднородной модели. Подробнее о моделях вычислений говорится в главе 14.

По-видимому, основным результатом теории схем электронной подписи является следующая

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

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

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