Обратимая выборка и адаптивная безопасность

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 10:19, 29 ноября 2015.
On Invertible Sampling and Adaptive Security
On Invertible Sampling and Adaptive Security.png
Авторы Yuval Ishai [@: 1][прим. 1],
Abishek Kumarasubramanian [@: 2],
Claudio Orlandi [@: 3][прим. 2],
Amit Sahai [@: 4][прим. 3].
Опубликован 2010 г.
Сайт www.spms.ntu.edu.sg
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


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

Введение

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

С момента введения MPC в 1980-х [1][2][3][4], было предложено множество определений безопасности и показаны их допустимые результаты. В частности, значительная программа исследовательских работ была вложена в реализацию адаптивно стойких MPC протоколов, безопасность которых необходимо проводить в присутствии противника, который может повредить стороны адаптивно в любой точке в ходе протокола.

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

Адаптивно стойкие протоколы данной статьи были впервые построены Canetti, Feige, Goldreich and Naor [5] в автономную модель, а затем Canetti, Lindell, Ostrovsky and Sahai [6] в универсальную компонуемую (UC) модель [7]. Эти протоколы применяются ко всем детерминированным выполняемым функциям, но в случае рандомизированных выполняемых функций они были ограничены до так называемых адаптивно правильно построенных выполняемых функций [6]. Наглядно, рандомизированные выполняемые функции могут представлять следующую проблему: когда противник повреждает все стороны в реальном исполнении [прим. 4], он узнает, частные случайности всех сторон. Однако в идеальном мире, если идеальные выполняемые функции подбрасывают несколько монет, которые хранятся скрыто и используются во время вычислений, идеальный противник (моделирующее устройство) никогда не узнает эти частные монеты, даже после повреждения всех сторон. Присутствие частной случайности в идеальном мире делает проблематичным реализовать рандомизированные выполняемые функции, в которых случайность не может быть эффективно вычислена из входов и выходов. "Адаптивно правильно построенные" выполняемые функции удовлетворяют синтаксическим требованиям, чтобы они показывали всю свою внутреннюю случайность, когда все стороны повреждены. (Другими словами, надежно реализуя подобные выполняемые функции, не ставится задача сокрытия внутренней случайности выполняемых функций от противника.) Вопрос для общих выполняемых функций был оставлен открытым.

В данной статье мы показываем, что для сильных и хорошо изученных вычислительных предположений, существуют выполняемые функции, которые не могут быть реализованы с помощью адаптивной безопасности. Конкретно, наш главный отрицательный результат зависит от следующих двух предположений:(1) существование так называемых извлекаемых односторонних функций [8][9][10](является обобщением нескольких предположений типа "сведения экспоненты" из литературы [11][12][13][14]), и (2) существование неинтерактивных доказательств с нулевым разглашением (NIZK) для NP [15][16].

Наш отрицательный результат применяется почти к каждой модели адаптивно безопасного вычисления без стираний из литературы. Он включает автономную безопасность в получестных и злонамеренных моделях (в соответствии с определением [17]), UC-безопасность в модели CRS (в соответствии с определением [6]) или даже безопасность в модели OThybrid, где каждая выполняемая функция должна быть обязательно реализована с неадаптивной UC-безопасностью [18][19]. Наш отрицательный результат не применяется к случаю, где только строгое подмножество сторон может быть повреждено (в частности, к MPC с честным большинством). Существование неповрежденных сторон позволяет моделирующему устройству избежать необходимости в "объяснении" выхода выполняемых функций, обеспечивая их внутреннюю случайность. Наш отрицательный результат также не применяется к адаптивной безопасности в автономной модели без повреждения выполнения сообщения [17]; это (нестандартное) понятие адаптивной безопасности не поддерживает даже последовательный состав. Смотрите параграф 1.2 ниже.

Обратимая выборка. Ключевое понятие, которое мы используем, чтобы получить наш отрицательный результат и, которое представляет независимый интерес, является обратимой выборкой (Определение 1 [20]). Предположим, что нам дают эффективный выборочный алгоритм . Можем ли мы всегда получать альтернативный эффективный выборочный алгоритм так, что выход не отличается от выхода , но может быть эффективно инвертирован в том смысле, что его случайность может быть эффективно вычислена, основываясь на его выходе? Здесь мы обратимся к дистрибутивному понятию инверсии, а именно, алгоритм инверсии является успешным, если пара вычислительно неразличима от пары , где - универсальный случайный вход для . Мы обращаемся к гипотезе, что каждый эффективный допускает эффективный , как и выше, как обратимая выборочная гипотеза (ISH). В то время как наше исследование ISH в основном мотивировано соответствием к адаптивной безопасности, этот вопрос независимо мотивирован другими криптографическими приложениям (такими как урегулирование отношения между шифрованием с открытым ключом и неочевидным обменом информацией); смотрите параграф 6 для более подробной информации.

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

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

