Случайная оракульная сводимость

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:21, 19 декабря 2015.
Random Oracle Reducibility
Random Oracle Reducibility.png
Авторы Paul Baecher[@: 1] and
Marc Fischlin[@: 2]
Опубликован ----
Сайт Department of Computer Science
Перевели Maxim Stepanov
Год перевода ----
Скачать оригинал


Аннотация

Мы обсудим понятие сведения случайных оракулов в двух криптографических схемах и . В принципе, случайное предсказание по схеме сводится к одному из предсказаний схемы , если хэш-функция созданного экземпляра (возможно так же на основе предсказания), которая делает безопасной, делает безопасной и . В некотором смысле, стандартные криптографические допущения для схемы вытекают из схемы , мы можем заключить, что схема полагается на слабые предположения. Технически, такой вывод не может быть сделан с учетом только отдельных доказательств в модели случайного предположения для каждой схемы. Понятие случайной сводимости предсказаний сразу позволяет немедленно передавать немгновенный результат из немгновенной схемы в схему . Мы, тем не менее, главным образом, заинтересованы в направлении установления иерархической схемы, основанной случайным предположением в области безопасности. В качестве примера, рассмотрим шифровальную схему Диффи-Хеллмана (DH) Cash et al. (Journal of Cryptology, 2009), который был представлен как безопасный под DH допущениями в схеме случайного предположения. Таким образом, чтобы улучшить схему шифрования, основанную на хэше ElGamal, опираясь на модели случайных предположений и строгие DH допущения, в которых преступник так же получает доступ к DH принятию оракульных решений. Как указывалось выше, мы считаем, что случайное предположение в двойной DH схеме, сводится к одной из хэшированных ElGamal криптографических схем. Наконец, мы рассмотрим дальнейшие сокращения случайного предсказания между общими схемами сигнатур, такими как GQ, PSS, и FDH.

Ключевые слова

Введение

Предположим, у Вас есть криптографическая схема , для которой может быть доказана безопасность случайной оракульной модели при некоторых допущениях , скажем, RSA допущение. Более того, допустим, что некто представляет Вам схему с той же целью, которая так же безопасна в случайной модели, но при потенциально более слабых допущениях , таких как факторинг. Понятно, что будь это не случайное предположение, и схема будет улучшаться по сравнения с со временем в других релевантных аспектах, таких как эффективность, следует отдать предпочтение схеме . К сожалению, случайная оракульная модель вносит некоторую нежелательную неопределенность при простейшем следовании стратегии выбора схемы с наиболее простыми допущениями.
Формально, доказательства в модели случайного оракула (ROM) все полагаются на одинаково сильных случайных хэш-функциях, но очень часто точные требования к хеш-функции для проведения доказательства безопасности для схемы остаются неясными. Это тем более верно, поскольку случайное предположение в некоторых схемах не мгновенно в том смысле, что эффективная хэш-функция не может надежно заменить случайный оракул [1]. Для нашего примера схемы и это означает, что схема может рассчитывать на более слабое допущение , но фактические требования к хеш-функции могут быть намного строже, чем для . В крайнем случае, хэш-функция в схеме может быть не мгновенна, в то время как хэш-функция для может основываться на очень мягком криптографическом допущении, таком как сопротивление коллизиям (хотя никаких доказательств не было найдено до сих пор).
Естественным подходом к преодолению проблемы было бы определение точных требований к хэш-функции и доказательство того, что схема также опирается на более слабые требования для хэш-функции, чем схемы . Однако, закрепление этих свойств случайных оракулов часто утомительно и не приводит к желаемым результатам, особенно если нужно показать, что эти условия необходимы. Одним из примеров являются свойства хэш-функции для OAEP, где Болдырева и Фешлин[2], затем Килц и др. [3] показали необходимые и, для значительно более слабых понятий безопасности, чем IND-CCA, достаточные условия для хэш-функций (в комбинации с дополнительными предположениями об основных перестановках). Ни один из этих результатов, однако, не показывает желаемый уровень безопасности. В дополнение к этим результатам, Килц и Питрсак[4] утверждали, что для произвольных перестановок, хеш-функция в OAEP не может быть безопасно подтверждена выводом IND-CCA. Последний результат не применим к специфическим перестановкам, таким как RSA.
Случайная оракульная сводимость.Стратегия, которую мы предлагаем здесь, основана на классическом редукционном подходе связывания криптографических предположений: Показать, что любая хеш-функция , начиная от эффективных экземпляров в случайных оракулах, которая делает схема безопасной при допущениях , так же делает схему безопасной при допущениях . Технически, это, кажется, слишком оптимистично, потому что хэш-функции в различных схемах часто не могут быть использованы без изменений, т.к. полагаются на разные области, ранги и т.д. Таким образом, мы допускаем "структурную" трансформацию для схемы в зависимости от конкретной хэш-функции. Есть три возможности связать хэш-функции в схемах:

Определение 1 (Случайная оракульная сводимость - неофициально)

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


