Случайные оракулы с (без) программируемостью

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:44, 2 декабря 2015.
Random Oracles with(out) Programmability
RandOr.png
Авторы Marc Fischlib[@: 1],

Anja Lehmann[@: 2],
Thomas Ristenpart[@: 3],
Thomas Shrimpton[@: 4],
Martijn Stam[@: 5],
Stefano Tessaro[@: 3]

Перевели Arseniy Kolobaev
Год перевода 2011-2015 г.
Скачать оригинал

Аннотация

В статье изучается свойство программируемости Модели Случайного Оракула (МСО), которое позволяет редукции безопасности динамически выбирать необходимый ряд выходных значений идеальной хэш функции. Это свойство представляет интерес по двум причинам :

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

Для оценки роли программируемости при обосновании безопасности системы в данной статье рассматриваются три типа программирующих редукий (непрограммирующие, ограниченно программирующие и полностью программирующие). Так же будет доказано , что не существует редукции для ЭЦП ХПОО в виде черного ящика в случае ограниченного программирования, и при этом наличие полного программирования позволяет доказать теоретическую безопасность ХПОО. Кроме того в работе доказывается, что механизм Shoup'a ( механизм инкапсуляции ключей на основе перестановки с лазейкой МИК-ПЛ) безопасен относительно атаки по выбранному шифртексту лишь в случае ограниченной программируемости, а в случае непрограммиремости не существует редукции в виде черного ящика.

В доказательствах использована безопасная техника разделения оракулов Hsiao-Reyzin'a.

Введение

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

Одним из таких свойств является программируемость. Не вдаваясь в подробности, можно сказать, что случайный оракул может быть наполнен динамически выбираемыми возвращаемыми значениями, тогда при условии, что значения выбираются правильным образом (сбалансировано на определенной области значений), любой метод выбора этих значений считается правильным. Техника программирования выходных значений СО в редукции безопасности имеет ключевое значение в бессчетном множестве правильных результатов [1][2][3]. Ни одна из известных функций стандартной модели не может предоставить возможность абсолютно случайной и адаптивной программируемости , которой обладает СО. Возникает вопрос : какой из данных результатов (если таковой вообще есть) мог бы быть получен без использования полной программируемости МСО?

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

  1. каждый может доказать ( используя новый вариант техники Hsiao-Reyzin разделения на 2 оракула [4]) невозможность предоставить ограниченно-программируемую редукцию безопасности в виде черного ящика для алгоритма цифровой подписи ХПОО [1]
  2. схема Shoup’а TDP-KEM [15] доказуемо безопасна от атак на основе выбранного шифр текста при условии частичной программируемости, но ни одна редукция безопасности в виде чёрного ящика не работает, если программируемость запрещена. Подытожить вышесказанное можно в виде схемы на рисунке 1.
Рис 1. Взаимодействие между различными моделями и пример результата. Публичный интерфейс показывает, что редукция В может видеть все запросы, поступающие от противника А, при этом «set $» показывает, что В может переопределять случайные значения для R, а R^p обозначает слабо программируемый СО.

«Пример : ххх » обозначает схему ХПОО или ОПАШ, для которой доказана безопасность при использовании модели показанной над ней, но при этом[5]- схема паддинга, часто используемая вместе с алгоритмом RSA. Алгоритм основан на сети Фейстеля, которая использует пару случайных оракулов G и H для преобразования открытого текста до начала асимметричного шифрования. В сочетании с некоторой однонаправленной перестановкой с лазейкой f это преобразование превращается в схему, для которой в модели случайного оракула можно доказать семантическую безопасность против атаки НР-АВШ. ОПАШ имеет две цели :

  • Внедрить элемент случайности , который может быть использован для преобразования детерминированной схемы шифрования (например традиционный RSA) в вероятностную схему.
  • Предотвращение частичной дешифровки текста на основании неспособности противника найти обратную (к однонаправленной подстановке с лазейкой) подстановку

Моделирование (не-)Программируемости в Редукции Безопасности. Nielsen [6] был первым, кто формально исследовал роль программируемости с точки зрения безопасности. Он показал, что не существует способа реализовать естественную криптографическую функциональность (независимое шифрование без взаимодействий) в модели подобной МСО, которая полностью запрещает программирование выходных значений СО. Его результаты, а также более ранние результаты, полученные Wee [7], в контексте нулевого разглагения, применяются в безопасности, основанной на симуляции, и в частности ограничивают возможность симулятора программировать СО в этом случае. К сожалению, их достижения недостаточны для обоснования большинства доказательств безопасности, основанных на МСО, которые используют программируемость в редукциях безопасности. В данной работе рассмотрено это направление в виде исследования редукций безопасности в моделях, содержащих СО, но имеющих ограниченную возможность программирования СО. Согласно подходам Nielsen’а [6], первой задачей является формализация в виде зависимости между работой редукции безопасности и внешнего СО (к которому злоумышленник также имеет доступ – т.е. редукция безопасности «видит» запросы, сделанные злоумышленником и ответы оракула) непрограммируемых редукций безопасности в виде черного ящика (ЧЯ) (т.е. редукция безопасности имеет доступ к противнику лишь через оракул). Далее будет рассмотрена более слабая модель, называемая случайно программируемой редукцией безопасности. Понятно, что внешний случайный оракул реализуется в виде индексированной сообщениями таблицы случайно выбранных точек последовательности, при этом до тех пор пока редукция безопасности не получает ряд точек, она может обрабатывать точки в порядке их расположения в таблице. Как будет показано далее, данное ограничение на программирование реализует промежуточную между полностью программируемой и непрограммируемой модель, охватывающую доказуемость важных схем. Полностью программируемая редукция безопасности позволяет произвольно выбирать значения выходной последовательности, как и в традиционных МСО доказательствах.

Модель слабо-программируемого случайного оракула (МСлПСО). Ограничением предложенной выше модели редукции безопасности является сведение редукции безопасности к модели ЧЯ. Как сказано в работе Nielson’a [6], предоставление моделей, в которых ограничение на программируемость в редукциях безопасности, не являющихся ЧЯ, спорно, требуют исследования. Все дело в том, что в моделях, отличных от ЧЯ, редукция безопасности напрямую имитирует все запросы злоумышленника к оракулу, и поэтому не существует способа заставить редукцию безопасности работать как внешний СО. В статье разрешена данная проблема для случайно программируемых редукций безопасности путём предоставления нового варианта МСО.