Более точно мы показываем, что общее адаптивно безопасное вычисление подразумевает (и фактически, эквивалентно), более сильную версию ISH, в которой выборочные алгоритмы дают вход в дополнение к их случайному входу, и где алгоритм инверсии должен быть успешным на каждом входе . Эта более сильная разновидность ISH исключена указанными выше предположениями, а именно, существование извлекаемых односторонних функций и систем доказательства NIZK для NP. Чтобы исключить более слабую разновидность ISH (без входа ), мы вынуждены использовать несколько более сильных предположений: нестандартная (но все еще вероятная) разновидность извлекаемой односторонней функции, и существование неинтерактивных неразличимых от свидетеля протоколов (NIWI) для NP без общей ссылочной строки [21][22][23].

Наши методы

Теперь мы приведем некоторое восприятие на нашей конструкции эффективного выборочного алгоритма , для которого ISH не действует. Для этой цели удобно сначала описать релятивизированный мир (определяется с помощью рандомизированного оракула), в котором подобный доказуемо существует. В качестве первой попытки предположим, что у нас есть оракул, вычисляющий случайную функцию . Теперь, рассмотрим эффективный выборочный алгоритм , который выводит случайный образ , а именно,. (Отметим, что является эффективным данным доступом оракула к ). Аналогично предыдущему PRG примеру, такого алгоритма недостаточно, чтобы опровергнуть вычислительную версию ISH: действительно, альтернативный сэмплер может просто вывести равномерно случайную строку длины . Высокоуровневая идея для исключения подобного альтернативного сэмплера состоит в том, чтобы сделать выходы эффективно проверяемыми. Формально, мы добавляем к дополнительный оракул , который решает, является ли данная строка образом . (Подобный оракул был использован Wee [24] в, казалось бы, несвязанном контексте разделения двух понятий вычислительной энтропии).

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

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

Чтобы получить явную версию вышеуказанного , мы используем извлекаемые односторонние функции, чтобы реализовать и доказательство NIZK для того, чтобы доказать принадлежность множества, чтобы эмулировать роль (последний подобен использованию доказательств NIZK в [25] [26]; смотрите параграф 1.2). По техническим соображениям, которые имеют дело с общей ссылочной строкой, требуемой системой доказательства NIZK, мы не можем использовать этот подход, чтобы опровергнуть основную версию ISH, описанную выше. Для этого мы должны использовать несколько более сложных принципов доказательства и применять доказательства NIWI вместо доказательств NIZK. Смотрите параграф 4 для более подробной информации.

Связанная работа

Адаптивно безопасные MPC (без стираний) были впервые реализованы в [5] для автономного случая. В [17], разновидность понятия адаптивной безопасности, которая гарантирует последовательный состав, была представлена: мы обращаемся к разновидности из [17], которая требует безопасности против повреждения выполнения сообщения (PEC). А именно, после того, как моделирование выполнено, среда может попросить, чтобы противник повредил дополнительные стороны и промоделировал свои представления. Эта разновидность используется в [17], чтобы доказать последовательный состав. Фактически, разделение между адаптивной безопасностью с PEC и без него показано в [27]. Мы подчеркиваем, что отрицательные результаты из [27], применяют к определенным протоколам, а не к выполняемым функциям. Таким образом, [27] создает протоколы, которые показывают, что будучи адаптивно безопасными в одной ситуации, и не адаптивно безопасными в другой ситуации, но не показывают выполняемые функции, которые не могут быть реализованы с адаптивной безопасностью, по сравнению с нашим невероятным результатом.

В инфраструктуре защиты UC [7] основной допустимый результат для стойкого осуществления адаптивно правильно построенных выполняемых функций против адаптивного противника был получен в [6] (смотрите также [28][29]). Данная работа также предложила следующего приемлемого кандидата для рандомизированных выполняемых функций, которые не могут быть реализованы с адаптивной безопасностью: на входе параметр безопасности , на выходе произведение двух случайных простых чисел по -бит. Однако мы не знаем, как связать возможность реализации этой выполняемой функции с адаптивной безопасностью для любого хорошо изученного предположения.

Если кто-то готов предположить, что честные стороны могут надежно стереть свои данные, то безопасность против адаптивных противников становится намного более простой задачей. Наши отрицательные результаты не применяются к этой альтернативной модели, и общие допустимые результаты в этой модели были получены в [30][31].

Обратимая выборочная гипотеза связана с вопросами неочевидной выборки, которые были изучены в других криптографических контекстах. Например, вопрос генерирования открытого ключа для схемы шифрования без изучения того, как расшифровать, связан с целью построения протокола неочевидного обмена информацией из схемы шифрования с открытым ключом [32][33]; практически любая несовершенная схема шифрования [34][20][29][35] требует некоторого вида неочевидной выборки открытых ключей; в связи с недавним результатом [36] вопрос о том, содержится ли ISH, был неофициально задан, в контексте превращения UC-стойких протоколов в модель общей ссылочной строки до получестных стойких автономных протоколов. Если общая ссылочная строка является случайной строкой, то вопрос заведомо уменьшается до наличия одной стороны, которая публикует случайную строку. Если CRS выбирается вместо используемого некоторого общего распределения, то становится неясно, может ли получестная сторона выбрать общую ссылочную строку без изучения лазейки. Смотрите параграф 6 для дальнейшего обсуждения этих дополнительных связей ISH с криптографией.

