Математические аспекты разработки схем электронной подписи
В литературе встречаются схемы электронной подписи двух типов. Стойкость схем первого типа может быть доказана при некоторых стандартных криптографических предположениях. Однако, как правило, эти схемы непригодны для практического применения, так как требуют больших (хотя и полиномиальных от параметра безопасности) вычислений и объемов памяти. Схемы второго типа более пригодны для практического применения, но вопрос об их стойкости открыт. 
Основная теорема 
Мы будем в основном рассматривать однородную модель вычислений (т. е. когда противник является полиномиальной вероятностной машиной Тьюринга), хотя формулируемые результаты верны (с соответствующими изменениями в определении стойкости) в неоднородной модели. По-видимому, основным результатом теории схем электронной подписи является следующая 
Теорема 3.  Пусть  -- некоторая угроза, а -- некоторая атака из списков, приведенных выше. Тогда схемы электронной подписи, стойкие против угрозы на основе атаки , существуют тогда и только тогда, когда существуют односторонние функции. 
Таким образом, существование стойких схем не зависит от того, против какой угрозы и на основе какой атаки из вышеприведенных списков рассматривается стойкость. 
В одну сторону теорема 3 вытекает из следующих соображений. Если некоторая схема является стойкой против угрозы на основе атаки , где и  -- те же, что и в теореме 3, то она является стойкой против полного раскрытия на основе атаки с открытым ключом. Другими словами, не существует эффективного алгоритма вычисления секретного ключа по известному открытому. Но из этого следует существование односторонних функций (см., например, [Ro]). 
Для доказательства обратной импликации теоремы 3 (что оказалось нетривиальной задачей), очевидно, достаточно доказать, что из существования односторонних функций следует существование схем электронной подписи, стойких против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений. Такие схемы являются в некотором смысле наиболее стойкими, если принять вышеописанную классификацию угроз и атак. 
Схемы Лампорта и Наора -- Юнга 
Схема Лампорта  представляет собой основу для построения многих доказуемо стойких схем электронной подписи. Приведем ее описание. Пусть  -- некоторая общедоступная односторонняя функция,  -- множество элементов длины из области определения , где  -- параметр безопасности (например, ), а  -- длина подписываемых сообщений. Секретным ключом является набор из элементов , где (каждый такой элемент выбирается независимо от других), а открытым ключом -- набор , где для , . Подписью для сообщения , где , является , а произвольный набор из элементов принимается в качестве подписи для сообщения , если и только если для всех . Другими словами, как генерация, так и проверка подписей производится побитово. 
Таким образом, чтобы подделать подпись, противник должен инвертировать функцию , что является вычислительно трудной задачей. Однако при использовании схемы Лампорта раскрывается часть секретного ключа, поэтому без замены ключей ее можно использовать только один раз. Кроме того, длина подписываемого сообщения ограничена параметром . 
Поставим теперь вопрос: как превратить одноразовую схему Лампорта в многоразовую? Если просто выбирать каждый раз заново ключи и передавать открытый ключ вместе с подписью для исходного сообщения, то возникает опасность подмены ключей. Для предотвращения этой опасности Наор и Юнг  предложили использовать саму схему Лампорта. Но суммарное число битов в и превосходит , следовательно, непосредственно с помощью схемы Лампорта подписать сообщение нельзя. Поэтому в  подписывается не сам открытый ключ , а значение на нем некоторой случайно выбранной функции из семейства односторонних хэш-функций. В той же работе  доказано, что полученная в ней схема является стойкой против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений. 
Таким образом, если существуют семейства односторонних хэш-функций, то существуют и схемы электронной подписи, стойкие против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений. В свою очередь, как доказал Ромпель , для существования семейств односторонних хэш-функций достаточно существования (произвольных) односторонних функций. Из этого следует обратная импликация теоремы 3. Отметим, что в  существование семейств односторонних хэш-функций доказано в предположении существования односторонних перестановок.