Слабо–программируемый случайный оракул (СлПСО) работает как идеализированная модель хэш функции. Пусть ρ – случайная функция, при этом её ряд значений совпадает со значениями хэш функции. Для каждого входного значения x СлПСО выбирает выходное значение ρ(r) из случайной последовательности r. Кроме того, СлПСО позволяет только злоумышленнику получать значения из строки r, которые используются СлПСО для генерации выходных значений. В МСлПСО все стороны имеют доступ к СлПСО, который использует регулярную однонаправленную функцию ρ. Требования, накладываемые на функцию ρ, обеспечивают ограничение программируемости МСлПСО. Например, попытка запрограммировать выход оракула на заданное значение у требует вычисления ρ-1(у) и опровержения однонаправленности; регулярность предполагает, что выход функции ρ будет сбалансирован. Это требование часто накладывается на СО. МСлПСО имеет мало общего со случайно программируемой редукцией безопасности. Тем не менее, в статье доказывается, что обе модели ограниченного программирования сильно взаимосвязаны. А имено, согласно Утверждению 3 (см.далее) любая редукция безопасности в виде ЧЯ в МСлПСО включает в себя случайно программируемую редукцию безопасности, в то время как согласно Утверждению 4 любая случайнопрограммируемая редукция безопасности содержит редукцию безопасности в МСлПСО. Помимо удобства доказательства результатов (в большинстве случаев работать с МСлПСО легче), эквивалентность моделей является подтверждением того, что данная формулировка ограниченной программируемости удачна. То же можно сказать и о результатах описанных ниже.

Использование в практических схемах. Полученные новые инструменты можно использовать для пересмотра доказательств безопасности многих важных схем. Эти схемы представляют интерес для изучения. Предполагается, что каждый может использовать данные техники, чтобы без труда проанализировать необходимость программируемости во многих дальнейших схемах. Первый пример - ЭЦП на основе алгоритма ХПОО. Единственные известные доказательства безопасности [8] используют редукции безопасности, вводящие ряд точек, лежащих в основе секретных перестановок, в одно или несколько выходных значений хэш функции. Возможно ли существование такой «умной» редукции безопасности, которая не зависела бы от программирования? В статье даётся формальное доказательство того, что это невозможно: Теорема 4 утверждает что не существует редукции безопасности, отличной от модели ЧЯ, способной доказать безопасность ХПОО в МСлПСО даже при маленькой стойкости. Может показаться, что программируемость играет значимую роль в существующих редукциях безопасности. Доказательство невозможности предоставить редукцию безопасности технически включено в данной статье. Предыдущие отрицательные результаты по сути использовали асимптотические методы для достижения разделения черных ящиков. Вместо этого, в доказательстве теоремы 4 используется другое приближение, которое не является асимптотическим по своей природе. Этот результат является дополнением к существующим отрицательным результатам для ХПОО, например [3].

Ещё один пример это МИК-ПЛ Shoup’a [9]. Доказательства безопасности SHoup’a (НР-АВШ) не используют внедрение сложной задачи в выходе СО, вместо этого используется программирование для обеспечения логической связи между имитацией декапсуляции оракула и симуляцией СО. В статье показан следующий неочевидный результат: МИК-ПЛ Shoup’a безопасна в МСлПСО (по Теореме 2), но при этом не существуют непрограммирующие редукции безопасности в виде ЧЯ для доказательства АВШ-безопасности (Теорема 3). Полученный отрицательный результат даже более сложен, чем в случае с ХПОО, и имеет несколько интересных технических барьеров (например, редукции безопасности могут перематывать состояния противников, что явно разрешено в непрограммирующей модели редукции безопасности).

Так же рассматривается ОПАШ [2].

Отметим, что доказательство безопасности в условии ограниченного программирования или отсутствия программирования является эвристическим. Это показывает, что доказательство в модели СлПСО или непрограммирующей редукции предоставляет более общее доказательство, чем в модели СО. Это является слабым местом МСО, поэтому программируемость является важным объектом рассмотрения из-за её очевидной искусственности. Отметим, что можно запустить непрограммирующую СО редукцию безопасности, когда используется конкретная хэш функция (например SHA-256) для реализации СО. Но при этом нельзя запустить полностью или случайно программирующие редукции безопасности.

Возможности для дальнейших исследований. Hofheinz и Kiltz[10]предложили некоторые идеи для изучения возможности программирования с совершенно другой точки зрения. Обобщая приёмы, предложенные Waters’ом[11], они построили хэш функцию стандартной модели, которая обладает ограниченной программируемостью. К сожалению, их хэш функции не достаточно программируемы, чтобы принимать их идеи для доказательства безопасности в моделях СО, как например ХПОО или схема Fiat-Shamir’a. Однако, их работы показывают, что лучшее понимание программируемости может увеличить применяемость широко распространенных решений в стандартной модели.

Модели редукции безопасности

В данном разделе формализуется на абстрактном уровне общая концепция редукции безопасности в виде черного ящика в модели случайного оракула. Представляются два варианта редукции безопасности в виде ЧЯ, в которых возможность редукции безопасности программировать СО ограничена.

Вводная часть

Введем основные понятия и алгоритмы работы оракулов

Доступ к злоумышленникам посредством оракула: Все алгоритмы (например, модель злоумышленника или редукции безопасности), а так же некоторые примитивы (например, случайный оракул) представлены как взаимодействующие машины Тьюринга (ВМТ). В частности, эти машины могут быть вероятностными и могут сохранять своё состояние. Каждая машина может иметь несколько связующих лент - интерфейсов, которые соединяют разные машины друг с другом. Обозначим ВМТ с интерфейсом, который ожидает доступ через оракул (т.е. черный ящик) к некоторой другой ВМТ как .Редукция безопасности В с доступом к злоумышленнику посредством оракула (обозначим как) может выполнять следующие действия:

  • В любое время В может запустить копию алгоритма А^((•)) по (заданным) случайности и входу, где берется тот же случайный вектор, который использовался ранее для получения выхода (или запроса оракула).
  • Когда одна из таких копий запущена, В получает каждое значение выхода А, и должен предоставить соответствующий ответ и некоторое значение случайного вектора, нужные, чтобы А смог выдать следующее значение.
  • В любой момент времени В может прекратить выполнение текущей копии А .