Сведения в области экспоненциальных предположений были представлены в [11], и с тех пор другие конкретные сведения экспоненциальных предположений были предложены в [13][14], пока, в некоторой недавней работе [9][8][10] абстрактное понятие извлекаемых функций не было представлено. Наши невероятные результаты полагаются на предположения данного вида.

Использование предположений-сведений в доказательствах безопасности получило критику в криптографическом сообществе, особенно потому что такие предположения кажутся трудными для опровержения [37] (даже в [13] "неправильное" предположение сведений из [12] было опровергнуто). Насколько мы знаем, наша работа является первой, чтобы применять подобные предположения к отрицательным результатам в криптографии.

Наконец, наше использование доказательств NIZK и NIWI для NP было причиной использования NIZK в [38], чтобы создать класс обобщенных функций, где эффективное изучение со средством анализа возможно, но получение с генератором, который приближает данную обобщенную функцию, неосуществимо, и [24] [39] в контексте разделения условной HILL и Yao энтропии. Отметим, однако, что ни одна из этих работ не сделала использование предположений сведений; такие предположения, по всей видимости, крайне важны для наших методов.

Начальные сведения

Система обозначений. Мы используем в качестве параметра длины; все распределения вероятности, которые мы рассматриваем в данной работе будут заканчиваться строками многочлена длины . Через обозначим равномерное распределение над . Мы используем , чтобы обозначить процесс выборки из распределения . Если является множеством, то обозначает равномерный выбор из . Для любого распределения и алгоритма , мы обозначаем через распределение вероятности на выходах , принятого через подбрасывания монеты (если он существует) и независимый случайный выбор входа из .

Мы используем стандартную систему обозначений , чтобы обозначить распределение из , полученное в результате процесса выборки, задаваемой последовательностью команд . Например, обозначает распределение пар , полученное первым выбором из и затем получение , выполнив на . Аналогично мы используем , чтобы обозначить вероятность события в пространстве вероятностей, определенных последовательностью команд . Например, - это вероятность, при которой выбирается в зависимости от и независимо выбирается в зависимости от , и не равны.

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

По умолчанию мы предполагаем, что эффективные алгоритмы должны быть равномерно распределены, а эффективные отличительные признаки должны быть неравномерно распределены. Мы будем использовать , чтобы обозначить произвольную пренебрежимо малую функцию.

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

Алгоритмы выборки. Мы представим любое вероятностное полиномиальное время (PPT) алгоритма как определение эффективного выборочного алгоритма (или сэмплера, если кратко). Через обозначим выходное распределение на входе и через обозначим выход, когда случайный вход (то есть, последовательность бросков монеты) задается .Без потери универсальности мы можем связать с каждым эффективным многочлен так, что - случайный вход длины . В соответствии с этим правилом, распределен однозначно к . Мы будем использовать это правило на протяжении всей статьи. В конечном итоге, мы будем иногда интересоваться частным случаем сэмплеров по унарному входному алфавиту; в этом случае определяет последовательность распределений .

Мы считаем, что выборочный алгоритм является обратной выборкой, если существует PPT алгоритм инверсии, который, учитывая вход и выборку из выхода , выводит случайный вход для , который соответствует . Кроме того, выбор должен быть “правильно распределен” в том смысле, что должны быть вычислительно неразличимы от , где . (Такое распределительное требование инверсии аналогично определению распределительной односторонней функция [41].)

TemplateDifinitionIcon.svg Определение «Определение 1 (Обратимый выборочный алгоритм).»
Мы считаем, что эффективный выборочный алгоритм является обратимой выборкой, если существует PPT алгоритма инвертирующего элемента такой, что множества распределения и вычислительно неразличимы.

Обратимая выборочная гипотеза

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

Гипотеза 1 (обратимая выборочная гипотеза: ISH ). Для каждого эффективного выборочного алгоритма существует эффективный выборочный алгоритм , удовлетворяющий следующим двум требованиям.

  1. Близость: множества распределений и вычислительно неразличимы.
  2. Обратимость: является обратимой выборкой (смотрите определение 1)

Гипотеза 2 (Слабая ISH). Слабая ISH определяется также, как и ISH, описанная выше, за исключением того, что входы для и ограничены, чтобы быть унарными (т.е, являются формой ).

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

Мы начнем (в параграфе 4) с опровержения слабой ISH, полагая, что существование сильной разновидности извлекаемых односторонних функций, также как и систем доказательства NIWI для NP. Затем мы будем (в параграфе 5) опровергать исходную и более сильную разновидность ISH для более слабых предположений, что стандартные извлекаемые односторонние функции (обобщение различных “предположений знания экспоненты” из литературы) существуют, так же как протоколы NIZK для NP в CRS модели. На высоком уровне, опровержение более сильной разновидности ISH легче, потому что дополнительный "внешний" вход позволяет нам представить случайность, над которой альтернативный сэмплер не имеет никакого контроля. Эта случайность может быть использована для того, чтобы выбрать CRS для NIZK доказательства или случайные параметры для семейства извлекаемых односторонних функций.

Условное опровержение слабой ISH

Как уже обсуждалось во введении, любой псевдослучайный генератор обеспечивает нетривиальный пример выборочного алгоритма выборки, для которого действует слабая ISH. Действительно, если выводит , где , тогда может просто вывести , где .

