4.6.2.2 Схемы Лампорта и Наора -- Юнга

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

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

Поставим теперь вопрос: как превратить одноразовую схему Лампорта в многоразовую? Если просто выбирать каждый раз заново ключи и передавать открытый ключ вместе с подписью для исходного сообщения, то возникает опасность подмены ключей. Для предотвращения этой опасности Наор и Юнг [NY] предложили использовать саму схему Лампорта. Но суммарное число битов в и превосходит , следовательно, непосредственно с помощью схемы Лампорта подписать сообщение нельзя. Поэтому в [NY] подписывается не сам открытый ключ , а значение на нем некоторой случайно выбранной функции из семейства односторонних хэш-функций. В той же работе [NY] доказано, что полученная в ней схема является стойкой против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений.

Таким образом, если существуют семейства односторонних хэш-функций, то существуют и схемы электронной подписи, стойкие против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений. В свою очередь, как доказал Ромпель [Ro], для существования семейств односторонних хэш-функций достаточно существования (произвольных) односторонних функций. Из этого следует обратная импликация теоремы 3. Отметим, что в [NY] существование семейств односторонних хэш-функций доказано в предположении существования односторонних перестановок.