Отметим, что модель является достаточно общей, поэтому В может, например, перемотать выходные значения состояния А до произвольного места, запустив новую копию А с использованным до этого вектором случайных значений. Так же стоит отметить, что, если В получает доступ через оракул к (отличному от ) , то В не должен отвечать на запросы , адресованные к О. Запросы направляются напрямую к О . Ответы так же напрямую идут от О к А. Обозначим как ситуацию, когда нужно явно обозначить, что запросы к первому оракулу контролируются В, а ко второму – нет. Иногда для простоты оракулы, контролируемые В, будут пропущены: дело в том , что любой оракул, к которому А в явном виде не имеет доступа, считается контролируемым В. Наконец, обозначает следующее: когда А делает запрос х к О, то х сначала направляется к В, который может произвести некоторые вычисления, вызвать другие оракулы, и лишь после этого направить результат О(х) к А. Ответ от О идет напрямую (но при этом он видим для В), и В не имеет возможности повлиять на него. Данная конструкция будет полезна во многих случаях.

Свойства безопасности. Очень удобно рассматривать общие свойства безопасности П для криптографических примитивов в контексте «игры», в которой участвует «кандидат» f (называемый П-кандидат) и противник А (называемый П-противник). В частности, для каждой тройки f, А и П ставится в соответствие значение функции преобладания . Считается, что f является П-безопасной, если мало для всех эффективных противников А. Можно предположить, что функция преобладания удовлетворяет условию линейности: если оракул О работает как с вероятностью р или как ' с вероятностью (1-р) , = р⋅ + (1- р) ⋅ для каждого примитива f и каждого противника А. Несмотря на то, что существуют функции преобладания, не отвечающие данному свойству (например, различающее преобладание с абсолютными значениями), можно привести типичные примеры функций, удовлетворяющих ему (например, разделение с абсолютными значениями).

Редукция безопасности в виде ЧЯ в МСО

Когда речь идёт о редукциях безопасности в виде ЧЯ, имеются ввиду редукции безопасности в виде абсолютных черных ящиков, таких как определил Reingold [12]. Такие редукции безопасности имеют первостепенное значение в криптографии, особенно в схемах, построенных на случайных оракулах, основной целью которых является практическое применение. В Определении 1, представленном ниже, формализовано понятие редукции безопасности в виде абсолютно черного ящика (АЧЯ) в МСО. Также ниже представлены определения двух вариантов СО: с ограниченным программированием и без программирования.

Полностью программирующая редукция безопасности (ППРБ) . В первом приближении стандартную концепцию редукции безопасности можно формализовать в виде ЧЯ в МСО. Так как они поддерживают стандартную технику программирования МСО без каких либо ограничений, то будем их называть полностью программирующие редукции безопасности.

Непрограммирующая редукция безопасности (НПРБ)В первой попытке дать определение НПСЖ необходимо отразить, что редукция безопасности совершенно не имеет контроля над ответами случайного оракула. А именно, на запросы отвечает случайный оракул, который выбирается один раз независимо от редукции и её входов и не меняется при каждом запуске противника А, инициированном В. Пока редукция безопасности В может запоминать все запросы, принимаемые СО от А, для В не существует возможности влиять на эти запросы. Данный подход моделирует ситуацию, при которой редукция безопасности может быть запущена при помощи внешнего СО.

Случайно программирующая редукция безопасности (СПРБ) В данном случае редукция безопасности В может программировать СО случайным образом, а не заданными значениями, и, следовательно, такой вариант является промежуточным между полностью программируемой редукцией безопасности и непрограммируемой. Далее введём понятие случайно программируемый случайный оракул (СПСО), формализующее идеализированный объект, обладающий тремя интерфейсами: (отметим, что обыкновенный СО имеет единственный интерфейс взаимодействия). Если к СПСО посылать запрос через вычисляющий интерфейс , то он будет вести себя как обыкновенный СО, отображающий область определения в область значений ОО → ОЗ. Случайный интерфейс <применяет случайное отображение → ОЗ. Наконец, программирующий интерфейс принимает ОО и У в качестве входных значений и выставляет (Х) таким же как (У). Так как запросы А к вычисляющему интерфейсу являются публичными, то редукция В может по запросу X, поступившему от А, вызвать необходимое количество запусков R rand, следующих за подходящим вызовом (X,У), для того, чтобы ответы на запросы А удовлетворяли конкретным свойствам ещё до того, как они дойдут до А. Данный подход предполагает минимум программируемости для случая, при котором постоянное число выходных бит может приобрести некоторую зависимость от входных значений. Следует отметить, что данные интерфейсы позволяют перепрограммировать СО. Это свойство позволяет перематывать состояние А и запускать его на другом, частично последовательном СО, в котором редукции уже не нужно выбирать текущие значения. Заметим, что непрограммирующие редукции способны предотвратить подобное ветвление. Пусть S= [f] - это криптографическая схема, основанная на примитиве f и случайном оракуле R: ОО → ОЗ. Пусть и - это свойства безопасности, которым могут удовлетворять S и f соответственно.