Этот пример показывает, что в целях определения контрпримера для (слабой) ISH, не достаточно для вычисления, выполняемого сэмплером, чтобы быть односторонней и для обеспечения выхода, чтобы быть редким, но его выход должен также быть верифицированным (признак, отсутствующий в вышеуказанном примере). Забегая вперед, возможность проверки будет достигнута через разновидности неинтерактивного нулевого разглашения. Оказывается, что даже требование "редкости" должно быть значительно усилено, чтобы исключить возможность прямой выборки выхода, без знания соответствующего входа. Классы редких односторонних функций с подобным свойством были изучены в [11][13][14] под руководством “предположений знаний”. Грубо говоря, предположение знаний для функции утверждает, что если любой эффективный алгоритм выводит какую-то точку в образе , то единственный способ должен вычислить этот образ, выбирая и при вычислении (здесь необходимо, чтобы образ был редким). Таким образом, алгоритм "знает" . Это формально получено, требуя существование эффективного алгоритма, который может извлекать из входа и случайности .

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

Затем, мы формально докажем, что слабая ISH является ложной, при условии, что существование сильного понятия извлекаемой односторонней функции (EOWF) и при условии, что неинтерактивные доказательства неразличимости свидетеля (NIWI) существует для всех NP.

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

TemplateDifinitionIcon.svg Определение «Определение 2 (Извлекаемая односторонняя функция (EOWF)).»
Пусть является односторонней функцией. Мы говорим, что - извлекаемая односторонняя функция, если для каждого PPT алгоритма со временем выполнения есть PPT алгоритм экстрактора такой, что для каждого :
для некоторой пренебрежимо малой функции .

Отметим, что вышеприведенное определение кажется более сильным, чем подобные определения из литературы, в которых требуется, чтобы была единственной, явно заданной односторонней функцией, по сравнению с ключевым набором функций. В частности, EOWF, как и выше, не может быть реализована, используя конкретные предположения знаний из литературы, такие как те из [11][13][14]. Однако все еще кажется вероятным, что (разновидности с гибкой длиной) практические криптографические функции удовлетворяют вышеуказанному определению. В параграфе 5, мы будем полагаться на более стандартное понятие EOWF (которое позволяет зависеть от случайного ключа, и получает предыдущие предположения из литературы), чтобы опровергнуть сильную разновидность ISH.

Далее нам необходимо понятие неинтерактивной системы доказательства неразличимого свидетеля (NIWI) [42][22][23]. Доказательство NIWI используется, чтобы эффективно доказать, что вход находится в некотором NP-языке , не позволяя верификатору проводить различия между любыми двумя возможными свидетелями. В то время как последнее свойство неразличимости свидетеля более слабо, чем свойство нулевого разглашения NIZK, оказывается, что этого достаточно для наших целей. Важное преимущество доказательств NIWI состоит в том, что они могут быть реализованы (относительно более сильных предположений) без надежной общей ссылочной строки, которая по сути требуется для доказательств NIZK.

TemplateDifinitionIcon.svg Определение «Определение 3 (Неинтерактивная система доказательства неразличимого свидетеля [21][42][22]).»
Пусть является любым NP языком, и фиксированное отношение свидетеля для . Тогда называется неинтерактивной системой доказательства неразличимого свидетеля (NIWI) для , если и являются PPT алгоритмами и содержат следующие условия для некоторой пренебрежимо малой функции .
  1. Полнота. Для всех
  2. Корректность. Для всех , для всех строковых доказательств
  3. Неразличимость свидетеля (WI). Для каждой схемы полиномиального размера семейства , и каждого таких, что и ,

Доказательства NIWI существуют для всех NP для хорошо изученных предположений [21][42][22].

Мы теперь используем вышеуказанные два примитива, чтобы установить основной результат данного параграфа.

TemplateTheoremIcon.svg Теорема Теорема 1.
Если существует EOWF, и существуют NIWI доказательства для NP, то слабая ISH неверна.
Доказательство

Пусть является EOWF. Мы сначала определяем эффективный выборочный алгоритм , который выводит две случайные точки образа и также доказательство NIWI, в котором, по крайней мере, одна из точек правильно вычислена. Таким образом, выборочный алгоритм выбирает случайные и выводит , где является доказательством NIWI, в котором или или находятся в образе . Более конкретно, получается, выполняя средство проверки NIWI для соответствия NP, определенного тогда и только тогда, когда на входе и свидетель . Из слабой ISH, мы получаем обратимый альтернативный выборочный алгоритм и его инвертор . Благодаря свойству корректности из доказательства NIWI, мы (фактически) обеспечены тем, что альтернативный сэмплер выводит по крайней мере одну верную точку в образе . Но тогда мы можем создать новый алгоритм , который выполняет и выводит случайным образом один из двух образов .

Теперь является алгоритмом, который выводит (с существенной вероятностью) верные точки в образе . Учитывая, что - EOWF, там должен существовать также экстрактор , который при наличии случайного входа выводит так, что . Используя к обратимой выборке случайного входа и подавая его на , мы можем эффективно инвертировать , что противоречит его односторонности. За более подробной информацией обратитесь к полной версии.