Некоторые детали не освещаются в этом варианте определения, такие как например что есть «безопасная» схема, какие свойства преобразований должны удовлетворять условиям или как рассматриваются криптографические предположения экземпляров хэш-функций. Мы заполним эти ниши в формальном определении, но пока что оставим их неофициальными. Отметим, однако, что формальное определение покрывает любой тип хэш-функции, то есть лежащие в основе предсказаний, а так же имеющие ключи и краткие описания, или их смеси. В частности, безопасность схему. В сильном случае может быть известна только для случайного предсказания Н0. При одинаковых допущениях А = В, или даже если А⊆ B, все три понятия совпадают. Разница лучше всего объясняется для случая B (предположения А строго сильнее, чем В. Строгое понятие в этом случае может использоваться неформально. Говорят: "схема B строго превосходит схему А в отношении предположения даже для хэш-функции". Сильный и, предположительно, более доступный подход можно охарактеризовать как: "схема B, по крайней мере так же хороша, как схема А в отношении предположений, но потенциально превосходит ее". Слабый случай говорит, что "схема B по крайней мере, так же хороша, как схема А". С точки зрения предположений безопасности, кажется, что строгие и сильные варианты наиболее интересны(отсюда названия); слабое соответствие не обеспечивает потенциальное улучшение в отношении предположения. Отметим, что сильное соответствие обычно обеспечивает безопасность схемы В в случайной оракульной модели и может быть представлено без доказательства безопасности схемы А. Мы лишь представили зависимость через предпосылку к импликации, чтобы понятия были сопоставимы. В качестве первой проверки адекватности, как предыдущие не мгновенные результаты относятся к определениям любого вида. Если хеш-функция безопасности B может (слабо, сильно, или строго) сводиться к хэш-функции безопасности A, и B оказывается не мгновенной, то это также следует для схемы A (иначе TH был бы действительным экземпляром для B ). В этой связи подход снижения также позволяет расширить не мгновенные результаты без непосредственной демонстрации неэффективности эффективных хеш-функций. И наоборот, любой новый результат безопасных инстанций A сразу передается в B. Кроме того, немедленно следует, что есть схемы A (позволяющие эффективные экземпляры) и B (будучи не мгновенной), что случайное предположение B даже слабо не сводится к предположению для схемы A. Пример: Хэшированное ElGamal шифрование. Чтобы показать, что сильный подход применим и определение нетривиально, мы рассмотрим случай шифрования хешированным ElGamal [5], и его выбранный зашифрованный текст как доказательство безопасности сильного подхода для оракульной модели предположений Диффи Хеллмана (DH)[12]. Здесь сильное DH предположение говорит, что вычисление DH ключей является недопустимым, даже если дан (ограниченный) доступ к принятию решений DH оракула. Cash et al. представил вариант, который показывает, что CCA-безопасность обеспечивается с помощью (регулярных) DH предположений в модели случайного оракула. Это яркий пример двух схем, где вариант может улучшаться с течением времени с точки зрения предположения, но где этот вывод технически не известно из-за случайности оракульной модели. Оригинальная схема хэш-шифрования ElGamal шифрует сообщение с помощью открытого ключа, где и для хешированного DH, ключа и симметричной схемы шифрования Enc. Вариант в , а вычисляет два связанных DH ключа с помощью открытых ключейи , и получает зашифрованный текст для . Мы показываем, за исключением небольшого ответвления схемы в [6], что случайные оракулы могут быть сильно сведены к одному из хэшей ElGamal. Зашифрованный текст в нашем варианте определяются т.е. мы разобьем хеширование на две оценки, по одной для каждого открытого ключа, и будем использовать второй ключ как своего рода подтверждение того, что первый ключ правильно вычислен. Мы можем рассматривать это как преобразования , где мы используем специальную схему симметричного шифрования, в которой ключ К1 подается на вход.Тогда мы доказываем, что безопасность IND-CCA для хэшированного кода Эль-Гамаля подразумевает безопасность парной схемы DH для любой хеш-функции при тех же предположения, при которых является безопасным. Мы также показываем, что наш вариант является безопасным в модели случайного предсказания, учитывая только положения, приведенные. Отсюда следует, что случайный оракул в нашей схеме сильно сводится к одному из хэшей ElGamal. Следует отметить, что для еще одной хэшированной схемы ElGamal, связанной с первоначальной схемой, была показана немгновенность[7]. Хотя схема отличается в двух важных аспектах от нашей схемы. Во-первых, их хэш шифрование Эль-Гамаля не использует случайности и, таким образом, является детерминированным. Во-вторых, понятие безопасности рассмотрено в IND-CCA-сохранении, которое дает противнику одновременно получить доступ к алгоритмам с открытыми ключами и к симметричной схеме с секретными ключами. В отличие от них, мы используем стандартное понятие безопасности IND-CCA для гибридной схемы с открытым ключом. Отметим, что сведение безопасности для нашего варианта с базовыми примитивами типа задачи Диффи-Хеллмана для случайного оракула H0 меньше, чем в терминах конкретной области. В то же время, наша схема образует случайный оракул в оригинальной схеме. Конечно, четкость границ безопасности является еще одним важным аспектом, кроме эффективности, при рассмотрении случайных сводимостей оракула. В принципе, это можно было бы включить в определение в качестве явного требования. Мы отказались делать так, потому что оба аспекта, четкость границ и эффективность зависят в некоторой степени от индивидуального желания платить за дополнительные гарантии безопасности для случайной сводимости оракула. Обратите внимание, что оба доказательства представлены для модели случайного оракула, где четкие границы в любом случае должны быть приняты с недоверием.

Восстановление сигнатурных схем. Мы приведем дополнительные примеры применимости понятия случайной сводимости оракула с учетом общих сигнатурных схем, таких как Guillou-Quisquater [8] или PSS [9], и покажем, что случайный оракул вероятностной версии FDH [10] (Полно-доменной хэш), сводится к случайным оракулам в этих схемах. Тем не менее, обратите внимание, что для FDH сигнатур известно только то, что они немгновенны для простых оценок хэшей над сообщением, то есть не случайны. Первый результат относится только к случайным перестановкам (то есть, не известно, применим ли результат к RSA), а второй, более поздний результат, имеет место при RSA и рассматривается как черный ящик группы. Любой прогресс в плане немгновенности FDH сигнатур для нашего вероятностного случая, таким образом, сразу же позволяют заключить, что схема сигнатуры Guillou-Quisquater и схема PSS являются немгновенными. Это каким-то образом расширяет результат немгновенности Голдвассера и Калая [11] об общих (и несколько надуманных) схемах Fiat-Shamir в "более естественном" виде. Мы обсудим другую случайную сводимость вероятностного оракула BLS сигнатур[12] в схеме сигнатуры Шнорра [13]. В этом случае, однако, мы должны выдвинуть нестандартное предположение, чтобы сделать работу по сокращению, а именно, знание экспоненциального предположения KEA1[14], которое утверждает, что когда дополняется значение X в кортеже Диффи-Хеллмана , надо знать дискретный логарифм у из Y. Для случайных оракулов это означает, что, если наша версия схемы BLS является немгновенной, то и схема сигнатуры Шнорра или предположение KEA1 ложны.

Несколько предостережений. Так же, как сводимость между теоретико-числовыми предположениями касалась лишь таких проблем, как факторинг и RSA, но не касались вопроса о действительной трудности RSA, сводимость для случайных оракулов не означает, что схема B, сама по себе является безопасной (в предположениях В) или, что хэш-функция может быть надежным экземпляром. Сведение говорит только, что схема В может быть безопасной, как схема А в отношении хеш-функции. Так как мы не ставим каких-либо формальных критериев для безопасности схемы А, которая может быть не безопасна, потенциальное сведение может быть тривиальным. Однако, как для соотношения предположений теории чисел, где сильное предположение обычно сопровождается некоторым анализом прочности, схема А, как правило, приходит с какой-либо формой гарантии безопасности. Часто, это является, по крайней мере, доказательством безопасности в модели случайного оракула, а иногда и для их расслабления как непрограммируемых случайных оракулов [15], отслеживаемых случайных оракулов [16], или неплотных случайных оракулов [17]. Преимуществом нашего подхода является то, что по нему сразу же следует, что В может быть также безопасно для соответствующих предположений, как и А. Предостережение состоит в том, что хэш-функция трансформируясь T H, в отличие от случайных оракулов, подчиняется некоторой структуре, так же как "раскол" оценки в нашем примере ElGamal. Поэтому, когда создается какая-то эффективная хэш-функция h, схема B может стать небезопасной для преобразованной хэш-функция Т h, несмотря на сокращение и доказательства 2 Чтобы быть точным, нужно проверить предположение KEA1, даже если можно получить дополнительные сигнатуры Шнорра под Ключ Х., что делает В безопасной для случайного оракула . В то же время, B может быть безопасным, когда создается с h непосредственно, а не через преобразования Т! Мы наблюдаем, однако, что это является неотъемлимым ограничением модели случайного оракула: Это полностью обеспечивается эвристикой, которая не позволяет сделать вывод о безопасности для конкретных экземпляров. Наш подход, по крайней мере, дает некоторую уверенность в выборе хеш-функции в том смысле, что безопасность является, по крайней мере, не ниже безопасности другой модели.

Случайная оракульная сводимость

Хэш-функции. Рассматриваем семейство хэш-функций Н, которые принимаются как образец из , согласно параметрам безопасности лямбда. Таким образом, ясно также, что хэш-функция H может иметь вход или выход ограниченной длины, зависящей от А. Мы пишем H ← (1^L) для отбора примеров. Например, чтобы смоделировать случайный оракул, обозначим через (1^L) семейство всех функций с указанного домена и диапазона и выберем случайную функцию из этого множества. В дальнейшем мы обычно будем просто определять хэш-функции H (•) с описанием самого Н. Мы предполагаем, что хэш-функции детерминированы в том смысле, что, как только хеш-функция была выбрана, ее дальнейшее поведение фиксировано. Хэш-функция семейства могут рассчитывать на некоторые криптографические предположения  ; в случае случайных оракулов, необходимость предположений отсутствует, поскольку выборка случайной функции уже предоставляет все желаемые свойства безопасности. Основываясь на хэш-функции H для схемы А, мы пишем AH для схемы, где каждая сторона или алгоритм получает доступ к оракулу Н. Кроме того, хэш-функция H может включать в себя публичное описание части, которая затем будет использоваться всеми сторонами и алгоритмами. Эта публичная часть может быть, например, полным описанием H, или только ее части, например, если Н является гибридом между случайным оракулом и ключом хэш-функции. Хэш-функция семейства является эффективной, если она удовлетворяет определению, например, сэмпл-функция Н, эффективно вычислимая и полностью описанная посредством публичной части. Преобразования. Хэш-функция H, используемая в криптографической схеме А, возможно, не сразу применима к другой схеме В по причине несовпадающих доменов и диапозонов. Поэтому мы используем алгоритм преобразования Т, так что схема В затем использует хэш-функцию (семантически, так что любой алгоритм получает полное публичное описание для использования при входе). Мы пишем TH для соответствующего семейства хэш-функций (описано путем отбора проб и оценки TH). В идеале, преобразование следует сделать только для структурных изменений (например, адаптации домена и диапазона), и должны быть детерминированными. Существует, однако, один технический аспект о структуре преобразований. А именно, мы явно требуем, чтобы преобразование являлось неструктурированным. Причина в том, что если мы допустим трансформацию с сохранением структуры преобразований, можно будет построить особые преобразования, с помощью которых некоторые схемы B всегда будут сводимы к схеме А. Чтобы получить представление о проблеме, рассмотрим произвольные схемы A и В, которые являются безопасными в модели случайного оракула. Пусть имеем Т с состоянием преобразования, которое игнорирует его оракул H и эффективно реализует случайный оракул с помощью ленивой выборки. Если ВТН является безопасной, то, очевидно, схема В так же безопасна, в соответствии с определением 1, приводимого в схеме А, несмотря на произвольную выборку из двух схем. Аналогичная проблема возникает с экземплярами: Пусть схема В в настоящее время является экземпляром некоторого семейства . Тогда строится преобразование Т, снова игнорируется его оракул, и, вместо первоначально, принимаются образцы функции Н0 ← и ответы на последующие запросы по Н0. Опять же, схема B остается безопасной и сводится к схеме А. Оба примера полагаются на динамическую функцию преобразования последовательных ответов и выбора хэшей. Таким образом, для того, чтобы исключить такие тривиальные случаи, мы предположим, что преобразования всегда неструктурированны. Это положение на первый взгляд может показаться чрезмерно ограничивающим, но, на самом деле, является полностью оправданным, поскольку хэш-функции по своей сути неструктурированны.

Безопасность схем. Мы считаем, что безопасность схем определяется общими понятиями, хотя можем моделировать и основываясь на их свойствах. Мы позволяем расширение (A, G), для которого обозначим преимущество противника игры G, т.е. вероятность успеха противника выиграть игру. Это делает Adv неявной частью G. Здесь, в принятия решений игр преимущество, как правило, обозначает вероятность успеха противника минус тривиальное догадки с вероятностью 1/2, а в вычислительных играх преимущество, как правило, вероятность вычисления решения противником. Аналогично для хэш-функций, мы можем написать GH для игры безопасности, в которой все стороны и алгоритмы получат доступ к Н. Понятно, что выбор является частью игры безопасности. Мы пишем GH для игры, для которой хэш-функция выбрана из семейства . Мы предполагаем, что предположения безопасности для схемы А есть набор элементарных свойств, таких, как незабываемость нижележащего MAC или теоретико-числовых предположений, твердость факторинга. Мы можем применить общий набор операций и отношений с предположениями очень точно, например, A ∪ B включает в себя все предположения, изложенные в А и В, а В ⊆ A означает, что если В имеет предположения, то и А тоже. Этот подход является легко применимым для предположений хэш-функции H и, возможно, предположений трансформации Т. Мы также предполагаем, что предположения "отказа", то есть, нужны определенные наборы, либо предположение не выполнится. Формально мы можем определить универсум предположений U и сказать, что любые предположения в U \ A ложны. Обратите внимание, что мы продолжаем формальные спецификации игр и предположений на минимальном уровне. Это возможно, как мы позже потребуем, когда случайный оракул сводится к конкретным играм и предположениям. Таким образом, до утверждения сведения, стоит рассмотреть "умные" игры и предположения. Мы только должны выставить очень ограниченные синтаксические требования, возможно, даже допускающие некоторые противоречивые предположения в A ∪ B (в этом случае, как правило, они становятся тривиальными требованиями).

Определение 2 (Игра на основе безопасности)

Обозначим через схему шифрования и GH игру для хэша семейства Х. Схема А называется GH -безопасной при предположениях А для хэш семейства Х, опирающихся на предположения Н, если для любого эффективного состояния А мы знаем, что , которым можно пренебречь в параметре безопасности. В качестве примера рассмотрим игру безопасности IND-CCA для схемы шифрования А (в модели случайного оракула), в котором игра GH происходит в несколько этапов, где А на первом этапе получает открытый ключ (в случае асимметричной схемы) и получает доступ к дешифрованию оракула плюс к случайному оракулу, затем выводит пару сообщений равной длины M0, M1, чтобы получить один вызов зашифрованной модели для закрытого случайного бита Ь, и, наконец, по-прежнему просит расшифровку запросов на вызов за исключением зашифрованного текста.Противник выигрывает, если правильно предсказывает B, и преимущество противника есть вероятность правильного прогноза минус 1/2. В приведенной выше схеме безопасности IND-CCA шифрования, с опорой на некоторое криптографическое предположение, делается отметка GH-безопасности под буквой случайного оракула . Случайная оракульная сводимость. Как было указано во введении, мы рассмотрим понятия сильной, слабой и строгой сводимости случайного оракула.

Определение 3 (случайная оракульная сводимость)

Пусть имеется криптографическая схема с игрой безопасности А и соответствующими предположениями, и пусть имеется также криптографическая схема с игрой В G^B и предположениями В. Тогда случайный оракул в схеме В (строго/сильно/слабо) сводится к случайному оракулу в схеме А, если для каждой хеш-функции семейства Н, опираясь на предположениях Н, существуют преобразования Т:

Будем говорить, что (слабо или сильно или строго) сводится к случайному оракулу . Оракул сводим за полиномиальное время, если он сводится с помощью детерминированных неизвестных за полиномиальное время преобразований Т для любого семейства Н. Если хэш-функция зависит от времени, мы говорим, что В является случайным оракулом и сводится (RO -сводимостью) к А. Некоторые замечания относительно определений и вариаций: - Вышесказанное не исключает возможность тривиальных примеров, когда схема В в самом деле опирается на более сильные предположениях, чем схема А, например, если это подмножество В. Как объяснено во введении, самыми интересными примерами кажутся те, где предположения В слабее, чем А или по крайней мере сравнимы. Иногда, однако, интерес может представлять случай, который требует более сильных предположений В, но что более эффективный. - Мы можем разработать больше понятий, касающихся порядка количественной сводимости. Выше было показано, что преобразование может зависеть от конкретной хэш-функции семейства Н, и, таким образом возможно появление специфических свойств Х. Может так же альтернативно требоваться, что преобразование должно быть универсальным в том смысле, что он работает для любого Н. - Приведенное выше определение предполагает, что преобразование Т не зависит от дополнительных предположений. В целом, можно указать предположения T и сказать, что схема В является безопасной при предположениях В = B ∪ Т. - Для нашего синтаксиса противник B в игре с преобразованным случайным оракулом смог бы получить доступ к TH, но не саму Н. Это может быть легко исправлено, если позволить преобразованию Т получить прямой доступ к Н через специальный режим запроса.

Основные результаты, относящиеся к сводимости понятий

Покажем сначала, что строгая сводимость предполагает сильную сводимость, что подразумевает слабую сводимость. Доказательство. А синтаксическая, и опущена из соображений экономии места.

Предложение 1 (Строгая ⇒ Сильная⇒ слабая сводимость)

Пусть имеется криптографическая схема с игрой безопасности А и предположениями, и пусть В - криптографическая схема с игрой G^B и предположениями В. Если случайный оракул в схеме В строго сводится к случайному оракулу в схеме А, то он также сильно сводится к нему. Если сильно сводится, то сводится и слабо. Обсудим теперь схему, которая поддерживает сильное сведение, но не является строгой. Обратите внимание, что для A⊆ B это требование будет тривиальным, потому что тогда понятия совпадают. Вместо этого, наш пример разделения даже имеет место для B включается в А.

Предположение2 (Сильная сводимость !⇒ строгая сводимость)

Существуют схемы A, B для игр и предположений A, B такие, что B включается в A, и случайный оракул из B сильно сводится к одной из схем А, но не строго. Доказательство. Пусть схема использует две копии схемы сигнатуры Lamport в единицу времени, основанная на предполагаемой односторонней функции F, а основана с помощью функции данного оракульного хэша. Пусть GP - стандартная незабываемая игра для разовых схем сигнатуры, и пусть имеется предположение, что основная функция F действительно односторонняя. Пусть В и будет той же схемой, что и игра, но пусть В - пустое множество. Рассмотрим хэш-функцию семейства Н, образцы тривиальной функции , где Н пусто. F является односторонней, независимо от H-части сигнатуры. В отличие от B, она будет небезопасна в В и для тривиальной функции семейства хэшей, потому что, по предположению о минималистичном подходе ко множеству В, функция F не является односторонней. Следовательно, случайный оракул в B не может быть строго сводится к оракулу в А. Наконец, обратите внимание, что для семейства хэш-функции, которая является односторонней схемой сигнатуры В и становится безопасной даже в B, потому что любого фальсификатора должна быть подделана схема сигнатуры для хэш-функции. В то же время, любая схема семейства хеш-функций B является безопасной при A ∪ B. Эти два свойства показывают, что случайный оракул в B сильно сводится к А. Для следующего разделения мы также должны исключить искусственные примеры, где хэш-функция предположения Н "составляется" для предположений в A \ B, чтобы сделать схему B безопасной. Мы говорим, что Н неинтерферирует с А и В тогда и только тогда . В этом случае мы говорим, что случайный оракул на схеме B сводится к оракулу на схеме А под неинтерферирующий хэш предположения, если сводимость имеет место для всех хэш-функция семейства H с неинтерферирующие предположение Х.

Предложение 3 (Слабость !⇒ Сильная сводимость)

Там существует схемы A, B для игр В и предположений А, В, что В (А, а случайный оракул В слабо сводится к одной из схем А, но не сильно для хэш-функций). Доказательство. Рассмотрим снова схему сигнатуры Лампорта для схемы А, опираясь на одностороннюю функцию F (один вариант которой постулируется в A). Схема игнорирует хэш-функции. Пусть G^H В будет незабываемой игрой для одноразовой сигнатуры схемы. Любая хэш-функция делает обе схемы безопасности под предположениям А ∪ B, таких, что случайный оракул слабо сводится к одному из предположений А. Так как В не могут быть в безопасности предполагая только B, потому что хэш-функция не может включать в себя предположение об одном из способов Р по невмешательству, схема не может сильно снизить безопасность случайного оракула. Последствия невозможности создания экземпляра. В этом разделе мы кратко покажем основные результаты о (не) случайных оракулах создания экземпляров. Мы определим невозможность создания экземпляров по отношению к очень рыхлому требованию предположений, оставив на рассмотрение только "стандартные" криптографические предположения в А и В.

Определение 4 (невозможность создания экземпляра)

Пусть – безопасно при предположениях А для случайного оракула Н. Тогда случайный оракул не может быть экземпляром для GH А и А, если для любой эффективной хэш-функции семейства H с предположением H схемы А не A -безопасна по предположениям А.

Предложение 4 (не возможно создать экземпляр В ⇒ аналогично для А)

Предположим, что схема B с GH B и B предположений (строго соответственно/сильно соответственно/слабо) за полиномиальное время RO-сводится к схеме А для А и (True) предположения А. Если невозможно создать экземлпяр для В для GH, в разделе В ( для строгих сокращений) соответственно A ∪ B (для сильного или слабого сокращения), то А для GH A и предположения А. Доказательство снова довольно просто получается из определений. Понятно, что это предполагает, что любой результат передается в В. Учитывая понятие невозможности создания экземпляра, в следующий раз мы обратим внимание на схемы, для которых случайные оракулы даже слабо не сводимы друг к другу:

Предложение 5 (невозможность сведения)

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

Пример:Хэшированый ElGamal

В этом разделе мы покажем, что хэш-функция в схеме шифрования двойной DH является РО-сводимой к хэш-функции в хешированном ElGamal. Заметим, что мы не знаем, допускает ли оригинал сведение к хешированному ElGamal. Сначала мы рассмотрим классическую схему ElGamal хэш-шифрования, как представлено в [5]. Эта схема, обозначается A = (KGenA, ENCA, Дека) основана на проблеме DH и использует хэш-функции H и симметричный шифр (ENC, DEC). В частности, Предположение 1 (схема шифрования хэшированного ElGamal).

Схема шифрования хэшированного ElGamal в ПЗУ, определяется следующим образом: KGenA (λ) выбор , Return Вернуться Вернуться Предполагая, что схема А защищена симментричным шифром от зашифрованной атаки, где противник имеет доступ к ограниченному DH принятия оракульных решений (это доказано), можно выполнить моделирование случайного оракула по сильному DH предположению. Достаточно доказать безопасность CCA, так как злоумышленник получает решение оракула через дешифрование оракула, например, если часть информации о ключе попала к нему в руки. Мы всегда относятся к атакам с участием только одного вызов на протяжении всей статьи. Двойная DH Схема. Впоследствии, Cash et. al. ввели, так называемого, сильного близнеца DH предположения, который имеет место тогда и только тогда, когда обычное DH предположение выполняется. Соответствующие проблемы DH близнеца так же трудны, но в случае близнеца, мы имеем прямой доступ к оракульному принятию решений. Это позволяет вывести чистое доказательство безопасности для варианта хэша схемы ElGamal. Таким образом, схема с двумя ElGamal позволяет строить более аккуратные теоретико-числовые предположения, сохраняя безопасность CCA. Тем не менее, случайный оракул в схеме с двумя ElGamal шифрами используется несколько иначе, чем в оригинальной схеме: его домен является множеством троек группы элементов, в отличие от кортежей в оригинальной схеме. Хотя это создает проблем в ПЗУ для хэш-функции H: {0, 1} * → {0, 1} λ с произвольной длиной входа, последствия для других свойств безопасности менее ясны. Например, это может быть, что двойная схема DH требует более строгой из хэш-функции. С помощью RO-сводимости мы покажем, что в данном случае эти последствия нам не важны. Структура 2. (Схема шифрования близнецов DH).

Двойная схема шифрования в ПЗУ, определяется следующим образом: KGenB (λ) выбрать Вернуться Вернуться , если множество t ← ⊥Вернуться m Мы можем посмотреть преобразование хэш-функции следующим образом: . Разделение фактического шифрования сообщения для одной ключевой половины и вывод другой в открытом доступе с ключами двойной длины может рассматриваться как алгоритм шифрования. RO-сводимости. Покажем сначала, что наш близнец, схема DH, слабо сводится к случайному оракулу в одной из хешированных схем ElGamal для IND-CCA безопасности, т.е., полагает сильное DH предположение. Мы обсудим позже, что обеспечит схема в модели случайного оракула: Теорема 3. Рассмотрим хэш ElGamal схемы шифрования для игры IND-CCA безопасности, предположение, что симметричное шифрование схемы обеспечивает IND-CCA, и сильное DH предположение выполняется. Тогда близнец шифрования DH, схема B с игрой IND-CCA безопасности, и допущения В, что симметричная схема шифрования обеспечит IND-CCA и что DH предположение выполняется, RO-сильно сводится к хешированному ElGamal схемы шифрования через .Доказательство вытекает из следующих двух утверждений. Предложение 6. В предположениях теоремы 3, близнец схемы шифрования DH слабо RO-сводится к хешированному ElGamal схемы шифрования. Доказательство. Пойдем от противного. Предположим, что существует алгоритм B, который подрывает IND-CCA безопасностm В. Затем мы опишем противника A, который подрывает IND-CCA безопасность. Этот противник моделирует вторую ключевую часть схемы. Описание. Для инициализации моделирования, противник А на входе выбирает другую половину секретного ключа x1 ← Zq и вычисляет соответствующий открытый ключ X1 ← g x1. Следующим работает противник B с входным и отвечает на запросы оракула на основе B следующим образом: - Во-первых, переводит любой хеш-запрос , из В в два запроса в собственный оракул.Точнее, отвечает на запрос с . - Для того, чтобы ответить на вызов запроса В (M0, M1), противник представляет (M0, M1) к своему вызову оракула и анализирует соответствующую часть зашифрованного текста в ответ на (Y, С). Остается вычислить дополнительную информацию путем повторного использования случайности У, полученную от оракула. Противник вычисляет и, наконец, возвращает зашифрованный текст . - При дешифрации запроса (Y, C, k1) из B, противник первый проверяет, соответствует ли (Y, C) значению в зашифрованном запросе, . Если это так, то А сразу же возвращает ⊥. Иначе просит свой расшифровки оракула для дешифрования м (Y, С). Чтобы ответить на запрос, он возвращает м. - Заметим также, что мы можем предоставить B прямой доступ к оракулу Н. Противник А будет просто впереди этого запроса и передаст обратно ответ. Когда, в конце концов, В выводит предположение В, тогда А тоже его выводит. Анализ. Моделирование является совершенным в следующем смысле: В не можете представить зашифрованный ключ дешифрования оракула (после получения вызова зашифрованный при k * 1 6 = k1, которые бы расшифровывались правильно. Следовательно, такие ключи могут быть тут же отклонены, то есть, моделирование только представляет "отброшенные" зашифрованные оракулы, которые никогда не появлялись раньше. Следовательно, А также представляет собой успешного злоумышленника на хешированной схеме ElGamal, если В один для двойной схемы DH. Кроме того, преимущества обоих алгоритмов в их соответствующей IND-CCA идентичны. Для завершения доказательства для сильного сведения мы, наконец, покажем, что наша версия является безопасной в модели случайного оракула: Предложение 7. Близнец шифрования DH схемы B с предположениями В, что симметричная схема шифрования обеспечивает IND-CCA и что DH предположение выполняется, это IND-CCA-безопасность в модели случайного оракула. Доказательство. Доказательство сложнее, когда пары в схеме являются близнецами. В отличие от этого, в нашей схеме пары и связаны слабо. Покажем, что это неплотное соединение может быть сильное моделируемого соединения противника. На первом этапе мы займемся нормализацией противника A против IND-CCA нашей двойной схемы DH. Во-первых, мы можем считать, что А никогда не делает хэш запрос дважды. Во-вторых, мы можем предположить, что А никогда не представляет кортеж (Yi, CI, k) для дешифрования оракула до получения вызова зашифрованный . Это уменьшает вероятность успеха противника с помощью незначительного количества D / Q для полиномиального числа D дешифрования запросов В. В-третьих, мы можем предположить, что противник А не никогда отправляет запрос расшифровки , чтобы, в случае, , оно не оспаривало хэш-функцию о для Z = Y до. Потери составляют не более D • 2 -λ. В-четвертых, мы предполагаем, что противник не представляет для дешифровки оракула, где Yi = Y, но k = К; такой запрос не может быть действительным. В-пятых, мы предполагаем, что Х = Y*1 6, который происходит с вероятностью 1 - 1 / d. Укрощение Хэш-запросов. Рассмотрим нормированную атаку А против нашей двойной схемы D^H. Предположим, что А, в дополнение к T^H, также имеет прямой доступ к случайному оракулу. На самом деле, мы предполагаем, теперь, что все алгоритмы, в том числе и алгоритмы основной схемы противника, никогда не называем TH, но используем H для имитации TH с двух запросов. Определить следующий HashQuery событий, что во время нападения IND-CCA, А в какой-то момент просит запрос Y появляется в вызов зашифрованного текста, и или для общественности Основные данные . Мы показываем, что вероятность (L) из HashQuery событий должна быть незначительной. Для доказательства пойдем от обратного. Затем мы показываем, как разорвать проблемы близнецов (и, таким образом, проблему DH) по алгоритму В. Алгоритм B получает описание группы и значения Y, X0, X1 на вход. Это может также запросить близнец DH оракула о значениях (g, В, D), который выводит 1 тогда и только тогда . Значения x0, x1 служат открытым ключом, представленной А, и Y будут размещены в запросе зашифрованного текста. Алгоритм B запускает атаку А с помощью входных данных, таких как открытый ключ, и имитации случайного оракула и дешифрования запросов следующим образом: - В будет поддерживать список L кортежей вида (A, B, K) или (DH, A , Хl, К), где первый тип соответствует прямому хэш запросу А, а второй тип - неявному запросу хэша. Первоначально, В устанавливает для произвольного значения k0, k1 для хеш-значений для вычисления вызовов зашифрованной функции (обратите внимание, что Y уже известно с самого начала). - Всякий раз, когда делается хэш-запрос (a, b) алгоритмом B, первые поиски записи в L такие, что или образует правильный близнец DH Кортежа (в X0, X1). С только один случай может произойти. Если нашли, и существует запись в L для случая , соответственно, в случае , то заменить эту запись по в L. В любом другом случае, подобрать K наугад из в L. Возврат k. - Если А делает запрос расшифровки , то проверьте или нет. В случае посмотреть запись в L и использовать k0, чтобы расшифровать CI. (Обратите внимание, что, по предположению, K1 должны быть правильными.) Пусть Yi = Y 6. Тогда, так как противник нормализуется, там должна быть запись в L уже, вызванный хэш запроса, где I. (Там не может существовать другого входа для , так как хэш-запросы никогда не повторяются). Учитывая (Yi, Z1, K1), проверить записи , что образует правильный близнец кортеж для X, Y. Если такая запись существует, то использовать k и расшифровать CI. Если такой записи не существует, проверьте кортеж в L и используйте k0 для расшифровки. В противном случае, нужно выбрать новое значение в L, и использовать k для расшифровки. Вернуть расшифрованное сообщение. Чтобы подготовить испытание зашифрованного текста, В использует ранее выбранные значения k, c, помещенные в L, а также выбирает одно из двух сообщений M, N наугад, и возвращает . Если А, заканчивая алгоритм B, записывает все записи в , и повторяет описанную выше процедуру, с той же группой, но с рандомизированными данных, S1-1-а для случайных и случайный бит а. Каждый второй случайный выбор основан на новой случайности. Любой запрос (А, В, С) в двойном D^H Oracle в этом втором прогоне сначала преобразуется в при а = 0, соответственно при а = 1. В конце, В преобразует все пары (A, B) в список L второго прогона, вычисляет и , что фактически удваивает число пар. Нужно запустить на всех комбинациях, чтобы найти решение к двойной проблеме . Анализ. Содержание списка хэша L обеспечивает более проработанную реализацию того, как случайный оракул будет вести себя: Так как любой расшифровки запроса для Yi 6 = Y должен уже содержать соответствующую запись по предположению, мы можно проверить с помощью двойного DH оракула, если у нас уже есть соответствующий вход . Если нет, мы создаем свежую случайную строку и сохраняем неявное представление в L, и позже тщательно проверяем хэш запрос для Y, x (в этом случае мы обновляем запись в L и повторно используем значение k0). Что касается вероятности успеха В, мы называем группу подходящей, если вероятность успеха A на этой группе превышает Е/2. По аргументу усреднения, группа хороша с вероятностью не менее Е/2.Следовательно, учитывая такую хорошую группу, и тот факт, что В обеспечивает идеальное моделирование, В получает право входа или с вероятностью не менее Е/2 в первом периоде. То же самое относится в перспективе ко второму, где повторной рандомизации следует избежать для каждого близнеца запроса DH оракула. С вероятностью ½, алгоритм В получает соответствующие значения и , потому что порядок разрядов во второй итерации скрыт от А. В целом, и пренебрегая незначительными потерями за счет нормализации А, алгоритм В, таким образом, решает двойную задачу DH с вероятностью не менее 3/16.

Сводимость среди сигнатурных схем

В этом разделе мы кратко рассмотрим еще несколько частей нашей работы. В частности, мы даем три отношения между сигнатурными схемами, включая сигнатуры схему GuillouQuisquater (GQ), к которой мы сводим вероятностную версию FDH, схему сигнатуры PSS , к которой мы также сводим вероятностные изменения FDH и, наконец, сводимость Шнорр сигнатур [13] А (вероятностной версии) для BLS сигнатуры [18]. GQ ⇒ FDH. Рассмотрим сначала RSA основе Guillou-Quisquater идентификации схемы и ее производную схему сигнатуры через эвристики Fiat-Shamir [8]. Для открытого ключа и секретного ключа х с X = х mod N вычисляется сигнатура в качестве (R, у) для случайной , и где для . Вероятностный хэш полного домена (FDH) RSA схемы сигнатуры с подписями виде (R, σ) для а = (H (pk, R, M)) d mod N является строго случайным оракулом, сводится к вышеупомянутой Guillou- Quisquater схеме с помощью преобразования для любого типа подделки атаки в предположении RSA. Причина в том, что любоя сигнатура GuillouQuisquater для H может рассматриваться как FDH сигнатура для </math>TH: {0, 1} * -> Z * N</math>, и любая успешная подделка для схемы FDH для TH является, наоборот, действительной подделкой для схемы Guillou- Quisquater. PSS ⇒ FDH. Сведение в другом варианте вероятностного FDH в схеме сигнатуры PSS похоже на случай GQ. Рассмотрим FDH сигнатуры за PSS-кодирующей для . Здесь Н0, Н1, Н2 являются хэш-функциями, полученными из Н, как в схеме PSS. Тогда любая успешная атака на FDH с хэш-функциями TH легко поддается подделыванию от PSS с хэш-функциями H. Следовательно, PSS позволяет строгое сведение случайного оракула к вероятностной версии FDH в предположении, RSA для любого типа подделки атаки. Шнорр ⇒ BLS. Рассмотрим вероятностный вариант схемы BLS сигнатуры [12], где сигнатуры имеют вид для случайности R, сообщение m, закрытый ключ х и открытый ключ X = G^X. Она осуществляется аналогично оригинальной схеме с помощью вычислений сопряжения.





Мы считаем, что схема сигнатуры Шнорра (напомним, что сигнатура существует в виде для ключевого , и является (строго) случайным оракулом и сводится к версии BLS через трансформации . Это справедливо, полагая, дискретный логарифм предположения под расширенной версией предположения KEA1 [18,3], которая гласит, что для любого противника А, для ввода описания группы, g, х, и с доступом к оракулу, сигнатуры Шнорра под ключевой X и хэш-функции оракула, выводит пару , существует противник A0, который подает информацию на тот же вход и имеет доступ к тем же оракулам, выводит у с . Вероятность того, что А будет успешно, но А0 нет, должна быть незначительна для любых А. Предположим теперь, что существует несколько успешных противников B для нашей версии BLS. Построим противника А схемы Шнорра следующим образом. Всякий раз, когда B получает некоторый запрос m, противник A встает вперед этим запросом к собственной сигнатуре оракула. Он использует ответ (C, Y) для расчета , вычисляет (такая, что Н (Р, t) = C) и, наконец, ответы на запросы В(R, H).Это имитирует правильную сигнатуру, так как B ожидает R и . Остается сделать подделку Шнорра с помощью подделки Б, обозначенной .Для этого заметим, что, в соответствии с дополненным предположением KEA1, для A (B работает в подпрограмме), выводимого x по подделке , должен существовать противник A, возвращающий . Это должно быть справедливо и с пренебрежимо малой вероятностью, потому что успешно с не-пренебрежимо малой вероятностью, в противном случае, дополненное предположение KEA1 было бы неверно. Следовательно, существует противник, который создает действительные подделки для схемы Шнорра с не пренебрежимо малой вероятностью.

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

  1. Darmstadt University of Technology, Germany, E-mail: www.minicrypt.de
  2. Darmstadt University of Technology, Germany, E-mail: www.minicrypt.de

Примечание

Литература

  1. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: 30th ACM STOC. pp. 209–218.
  2. Boldyreva, A., Fischlin, M.: Analysis of random oracle instantiation scenarios for OAEP and other practical schemes. In: CRYPTO 2005. LNCS, vol. 3621, pp. 412– 429.
  3. J. H. An, Y. Dodis, and T. Rabin. On the security of joint signature and encryption. In L. Knudsen, editor, Advances in Cryptology – Eurocrypt 2002, volume 2332 of Lecture Notes in Computer Science, pages 83–107. Springer-Verlag, 2002.
  4. Kiltz, E., Pietrzak, K.: On the security of padding-based encryption schemes - or - why we cannot prove OAEP secure in the standard model. In: EUROCRYPT 2009. LNCS, vol. 5479, pp. 389–406.
  5. 5,0 5,1 Abdalla, M., Bellare, M., Rogaway, P.: The oracle Diffie-Hellman assumptions and an analysis of DHIES. In: CT-RSA 2001. LNCS, vol. 2020, pp. 143–158.
  6. Coron, J.S.: On the exact security of full domain hash. In: CRYPTO 2000. LNCS, vol. 1880, pp. 229–235.
  7. Bellare, M., Boldyreva, A., Palacio, A.: An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In: EUROCRYPT 2004. LNCS, vol. 3027, pp. 171–188.
  8. 8,0 8,1 Guillou, L.C., Quisquater, J.J.: A practical zero-knowledge protocol fitted to security microprocessor minimizing both trasmission and memory. In: EUROCRYPT’88. LNCS, vol. 330, pp. 123–128.
  9. J. H. An, Y. Dodis, and T. Rabin. On the security of joint signature and encryption. In L. Knudsen, editor, Advances in Cryptology – Eurocrypt 2002, volume 2332 of Lecture Notes in Computer Science, pages 83–107. Springer-Verlag, 2002.
  10. Dodis, Y., Oliveira, R., Pietrzak, K.: On the generic insecurity of the full domain hash. In: CRYPTO 2005. LNCS, vol. 3621, pp. 449–466.
  11. Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: 44th FOCS. pp. 102–115. IEEE Computer Society Press
  12. 12,0 12,1 Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. Journal of Cryptology 17(4), 297–319
  13. 13,0 13,1 J. H. An, Y. Dodis, and T. Rabin. On the security of joint signature and encryption. In L. Knudsen, editor, Advances in Cryptology – Eurocrypt 2002, volume 2332 of Lecture Notes in Computer Science, pages 83–107. Springer-Verlag, 2002.
  14. Hada, S., Tanaka, T.: On the existence of 3-round zero-knowledge protocols. In: CRYPTO’98. LNCS, vol. 1462, pp. 408–423.
  15. Nielsen, J.B.: Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In: CRYPTO 2002. LNCS, vol. 2442, pp. 111–126.
  16. J. H. An, Y. Dodis, and T. Rabin. On the security of joint signature and encryption. In L. Knudsen, editor, Advances in Cryptology – Eurocrypt 2002, volume 2332 of Lecture Notes in Computer Science, pages 83–107. Springer-Verlag, 2002.
  17. Yoneyama, K., Miyagawa, S., Ohta, K.: Leaky random oracle (extended abstract). In: ProvSec 2008. LNCS, vol. 5324, pp. 226–240.
  18. Fischlin, M., Lehmann, A., Ristenpart, T., Shrimpton, T., Stam, M., Tessaro, S.: Random oracles with(out) programmability. In: ASIACRYPT 2010. LNCS, vol. 6477, pp. 303–320.