TemplateDifinitionIcon.svg Определение «Определение - Определение 1»
Пусть Х ∈ { 'полностью программирующая, непрограммирующая, случайно программирующая} .Пусть(,, t,,)XМСО редукция безопасности для S в виде абсолютно чёрного ящика является оракулом со свойством, что для всех П-противников

и все -кандидатов f, если

для случайного оракула R : ОО → ОЗ и > 0 , следует где q обозначает полное количество запросов , поступающих от А, а l соответствует полной длине этих запросов. Более того, В работает в течение времени t, делает запросов к оракулу и запускает экземпляров , где все три числа являются функциями от ε, q и l. Кроме того, если : Х = полностью программирующая , то O_1=f , O_2=(⋅) , и = Х =непрограммирующая,то O_1=(f,R),= , и = ( , ) Х = случайно программирующая , то =(f, , ,) , = , и = ( , , , ), где R^'= , , ) является СПСО.

В данном разделе применяется новаторский подход для достижения деления черного ящика в конкретных условиях. Подход применим во всех случаях использования редукции, и проиллюстрирован для ППРБ редукции. Для того, чтобы опровергнуть существование редукции в виде абсолютного черного ящика в рамках определённого класса редукций, для каждой рассматриваемой редукции В необходимо доказать существование П' – кандидата f и противника А, таких, что значение функции превосходства будет большим, но мало . Достичь этого можно, показав существование случайного П' – кандидата F и противника АР со скрытым от других участников случайным рядом Р (т.е. не контролируемым редукцией В), для которых верно, что значение велико для всех значений случайного ряда р и для всех (фиксированных) примитивов f, полученных фиксированием случайного ряда принадлежащего F, но при этом мало для всех рассматриваемых редукций В. Благодаря свойству линейности функции преобладания, имеем =:

TemplateTheoremIcon.svg Теорема Теорема 1
Где ожидаемое значение берётся в зависимости от выбора случайного значения р и примитива f , реализуемого с помощью F (с соответствующими распределениями вероятностей, которые в общем случае могут даже коррелировать). Поэтому для всех рассматриваемых редукций В должны существовать некоторый специальный примитив f и противник
Доказательство
без скрытого случайного ряда, такие, что math>B^{(F,A_P^{F,.})</math> ≤ тоже будет мало[13]. Следовательно, подобное утверждение (для случайных примитивов) также предполагает отсутствие редукции, работающей одинаково со всеми примитивами, в частности нет необходимости применять широко распространенное ассимптотическое и универсальное упорядочивание, основанное на лемме Borel-Cantelli. Такой подход является новаторством данной работы.

Слабо-программируемые МСО

Идеальный (случайный) примитив слабо-программируемого случайного оракула относительно функции ρ : СП →ОЗ. По умолчанию T[X ]= ⊥ для всех Х. В предыдущем разделе программируемость рассматривалась путём изучения ограниченного набора редукций. С точки зрения противника, управляемого редукцией, ничего не изменилось. В данном разделе рассматривается альтернативный подход, основанный скорее на модификации случайного оракула, чем на ограничении редукции. Положим СО как функцию отображения из области определения ОО в область значений ОЗ, где ОЗ является ограниченной и не пустой. С того момента как идеальные примитивы были описаны при помощи стабильной вероятностной машины Тьюринга, стало возможным представить использование случайного оракула при помощи так называемого сбора образцов: как только появляется новый запрос Х∈ ОО, СО возвращает случайное значение z ⟵$ ОЗ и запоминает пару (X, z) для использования в будущем. Теперь необходимо ограничить возможность выбора значения z. А именно, необходимо параметризировать случайный оракул функцией ρ: случайная последовательность СП→ОЗ для ограниченной не пустой случайной последовательности. Каждый раз, когда случайный оракул получает новый запрос Х, он случайным образом выбирает r ⟵$ СП и возвращает z = ρ(r) и записывает Х вместе с r. Теперь, учитывая тот факт, что идеальный примитив может иметь несколько интерфейсов, можно определить два новых интерфейса: честный интерфейс, используемый честными сторонами и протоколами и соперничающий. Последний позволяет противнику подтвердить, что случайный оракул работает должным образом. Формально можно представить следующее определение слабо-программируемого (ρ-ограниченного) случайного оракула. '

TemplateDifinitionIcon.svg Определение «Определение 2 - Идеальный примитив »
Для функции ρ: СП → ОЗ идеальный примитив (, ), описанный на рисунке 2, называется ρ-СлПСО (или просто СлПСО , если ρ неявно подразумевается) .

Отметим, что честный интерфейс данного объекта возвращает ряд значений z, ассоциированных со значением запроса, являющегося входным значением. Соперничающий интерфейс возвращает ряд значений z и случайное значение r , по которому вычисляется z. До сих пор на функцию ρ не накладывалось никаких ограничений. Например, если ρ является тождественной функцией (и соответственно ОЗ = СП) , то полученный идеальный примитив эквивалентен обыкновенному случайному оракулу. С другой стороны, если ρ является константой, то R^ρ не сможет моделировать идеальную криптографическую хэш функцию. Поэтому необходимо определить, какими свойствами должна обладать хорошая ρ функция.

TemplateDifinitionIcon.svg Определение «Определение 3 »
Хорошая ρ . Функция ρ : СП → ОЗ называется хорошей для ОЗ только в том случае, если выполнены следующие 3 условия: (1) СП ограничена, (2) ОЗ делит СП и (3) ρ является регулярной функцией, т.е. для всех у ∈ ОЗ верно

r∈СП:ρ(r)=y|= Правильно подобранная хорошая ρ при вычислении значения в равномерно выбираемых точках ОО даёт равномерные результаты (равномерное распределение ОО функции ρ приводит к равномерному распределению области значений, если ρ хорошая). Иными словами,случайный оракул R:ОО→ ОЗ и СлПСО (с одинаковыми ОО и ОЗ) неразличимы с информационно-теоретической точки зрения лишь когда ρ является хорошей для ОЗ. Легко видеть, что различные функции ρ ограничивают возможность редукции программировать СО. Для уже рассмотренных случаев ключевым свойством функции ρ, которое делает доказательство безопасности через редукцию несостоятельным, является однонаправленность ρ, описанная в неассимптотической форме. Для любой функции ρ и «однонаправленного противника» (ОНФ-противника) А можно определить функцию «однонаправленного преобладания» (ОНФ-преобладания) как: Pr [:r←s СП ; ←s A ] где ОНФ-противник А определяется как вероятностный алгоритм, который в качестве входного значения принимает точку у∈ ОЗ , а на выходе получает точку х∈ СП. Однонаправленность функции ρ обеспечивает непрограммируемость в следующем смысле: рассмотрим, например, редукцию безопасности, типичную для ХПОО. Данная редукция принимает случайный образ у в соответствии с некоторой секретной перестановкой (лазейкой), и в некоторых точках вставляет это значение в качестве значения хэша в режиме черного ящика, так как это делает якобы успешный противник. Но, с того момента как противник получает доступ к интерфейсу, редукция должна предоставить прообраз у относительно функции ρ, нарушая тем самым свойство однонаправленности ρ.

Редукция в модели СлПСО .Можно напрямую определить модель СлПСО (МСлПСО) по аналогии с МСО (все «честные» участники имеют доступ к, все «соперничающие» - к ), при этом определение редукции в виде ЧЯ естественным образом дополняет эту модель. В частности, далее будет рассмотрено строгое определение редукции, которое допускает наличие любой хорошей функции ρ, не рассматривая, насколько эффективно она вычисляется. Пусть(П → , δ, t , , , ) СлПМСО редукция безопасности для S в виде абсолютно чёрного ящика является оракулом со свойством, что для всех П-противников оракулом А( ⋅ ) , всех хороших функций ρ для ОЗ и всех -кандидатов f, если > ε для функции ρ - СлСПО = (,,) с определённой областью значений ОЗ и ε> 0 , то> 1 (ε, q, l)

где q обозначает полное количество запросов, поступающих от А, а l соответствует полной длине этих запросов. Более того, В работает в течение времени t, делает и запросов к заданным ρ и F соответственно и запускает экземпляров , где все три числа являются функциями от ε, q и l. }} Как только редукция посчитает все хорошие функции ρ, она должна работать с однонаправленными ρ. В общем случае она должна работать с любой функцией' ρ , выбранной случайно из всего набора функций СП →ОЗ. Таким образом, редукции должны избегать использования программирования в виде ХПОО: редукция не может вставлять необходимый ряд значений в один из ответов СлПСО. Однако, как будет показано в следующем разделе, можно извлечь множество преимуществ из ещё более ограниченной техники программирования в модели СлПСО. Хотя все редукции в МСлПСО представлены в виде модели абсолютно черного ящика, следует подчеркнуть, что модель СлПСО допускает наличие редукций в виде, отличном от черного ящика.