Условное опровержение ISH

В этом параграфе мы опровергаем основную (сильную) разновидность ISH относительно более слабых и более стандартных предположений, чем те, которые использовались, чтобы опровергнуть слабую ISH.

Мы начинаем, определяя ослабленное понятие извлекаемой односторонней функции, которая является подобной понятию (в неинтерактивном режиме) извлекаемого множества семейства функций, предложенным Canetti и Dakdouk [8][9][10]. В отличие от предыдущего понятия из Определения 2, ослабленное понятие следует из предыдущего конкретного предположения знания в литературе, такого как предположение знания экспоненты Damg˚ard [11].

TemplateDifinitionIcon.svg Определение «Определение 4 (Множество семейств функций).»
Семейство функций, упорядоченное по пространству ключей , является множеством функций , в котором каждая функция имеет ту же область определения и диапазон. Множество семейств функций, , определяется как множество функций семейств с пространством ключей
TemplateDifinitionIcon.svg Определение «Определение 5 (Множество семейств односторонних функций).»
Множество семейств функций является односторонним если:
  • можно оценить (с учетом , , и области определения ) за время, полиномиальное в , и
  • для каждого схемы полиномиального размера семейства есть пренебрежимо малая функция такая, что для каждого , область определения
TemplateDifinitionIcon.svg Определение «Определение 6 (Множества семейств неинтерактивных извлекаемых односторонних функций [10]). »
Мы говорим, что множество семейств односторонних функций является неинтерактивно извлекаемым (без вспомогательной информации), если для любого эффективного выборочного алгоритма , выполненного за время (со случайным входом ), там существует PPT алгоритм и пренебрежимо малая функция такая, что для всех :

Различие между вышеуказанным понятием множеств семейств извлекаемых односторонних функций и понятием EOWF из Определения 2 является то, что извлечение не гарантируется для всех функций в функциональном семействе, и только для произвольно выбранных функций (конкретно, первый шаг выбирает случайную функцию). Кроме того, процесс выбора случайной функции может использовать частную случайность, которая не доступна алгоритму .

Вышеуказанное различие делает возможным получить множество семейства извлекаемых односторонних функций из существующих предположений знаний в литературе [11][12][13][14]. Как пример, предположение знание экспоненты (KEA) [11] неофициально утверждает, что там существует множество групп , где задачу дискретного логарифмирования трудно решить, и любой PPT противник , который на входе может вычислить пару вида , должен знать , в том смысле, что там существует эффективное устройство извлечения , которое с учетом случайного входа может вычислить . Накладывая этот пример на Определение 6, пространством ключей является и функция с определяется как

Затем, мы заменяем предыдущий NIWI примитив с неинтерактивным доказательством с нулевым разглашением (NIZK) в общей ссылочной строке (CRS) модели </ref>[15]</ref>[43]. Мы опустим (стандартное) определение NIZK, но отметим, что предположения, на которые системы доказательства NIZK для NP могут основываться, являются значительно более общими, чем соответствующие предположения для NIWI, и включают существование перестановок секретной информации </ref>[44].

Теперь мы готовы сформулировать основную теорему этого параграфа.

TemplateTheoremIcon.svg Теорема Теорема 2.
Если множества семейств неинтерактивных извлекаемых односторонних функций существуют и системы доказательства NIZK существуют для NP, то ISH является неверной.
Доказательство

Доказательство (план): доказательство придерживается той же самой схеме, как то из Теоремы 1, но использование NIZK вместо NIWI позволяет ему принимать несколько более простую форму.

Пусть является множеством семейства неинтерактивных извлекаемых односторонних функций. Мы сначала определим эффективный выборочный алгоритм , чьи входы являются парами строк является ключом из пространства ключей , и - равномерно случайная строка для использования в качестве CRS для системы доказательства NIZK. выводит случайный образ и доказательство NIZK (относительно ), у которого выход истинный. Пусть является обратимым альтернативным сэмплером, который предполагает ISH. Из-за корректности системы доказательства NIZK, выводит допустимые образы , когда выбирается равномерно случайным образом. Так как является извлекаемым, то мы можем использовать , его экстрактор и его инвертор , чтобы создать эффективный алгоритм инверсии для множества семейства , что противоречит его одностороннему свойству. За более подробной информацией обратитесь к полной версии.


Приложения ISH

Хотя наша основная мотивация для изучения ISH является ее отношением к адаптивно стойким MPC (описанных далее в Параграфе 7), мы начинаем с представления двух других следствий (слабой) ISH. Для того чтобы избежать неопределенности, мы напоминаем читателю, что в предыдущих параграфах мы опровергли ISH относительно некоторых определенных вычислительных предположений. Однако, поскольку мы не смогли опровергнуть ISH безоговорочно (или даже относительно стандартных криптографических предположений), все еще интересно изучать следствия ISH, чтобы поместить ISH в соответствующий криптографический контекст и далее обусловить наше исследование.

PKE и OT: В качестве первого следствия, отметим, что, если ISH выполняется, то будет установлен вопрос отношения между шифрованием с открытым ключом (PKE) и неочевидным обменом информацией (OT), как было изучено в [33].