Взаимодействия между редукциями разных типов

Определив все параметры редукций, можно определить правила взаимодействия между ними. Вначале сделаем очевидное утверждение: редукция в виде непрограммирующего черного ящика содержит в себе случайно программирующую, которая в свою очередь содержит в себе полностью программирующую. В данной статье строгое доказательство этого факта не приводится. Пусть S = является схемой, основанной на криптографическом примитиве f и случайном оракуле R : ОО → ОЗ. Пусть П и являются свойствами безопасности , которым с некоторой вероятностью удовлетворяют S и f соответственно.


Утверждение 1 (НПРБ ⇒ СПРБ ) . Если существует непрограммирующая (П → , , t , , , ) МСО редукция безопасности для S в виде абсолютно черного ящика, то существует случайно программирующая (П → , , t , , ,0,0, ) МСО редукция безопасности для S в виде абсолютно черного ящика.


Утверждение 2 (СПРБ⇒ ППРБ). Если существует случайно программирующая (П → , , t , , ,1,1, ) МСО редукция безопасности для S в виде абсолютно черного ящика, то существует полностью программирующая ( , , t , , ,qA ) МСО редукция безопасности для S в виде абсолютно черного ящика, где = t + O( ) для (=q⋅( + (+ + .


Далее при помощи редукции в виде черного ящика будет показано, что система является безопасной в модели СлПСО лишь тогда, когда существует случайно программирующая редукция безопасности. Следовательно, ограничения случайного оракула моделью СлПСО и ограничения способности редукции безопасности программировать обыкновенный случайный оракул являются эквивалентными при использовании модели черного ящика. Первый результат в частности использует тот факт, что редукция в виде абсолютного черного ящика в модели СлПСО должна так же работать и для случайно выбранной регулярной функции ρ.

Утверждение 3 (редукция МСлПСО ⇒ СПРБ ). Если (П → , , t , , , ) МСлПСО редукция безопасности для S в виде абсолютного черного ящика, то существует случайно программирующая ( П → , , , , q⋅ , q⋅ , + q⋅ , ) МСО редукция безопасности для S в виде абсолютного черного ящика , где = , = t + O(q⋅l) .

Утверждение 4 (СПРБ ⇒ редукции МСлПСО ) . [14]Если существует случайно программирующая (П → ' , δ, t , , , ,, ) редукция безопасности для S в виде абсолютного черного ящика, то существует (П→ , , , , , ) МСлПСО редукция безопасности для S в виде абсолютного черного ящика, где = t + O(q⋅) ⋅log( q⋅))⋅l), ) = q⋅) + ) + ) + ) .


СлПСО не эквивалентны СО, но МСлПСО и МСО эквивалентны Ниже будет приведено подтверждение выводу о том, что СлПСО является более слабым требованием, чем полноценный СО. Тем не менее, экзистенциально СлПСО и СО являются эквивалентными, т.е. можно эффективно получить СО из СлПСО. Для сопоставления СО и СлПСО воспользуемся структурой «безразличности» Maurer’a , Rener’a и Holenstein’a , чтобы исследовать близкие к случайным оракулам примитивы. Далее при помощи функции преобладания обозначим любой отличительный признак (признак различия) D, который позволяет отличить конструкцию С с компонентом Н от идеального примитива «R» (с переходной формой в виде модели S). При помощи верхних индексов «СО» и «СлПСО» в функции обозначается тот факт, что идеальный примитив R является СО или СлПСО. Сначала необходимо показать, что СлПСО не является СО, т.е. он легко отличим от СО. Это необходимо, чтобы показать, что в общем случае слабо программируемые случайные оракулы отделены от случайных оракулов. Рассмотрим равенство для случайного оракула Н : ОО→ОЗ нерегулярной однонаправленной функции ρ: СП →ОЗ. В таком случае, любая модель S должна инвертировать ρ для осмысленного моделирования.

Утверждение 5 (СлПСО ⇏ СО). Для любой функции ρ, хорошей для ОЗ, для равенства =p(H(x) ) существует модельСлПСО, такая что = 0 для любого признака различия D, но при этом существует признак различия, такой что для любой модели S = ≥ 1- Несмотря на столь общее разделение, можно построить полностью программируемый случайный оракул из СлПСО, выдавая по одному биту выходов СО в каждый момент времени. Например для x∈{0,1}* обозначим i-й бит x через x|_i. Для функции Н: {0,1}*→{0,1}^l для некоторого l > 1 определим конструкцию : {0,1}*→,такую что = , где символ || обозначает конкатенацию строк, а ⟨i⟩ (без индому представлению числа i. Отметим, что конструкция вызывает Н все m раз чтобы получить выходное значение длины m. Так же можно улучшить эффективность, подавая на выход больше бит в каждой итерации ценой сжатия в редукции. Причем, благодаря отсутствию индекса у ⟨⋅⟩, всегда можно понять, что данная строка имеет вид x ||⟨i⟩ для некоторых натуральных i.

=

Где ожидаемое значение берётся в зависимости от выбора случайного значения р и примитива f , реализуемого с помощью F (с соответствующими распределениями вероятностей, которые в общем случае могут даже коррелировать). Поэтому для всех рассматриваемых редукций В должны существовать некоторый специальный примитив f и противник[15] |

Инкапсуляция Ключа на Основе Перестановки с Лазейкой

МИК-ПЛ безопасность в МСлПСО

того момента как идеальные примитивы были описаны при помощи стабильной вероятностной машины Тьюринга, стало возможным представить использование случайного оракула при помощи так называемого сбора образцов: как только появляется новый запрос Х∈ ОО, СО возвращает случайное значение z ⟵$ ОЗ и запоминает пару (X, z) для использования в будущем. Теперь необходимо ограничить возможность выбора значения z. А именно, необходимо параметризировать случайный оракул функцией ρ: случайная последовательность СП→ОЗ для ограниченной не пустой случайной последовательности. Каждый раз, когда случайный оракул получает новый запрос Х, он случайным образом выбирает r ⟵$ СП и возвращает z = ρ(r) и записывает Х вместе с r. Теперь, учитывая тот факт, что идеальный примитив может иметь несколько интерфейсов, можно определить два новых интерфейса: честный интерфейс, используемый честными сторонами и протоколами и соперничающий. Последний позволяет противнику подтвердить, что случайный оракул работает должным образом. Формально можно представить следующее определение слабо-программируемого (ρ-ограниченного) случайного оракула Механизм инкапсуляции ключа (МИК) состоит из трёх алгоритмов МИК = (Ключ, Инкап, Декап), которые выполняются последовательно. Вероятностный алгоритм генерации ключей возвращает ключевую пару (pk, sk) ← $ Ключ. Алгоритм инкапсуляции ключей Инкап является вероятностным, в качестве входного значения алгоритм принимает ключ рk и возвращает пару ключ-шифртекст (К,С) , где К принадлежит некоторому непустому набору K. Алгоритм декапсуляции ключей Декап в качестве входного значения принимает пару (sk, C) и однозначно возвращает ключ К ∈ K , или специальный символ ⊥ , означающий, что было принято некорректное значение пары (sk, C). Пусть А является МИК-противником, K является не пустым набором и пусть множество МИК = (Ключ, Инкап, Декап) является МИК. Безопасность МИК хэш функции R в модели СлПСО с соответствующей функцией ρ по отношению к противнику А определяются при помощи следующего эксперимента :

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

Описание противника Противник А должен быть описан в терминах некоторой мик-авш игры, так чтобы было ясно будет ли он использован редукцией В для взлома однонаправленности перестановки с лазейкой TP , и когда А будет запущен. В самом грубом приближении А , получая открытый ключ pk , может выбрать случайное значение r ← $ OO и вычислить С← F ( pk, r) ; Далее противник подает запрос к декапсулирующему оракулу , чтобы получить шифртекст С и значение К. Наконец он делает запрос r к случайному оракулу R и проверяет равенство R(r) = K. Если оно верно, то противник продолжает взлом схемы, например при помощи инвертирования на принятом шифртексте, чтобы затем угадать бит b путём дополнительного запроса к случайному оракулу. В противном случае А просто выдает ответ наугад. Если B оказывается эффективной, то она не может вычислить r, выдавая только С, таким образом она должна выдатьи ( на запрос А к декапсулирующему оракулу ) некоторый независимый ключ К’ , такой, чтобы равенство R(r) = K оказалось ложным. Такие рассуждения имеют два слабых места. Во-первых , В определяет случайность А, поэтому B выбирает r. Во-вторых, даже позволив А сделать запрос к декапсулирующему оракулу для получения шифртекста С с прообразом r (который неизвестен B), редукция B всё равно может запустить А ( при помощи случайного ответа на запрос декапсулирующего оракула) в том состоянии, в котором равенство R(r) = K не выполняется, и , следовательно, B может получить r (необходимое для). B может перемотать А таким образом, чтобы А получил шифртекст С, для которого В уже знает правильный ответ R (r). А значит В может обращать соответствующую перестановку с лазейкой TP, предоставляя выход y в качестве шифртекста на запрос А об инкапсуляции. Обе проблемы описаны при помощи случайного оракула О: и противника А , который при получении открытого ключа pk делает ряд запросов на декапсуляцию,,… , <mathC_l</math> (где l = q-1) , где вычисляется при помощи применения случайного оракула к pk, , ,… , и к ответам на предыдущие запросы. Затем он проверяет корректность ответов , , …в обратном порядке ( он проверяет равенствои прекращает проверку как только встретит первое невыполняющееся равенство (это ключевой момент для всего анализа). Наконец, противник выполняет действия, соответствующие случаям, когда все равенства верные или нет. Основная идея состоит в том, что перематывание не может помочь , если главной задачей редукции В является запуск экземпляров противника А, так как для достижения выполнения всех равенств потребуется экспоненциально много ( для l ) запусков А. Это можно доказать, сводя игру к чисто комбинаторной задаче. Такое приближение близко к идеям Canetti [16]для доказательства нижней границы раундовой сложности однонаправленной функции в виде черного ящика , используемой для доказательств при нулевом разглашении. Идеальный (случайный) примитив слабо-программируемого случайного оракула относительно функции ρ : СП →ОЗ. По умолчанию T[X ]= ⊥ для всех Х. В предыдущем разделе программируемость рассматривалась путём изучения ограниченного набора редукций. С точки зрения противника, управляемого редукцией, ничего не изменилось. В данном разделе рассматривается альтернативный подход, основанный скорее на модификации случайного оракула, чем на ограничении редукции. Положим СО как функцию отображения из области определения ОО в область значений ОЗ, где ОЗ является ограниченной и не пустой. С того момента как идеальные примитивы были описаны при помощи стабильной вероятностной машины Тьюринга, стало возможным представить использование случайного оракула при помощи так называемого сбора образцов: как только появляется новый запрос Х∈ ОО, СО возвращает случайное значение z ⟵$ ОЗ и запоминает пару (X, z) для использования в будущем. Теперь необходимо ограничить возможность выбора значения z. А именно, необходимо параметризировать случайный оракул функцией ρ: случайная последовательность СП→ОЗ для ограниченной не пустой случайной последовательности. Каждый раз, когда случайный оракул получает новый запрос Х, он случайным образом выбирает r ⟵$ СП и возвращает z = ρ(r) и записывает Х вместе с r. Теперь, учитывая тот факт, что идеальный примитив может иметь несколько интерфейсов, можно определить два новых интерфейса: честный интерфейс, используемый честными сторонами и протоколами и соперничающий. Последний позволяет противнику подтвердить, что случайный оракул работает должным образом. Формально можно представить следующее определение слабо-программируемого (ρ-ограниченного) случайного оракула. '

ХПОО не является доказуемо безопасной в модели СлПСО

В данном разделе рассмотрены традиционные схемы ЭЦП при помощи хэш функции с полной областью определения (ХПОО) и доказано, что они не являются доказуемо безопасными при использовании случайно программирующих редукций. Следовательно, требуется более сильная программируемость. Доказательство проводится в модели СлСПО. Хэш функция с полной областью определения Кратко схему ЭЦП при помощи ХПОО можно представить следующим образом. Схем = (Kg, Sig , Ver) основана на перестановке с лазейкой TP = (G , F, ← ). Чтобы подписать сообщение MMsg, необходимо вычислить (sk,H(M)), где Н: Msg → Sig хэш функция. Чтобы проверить подпись, нужно посмотреть, выполняется ли равенство ) = H(M), где (pk, sk) – ключи, вырабатываемые алгоритмом Kg. Ниже рассмотрена очень слабая стойкость ХПОО (называемая wsig) к фальсификации, так как противник может подделать подпись для некоторого случайного сообщения при помощи атак на ключе. Даже при использовании редукций от wsig до однонаправленной перестановки с лазейкой (owp) в МСлПСО нельзя доказать безопасность ХПОО. Теорема 4 (ХПОО не может быть доказуемо безопасной в МСлПСО). Пусть '(Kg,Sign,Ver)' является схемой ХПОО с пространством сообщений Msg , пространством подписей Sign и основанная на перестановке с лазейкой TP = (G , F, ) с областью определения Sig и пространством ключей/лазеек , а так же на случайном оракуле R: Msg → Sig. Тогда, для всех t 0 , всех 1 и всех (wsig → owp , , t ,( , , , , ) СлПСО редукция В в виде абсолютно черного ящика для ХПОО имее где - , - , - и - - это количество запросов В к G, , F, исоответственно, а - количество экземпляров противника, запущенных B. В доказательстве используется безопасная техника разделения оракулов Hsiao-Reyzin'a [11]. Для F и идеальной (т.е. случайной) перестановки с лазейкой = (G , F, ), определённых в теореме 3, необходимо задать функции , оракул B = , где является однонаправленной, так же как и ρ . При этом существует противник A_ХПОО , подделывающий ХПОО-подпись путем предоставления оракулу доступа к любому сообщению, т.е. он взламывает ХПОО в самом сильном случае. Грубо говоря, оракул разрешает инверсию на каждом выходе всякий раз как появляется прообраз для y’ относительно функции  : это позволяет инвертироватьдля любого выхода , и, следовательно, произвольно фальсифицировать подпись в СлПСО. Тем не менее, задача обращения функции на случайном y зависит от правильности вычисления прообраза у относительно функции ρ, что является такой же сложной задачей, как и обращение функции ρ, следовательно эта задача невыполнима , если является однонаправленной. Поэтому оракул используется для обращения для выходов, отличных от случайного шифртекста, что не позволяет выиграть ОНФ игру.

Термины

1)ХПОО - Хэш функция с полной областью определения (full domain hash, FDH) – схема цифровой подписи, основанная на использовании алгоритма RSA, которая соответствует парадигме hash-and-sign. Она доказуемо безопасна в модели случайного оракула. ХПОО включает в себя вычисление хэша от сообщения при помощи функции, размер образа которой соответствует размеру модуля (n=p⋅q) RSA , который затем возводится в секретную экспоненту (d)

2)Случайный Оракул СО (Random Oracle RO)— это абстрактная функция, которую можно представить в виде следующей модели. Пусть существует некий чёрный ящик, на вход которого можно подать строку любой длины. При первом запросе на выходе случайный оракул (RO — Random Oracle) выдаёт строку истинно случайных чисел фиксированной длины и записывает "запрос/ответ" в память. При последующих запросах RO проверяет: если такой запрос уже был, то выдаётся предыдущий ответ. Если не было, то производится новый цикл: генерация истинно случайной строки, её вывод, запись в память запроса и ответа. Такое гипотетическое устройство могло бы состоять из генератора истинно случайных чисел с памятью и процессором, но при количестве запросов, стремящимся к очень большим величинам (что требуется для моделирования криптопротоколов), его память и быстродействие также должны стремиться к бесконечности. Случайный Оракул может использоваться как идеализироанная модель хэш функции.

3)Редукция безопасности (security reduction) – вероятностный полиномиальный алгоритм работы случайного оракула, сводящий атаку на некоторую схему к решению сложной математической задачи, лежащей в основе данной схемы. Используется для доказательства высокой стойкости криптографических алгоритмов. Способ доказательства при помощи редукции называется «сведением к противоречию» : поиску простого решения трудной задачи (подробнее см. работу Ivan Damgard : «A «proof-reading» of some issues in cryptography»).

4)Программируемость (programmability) – свойство случайного оракула., состоящее в том, что для случайного оракула можно заранее задать любой необходимый метод вычисления выходных значений, при условии, что они являются равномерно распределёнными

5)Coin-string – случайная последовательность, генератор случайных чисел, часто используется в вероятностной машине Тьюринга

6)Игра (game) – способ описания некоторого свойства безопасности системы. В игре заранее определены возможности потенциального противника и система считается безопасной до тех пор, пока противник не сможет выиграть игру