TemplateTheoremIcon.svg Теорема Теорема 3.
Если ISH выполняется, то существование семантического стойкого PKE подразумевает существование протокола неочевидного обмена информацией.
Доказательство
Доказательство следует при рассмотрении протокола для аналогичного к EGL протоколу [32] , где получатель выбирает один открытый ключ с алгоритмом генерации ключей (таким образом, изучение секретного ключа), и другое использование альтернативного обратимого выборочного алгоритма, как описано в ISH. Безопасность получателя слабо следует из свойства близости ISH, в то время как безопасность отправителя может быть выведена из семантической безопасности PKE схемы. За более подробной информацией обратитесь к полной версии.


Предположения для UC-стойкого вычисления: систематическое изучение минимальной установки и вычислительные предположения для UC-стойких вычислений недавно были принятый в [36]. Вопрос, который авторы оставили открытым, состоит в том, является ли существование автономного неочевидного обмена информацией (SA-OT) необходимым предположением для UC-стойкого неочевидного обмена информацией (UC-OT) в модели общей ссылочной строки (CRS), где строка выбрана из произвольного распределения. Если ISH выполняется, то можно было ответить на этот вопрос утвердительно. Чтобы показать, что SA-OT является необходимым для UC-OT, мы покажем, как создать протокол для SA-OT, предполагая, что UC-OT в модели CRS существует. Интуитивно мы должны обработать CRS, чтобы выполнить работу протокола, но мы не хотим, чтобы никакая сторона изучила соответствующую лазейку. К сожалению, мы не можем позволить сторонам использовать MPC, чтобы обработать эту CRS, так как неограниченный условиями MPC невозможен, и мы не можем принять, что OT существует (или любое эквивалентное вычислительное предположение). Но если ISH выполняется, то есть способ выбрать любую CRS, не изучая лазейку при использовании обратимого сэмплера, после которого стороны могут выполнить UC-OT за счет этой CRS. Также отметим, что мы не нуждаемся в этой поддельной CRS, которая будет распределена точно также, как реальная CRS, но только вычислительно близко: если протокол UC-OT работает с реальной CRS но не с поддельной CRS, это может использоваться в качестве отличительного признака, таким образом, нарушая ISH. Стандартные методы сложности могут быть использованы, чтобы превратить этот протокол в протокол, стойкий против злонамеренного противника.

Адаптивная безопасность и ISH

В этом параграфе мы покажем, что наша сильная разновидность ISH (Гипотеза 1) тесно связана с протоколом конфиденциального вычисления с безопасностью против адаптивных противников (адаптивный MPC или AMPC, для краткости). Мы сначала покажем, что, если все рандомизированные выполняемые функции допускают протоколы AMPC, тогда ISH - верна. В соответствии с Теоремой 2, это дает первые убедительные доказательства, что общий AMPC невозможен. Затем, мы продолжаем, чтобы показать, что, если ISH - верна и все стороны взаимно связаны с OT-каналами[прим. 5], тогда общие AMPC возможен – таким образом, показывая, что ISH существенно эквивалентна основному AMPC.

Как обсуждалось во введении, наши результаты применяются к широкому диапазону AMPC моделей из литературы. Для удобства мы обратимся к двухсторонней получестной модели, в соответствии с определением [17], которая требует стойкости против повреждения выполнения сообщения (PEC). Последнее означает, что после того, как выполнение отработало, среда может попросить противника повредить дополнительные стороны. Требование PEC необходимо, чтобы доказать последовательный состав адаптивно стойких протоколов, и соответствует большинству других определений адаптивной безопасности из литературы (такая как адаптивная UC-безопасность). Наши отрицательные результаты не действует для адаптивно стойких протоколов без PEC (так как в получестном двухстороннем случае, безопасность в этой модели эквивалентна неадаптивной безопасности [27]).

Краткие предварительные сведения. Этот параграф является неофициальным введением в (адаптивно стойкие) MPC протоколы. В MPC протоколе адаптивная безопасность подразумевает, что враждебный объект может адаптивно выбрать стороны, которые он хочет повредить в любой точке в протоколе. Противник является получестным, если стороны, которые он повреждает, всегда следуют за предписанным протоколом. Его цель состоит в том, чтобы попытаться получить столько информации, насколько возможно при этом ограничении. Стойкость против подобных противников является основным требованием для любого криптографического протокола. Идеальная модель стойкости для MPC протоколов - та, в которой существует надежная третья сторона, которая (через безопасные частные каналы), получает все входы от участников протокола и отправляет назад их соответствующие выходы. Получестные противники в этой модели могут только изучить вход и выход сторон, которые он повреждает. Рассматривая это как основание для безопасности, в идеально-реальной модели [17], реальный мировой протокол для MPC является стойким, если для каждого противника в реальном выполнении, существует идеальный мировой противник (также известный как моделирующее устройство), так, что выходы и вычислительно неразличимы. Мы отправляем читателя к [17][31] для более точного определения этого понятия.

Адаптивно стойкий MPC обозначает ISH

Сначала мы показываем, что если AMPC протоколы существуют для каждой выполняемой функции , то ISH (Гипотеза 1) - верна.