7)НР-АВШ атака неразличимости по выбранному шифртексту (IND-CCA indistinguishability under (non-adaptive) chosen ciphertext attack ) - одна из разновидностей атаки неразличимости. Криптосистема считается безопасносной с точки зрения неразличимости, если ни один противник, получивший шифртекст одного из двух сообщений (М1 и М2 заданных противником) , не способен различить какому из двух сообщений соответствует шифртекст с вероятностью, значительно превышающей вероятность угадывания (1/2). НР-АВШ описывается в терминах игры между противником претендентом. В схемах, безопасность которых основана на решении сложной вычислительной задачи, противник представлен в виде вероятностной полиномиальной машины Тьюринга, т.е. это значит, что он должен завершить игру за полиномиальное количество шагов. Противнику предоставляется открытый ключ pk, алгоритм шифрования сообщения M на ключе pk E(pk,M) , а так же доступ к «оракулу расшифрования», который может по запросу противника расшифровать любой шифртекст. Противник может использовать оракул расшифрования лишь до тех пор, пока не получит «контрольный шифртекст» (в случае адаптивной атаки НР-АВШ 2 противник может продолжить использование оракула даже после получения контрольного шифртекста, при условии, что он не будет направлен в оракул расшифрования) : Претендент генерирует ключевую пару PK, SK, основанную на некотором секретном параметре k (например размер ключа в битах), и предоставляет противнику доступ к открытому ключу PK. Ключ SK претендент оставляет себе. Противник может производить шифрование любое количество раз, обращаться к оракулу расшифрования любое количество раз, или другие операции вычислений. В итоге противник предоставляет претенденту два различных открытых текста М0 и М1. Претендент случайным образом выбирает бил b ∈ {0, 1} и отправляет «контрольный шифртекст» С = E(PK, Mb) противнику. Противник может проводить любое количество дополнительных вычислений или шифрований. 5.1) В случае неадаптивной атаки (НР-АВШ) противник больше не может использовать оракул расшифрования. 5.2) В случае адаптивной атаки (НР-FDI2) противник может продолжать использовать оракул расшифрования, но при этом не может направить в него контрольный шифртекст С.

Противник выдаёт значение бита b.

Система считается НР-АВШ (НР-АВШ2) безопасной, если противник угадывает значение b с вероятностью, не отличимой от вероятности угадывания.

8)Нулевое разглашение (zero-knowledge) - понятие, используемое в криптографии. Доказательство с нулевым разглашением (или протокол с нулевым разглашением) представляет собой метод взаимодействия, при котором первая сторона может доказать второй стороне достоверность некоторого утверждения (чаще математического), без раскрытия какой-либо секретной информации о себе.

9)Преобладание (advantage) – термин, означающий что противник имеет вероятность,большую вероятности угадывания в атаке неразличимости

10)Семантическая безопасность (semantic security) - понятие , используемое в асимметричной криптографии. Система считается семантически безопасной, если противник, имеющий ограниченные вычислительные ресурсы, не может получить однозначную информацию об открытом тексте, при условии, что ему доступны шифртекст и соответствующий открытый ключ.

11) Конкретная безопасность (exact security / concrete security) – приближение, ориентированное на практические задачи, целью которого является уточнение вычислительной сложности , с которой сталкивается противник, по сравнению с обобщённой полиномиальной моделью.

12)ОПАШ оптимальный паддинг при асимметричном шифровании (Optimal Asymmetric Encryption Padding (OAEP)) - схема паддинга, часто используемая вместе с алгоритмом RSA. Алгоритм основан на сети Фейстеля, которая использует пару случайных оракулов G и H для преобразования открытого текста до начала асимметричного шифрования. В сочетании с некоторой однонаправленной перестановкой с лазейкой f это преобразование превращается в схему, для которой в модели случайного оракула можно доказать семантическую безопасность против атаки НР-АВШ. ОПАШ имеет две цели : - Внедрить элемент случайности , который может быть использован для преобразования детерминированной схемы шифрования (например традиционный RSA) в вероятностную схему. - Предотвращение частичной дешифровки текста на основании неспособности противника найти обратную (к однонаправленной подстановке с лазейкой) подстановку