TemplateTheoremIcon.svg Теорема Теорема 4.
Если для каждого PPT выполняемой функции существует протокол , который надежно реализует против адаптивного получестного противника (с PEC), тогда ISH – верна.
Доказательство

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

  1. Выход протокола и выполняемая функция являются вычислительно близки (потому что протокол корректен);
  2. Существует моделирующее устройство , которое может объяснить случайность используемых в , чтобы произвести выход , без доступа к выполняемой функции случайной ленты .
Поэтому, мы можем использовать протокол и моделирующее устройство как основу, чтобы построить обратимый выборочный алгоритм , которые удовлетворяют требованию ISH. Обратимый выборочный алгоритм может быть построен, моделируя выполнение протокола между и “в голове”, пока инвертор запустит моделирующее устройство как подпрограмму. За более подробной информацией обратитесь к полной версии.


ISH подразумевает адаптивно стойкий MPC

В предыдущем параграфе мы показали, что AMPC подразумевает ISH. Теперь мы покажем, что обратное тоже верно.

Чтобы получить результат более сильным, мы покажем, что ISH подразумевает самую сильную разновидность MPC, то есть, протокол конфиденциального вычисления против активного, адаптивного противника в универсально компонуемой инфраструктуре защиты (UC-AMPC). С учетом, что данное UC вычисление является невозможным в простой модели, мы смотрим на OT-гибридную модель, где возможно оценить адаптивно правильно построенные выполняемые функции[6], и мы показываем, как ISH позволяет нам расширять этот результат до всех выполняемых функций. Мы отправляем читателя к [7] для определения UC-AMPC. Мы смотрим на адаптивную безопасность, где противник может повредить любую из этих двух сторон в любой точке в течение протокола .

TemplateTheoremIcon.svg Теорема Теорема 5.
Если ISH выполняется, то активный стойкий UC-AMPC возможен для любой выполняемой функции в UC-OT гибридной модели.
Доказательство

Известно, что любая детерминированная выполняемая функция может быть надежно реализована в OT-гибридной модели [18][19]. Используя теорему состава UC и ISH мы расширяем результат для рандомизированных выполняемых функций.

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

Теперь определим новую, детерминированную выполняемую функцию как , где и где является альтернативным сэмплером для . Будучи детерминированной выполняемой функцией, может быть надежно реализована с адаптивной безопасностью в OT-гибридной модели.

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


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

  1. Technion and UCLA, E-mail: yuvali@cs.technion.ac.il
  2. UCLA, E-mail: {abishekk,sahai}@cs.ucla.edu
  3. Aarhus University, E-mail: claudio@cs.au.dk
  4. UCLA, E-mail: {abishekk,sahai}@cs.ucla.edu

Примечание

  1. Supported in part by ISF grant 1310/06, BSF grant 2008411, and NSF grants 0830803, 0716835, 0627781.
  2. This work was done while the author was visiting UCLA.
  3. Supported in part by NSF grants 0916574, 0830803, 0716389, and 0627781, an equipment grant from Intel, and an Okawa Foundation Research Grant.
  4. На первый взгляд, может показаться странным требование какой-либо безопасности, когда все стороны, участвующие в протоколе, в конечном итоге повреждены. Однако, важно, когда протоколы предназначаются, чтобы быть составленными (даже последовательно). Например, подпротокол большего протокола может включать только небольшое подмножество S из участников большего протокола. В такой ситуации, гарантируя безопасность большего протокола, когда (только) участники в S повреждены, может потребоваться анализ безопасности подпротокола, когда все участники подпротокола повреждены.
  5. Наше использование идеального OT может заменяться любым адаптивно безопасным OT протоколом, который может быть основан на стандартных криптографических предположениях.