14) Непрограммирующая редукция безопасности НПРБ (Non-programming reduction NPRed) – редукция совершенно не имеющая контроля над ответами случайного оракула. Случайный оракул выбирается один раз независимо от редукции, и остаётся неизменным (т.е. ответы на запросы противника генерируются по схеме, определённой один раз).

15)Случайно программирующая редукция безопасности СПРБ (Randomly-programming reduction RPRed) – редукция может программировать СО лишь случайным, а не конкретно заданным способом . Такой вариант является промежуточным между полсностью программирующей и непрограммирующей редукциями.

Контакты авторов материала

  1. Darmstadt University of Technology, Germany
  2. IBM Research Zurich, Switzerland
  3. 3,0 3,1 University of California, San Diego, USA
  4. Portland State University, Portland, Oregon, USA
  5. Laboratory for Cryptologic Algorithms (LACAL), EPFL, Lausanne, Switzerland

Примечания

Литература

  1. 1,0 1,1 Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Proceedings of the Annual Conference on Computer and Communications Security (CCS). ACM Press, New York (1993)
  2. 2,0 2,1 Bellare, M., Rogaway, P.: Optimal asymmetric encryption — how to encrypt with RSA. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995)
  3. 3,0 3,1 Dodis, Y., Oliveira, R., Pietrzak, K.: On the generic insecurity of the full domain hash. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 449–466. Springer,Heidelberg (2005)
  4. Конкретная безопасность (exact security / concrete security) – приближение, ориентированное на практические задачи, целью которого является уточнение вычислительной сложности , с которой сталкивается противник, по сравнению с обобщённой полиномиальной моделью.
  5. ОПАШ оптимальный паддинг при асимметричном шифровании (Optimal Asymmetric Encryption Padding (OAEP))
  6. 6,0 6,1 6,2 Полностью программирующая редукция безопасности ППРБ (Fully-programmin reduction FPRed) - редукции, поддерживающие программирование случайного оракула без ограничений.
  7. Coron, J.S.: On the exact security of full domain hash. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 229–235. Springer, Heidelberg (2000)
  8. Coron, J.S.: On the exact security of full domain hash. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 229–235. Springer, Heidelberg (2000)
  9. Случайно программирующая редукция безопасности СПРБ (Randomly-programming reduction RPRed) – редукция может программировать СО лишь случайным, а не конкретно заданным способом . Такой вариант является промежуточным между полсностью программирующей и непрограммирующей редукциями.
  10. Hofheinz, D., Kiltz, E.: Programmable hash functions and their applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 21–38. Springer, Heidelberg (2008)
  11. 2) Случайный Оракул СО (Random Oracle RO)— это абстрактная функция, которую можно представить в виде следующей модели. Пусть существует некий чёрный ящик, на вход которого можно подать строку любой длины. При первом запросе на выходе случайный оракул (RO — Random Oracle) выдаёт строку истинно случайных чисел фиксированной длины и записывает "запрос/ответ" в память. При последующих запросах RO проверяет: если такой запрос уже был, то выдаётся предыдущий ответ. Если не было, то производится новый цикл: генерация истинно случайной строки, её вывод, запись в память запроса и ответа. Такое гипотетическое устройство могло бы состоять из генератора истинно случайных чисел с памятью и процессором, но при количестве запросов, стремящимся к очень большим величинам (что требуется для моделирования криптопротоколов), его память и быстродействие также должны стремиться к бесконечности. Случайный Оракул может использоваться как идеализироанная модель хэш функции.
  12. Непрограммирующая редукция безопасности НПРБ (Non-programming reduction NPRed) – редукция совершенно не имеющая контроля над ответами случайного оракула. Случайный оракул выбирается один раз независимо от редукции, и остаётся неизменным (т.е. ответы на запросы противника генерируются по схеме, определённой один раз).
  13. Bellare, M., Rogaway, P.: The exact security of digital signatures — how to sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996)
  14. Boneh, D., Franklin, M.K.: Identity-based encryption from the weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)
  15. 5) Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. Journal of Cryptology 17(4), 297–319 (2004) .
  16. Canetti, R., Kilian, J., Petrank, E., Rosen, A.: Black-box concurrent zeroknowledge requires ˜Ω (log n) rounds. In: Proceedings of the Annual Symposium on the Theory of Computing, STOC 2001. pp. 570–579. ACM Press, New York (2001)