Литература

  1. Yao, A.C.-C.: How to generate and exchange secrets, pp. 162–167 (1986)
  2. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority, pp. 218–229 (1987)
  3. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computation (extended abstract). In: STOC, pp. 1–10 (1988)
  4. Chaum, D., Cr´epeau, C., Damg˚ard, I.: Multiparty unconditionally secure protocols (extended abstract). In: STOC, pp. 11–19 (1988)
  5. 5,0 5,1 Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: STOC, pp. 639–648 (1996)
  6. 6,0 6,1 6,2 6,3 6,4 Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC, pp. 494–503 (2002)
  7. 7,0 7,1 7,2 Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: FOCS, pp. 136–145 (2001)
  8. 8,0 8,1 8,2 Canetti, R., Dakdouk, R.R.: Extractable perfectly one-way functions. In: Aceto, L., Damg˚ard, I., Goldberg, L.A., Halld´orsson, M.M., Ing´olfsd´ottir, A., Walukiewicz, I. (eds.) ICALP 2008, LNCS, vol. 5126, pp. 449–460. Springer, Heidelberg (2008)
  9. 9,0 9,1 9,2 Canetti, R., Dakdouk, R.R.: Towards a theory of extractable functions. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 595–613. Springer, Heidelberg (2009)
  10. 10,0 10,1 10,2 10,3 Dakdouk, R.R.: Theory and application of extractable functions (2009), http://cs-www.cs.yale.edu/homes/jf/Ronny-thesis.pdf
  11. 11,0 11,1 11,2 11,3 11,4 11,5 11,6 Damg˚ard, I.: Towards practical public key systems secure against chosen ciphertext attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445–456. Springer, Heidelberg (1992)
  12. 12,0 12,1 12,2 Hada, S., Tanaka, T.: A relationship between one-wayness and correlation intractability. In: Imai, H., Zheng, Y. (eds.) PKC 1999. LNCS, vol. 1560, pp. 82–96. Springer, Heidelberg (1999)
  13. 13,0 13,1 13,2 13,3 13,4 13,5 Bellare, M., Palacio, A.: The knowledge-of-exponent assumptions and 3-round zeroknowledge protocols. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 273–289. Springer, Heidelberg (2004)
  14. 14,0 14,1 14,2 14,3 14,4 Prabhakaran, M., Xue, R.: Statistically hiding sets. In: Fischlin, M. (ed.) CT-RSA 2009. M. Prabhakaran R. Xue, vol. 5473, pp. 100–116. Springer, Heidelberg (2009)
  15. 15,0 15,1 Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: STOC, pp. 103–112 (1988)
  16. Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084–1118 (1991)
  17. 17,0 17,1 17,2 17,3 17,4 17,5 17,6 17,7 Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptology 13(1), 143–202 (2000)
  18. 18,0 18,1 Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20–31 (1988)
  19. 19,0 19,1 Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer - efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008)
  20. 20,0 20,1 Damg˚ard, I., Nielsen, J.B.: Improved non-committing encryption schemes based on a general complexity assumption. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 432–450. Springer, Heidelberg (2000)
  21. 21,0 21,1 21,2 Dwork, C., Naor, M.: Zaps and their applications. SIAM J. Comput. 36(6), 1513–1543 (2007)
  22. 22,0 22,1 22,2 22,3 Groth, J., Ostrovsky, R., Sahai, A.: Non-interactive Zaps and new techniques for NIZK. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 97–111. Springer, Heidelberg (2006)
  23. 23,0 23,1 Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008)
  24. 24,0 24,1 Wee, H.: On pseudoentropy versus compressibility. In: IEEE Conference on Computational Complexity, pp. 29–41 (2004)
  25. Naor, M.: Evaluation may be easier than generation (extended abstract). In: STOC, pp. 74–83 (1996)
  26. Hsiao, C.-Y., Lu, C.-J., Reyzin, L.: Conditional computational entropy, or toward separating pseudoentropy from compressibility. In: Naor, M. (ed.)EUROCRYPT 2007. LNCS, vol. 4515, pp. 169–186. Springer, Heidelberg (2007)
  27. 27,0 27,1 27,2 27,3 Canetti, R., Damg˚ard, I., Dziembowski, S., Ishai, Y., Malkin, T.: Adaptive versus non-adaptive security of multi-party protocols. J. Cryptology 17(3), 153–207 (2004)
  28. Choi, S.G., Soled, D.D., Malkin, T., Wee, H.: Simple, black-box constructions of adaptively secure protocols. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 387–402. Springer, Heidelberg (2009)
  29. 29,0 29,1 Garay, J.A., Wichs, D., Zhou, H.-S.: Somewhat non-committing encryption and efficient adaptively secure oblivious transfer. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 505–523. Springer, Heidelberg (2009)
  30. Beaver, D., Haber, S.: Cryptographic protocols provably secure against dynamic adversaries. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 307–323. Springer, Heidelberg (1993)
  31. 31,0 31,1 Lindell, A.Y.: Adaptively secure two-party computation with erasures. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 117–132. Springer, Heidelberg (2009)
  32. 32,0 32,1 Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. ACM Commun. 28(6), 637–647 (1985)
  33. 33,0 33,1 Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: FOCS, pp. 325–335 (2000)
  34. Beaver, D.: Plug and play encryption. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 75–89. Springer, Heidelberg (1997)
  35. Choi, S.G., Dachman-Soled, D., Malkin, T., Wee, H.: Improved non-committing encryption with applications to adaptively secure protocols. In: Matsui, M. (ed.)ASIACRYPT 2009. LNCS, vol. 5912, pp. 287–302. Springer, Heidelberg (2009)
  36. 36,0 36,1 Damg˚ard, I., Nielsen, J.B., Orlandi, C.: On the necessary and sufficient assumptions for UC computation. In: Micciancio, D. (ed.) Theory of Cryptography. LNCS, vol. 5978, pp. 109–127. Springer, Heidelberg (2010)
  37. Naor, M.: On cryptographic assumptions and challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 96–109. Springer, Heidelberg (2003)
  38. Goldreich, O.: Foundations of cryptography: Basic applications. Cambridge Univ. Pr., Cambridge (2004)
  39. Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: FOCS, pp. 230–235 (1989)
  40. 42,0 42,1 42,2 Barak, B., Ong, S.J., Vadhan, S.P.: Derandomization in cryptography. SIAM J. Comput. 37(2), 380–400 (2007)
  41. De Santis, A., Micali, S., Persiano, G.: Non-interactive zero-knowledge proof sys- tems. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 52–72. Springer, Heidelberg (1988)
  42. Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In: FOCS, pp. 308–317 (1990)