Эффективные неинтерактивные безопасные вычисления

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 08:17, 22 декабря 2015.
Efficient Non-interactive Secure Computation
Towards a Game Theoretic View of Secure Computation.png
Авторы Yuval Ishai1 [@: 1] ,
Eyal Kushilevitz [@: 2] ,
Rafail Ostrovsky [@: 3]
Manoj Prabhakaran [@: 4]
Опубликован 2011 г.
Перевели Nikolay Morozov
Год перевода 2015 г.
Скачать Оригинал

__NUMBEREDHEADINGS__

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

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

Руководствуясь данным фактом, мы рассмотрим вопрос безопасных двусторонних вычислений в модели, позволяющей только параллельные вызовы алгоритма передачи (OT) без дополнительного взаимодействия. Получены следующие результаты.

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

Объединяя полученные результаты с параллельными OT протоколами (с 2 сообщениями) в CRS модели, мы получим первое решение для исходного вопроса мотивации, важного в случае использования черного ящика для стандартных криптографических примитивов.

Введение

Эта работа вызвана наличием следующих вариантов задачи вычисления зашифрованных данных [1] [2]. Предположим, что приемник хочет раскрыть семантически безопасное шифрование своего секретного входа x таким образом, чтобы любой отправитель , имеющий вход y, мог бы показать значение для , послав лишь одно сообщение. (Сообщение можно рассматривать как шифрование , которое получатель может расшифровывать). Мы хотим, чтобы в данном процессе безопасность y соблюдалась для вредоносных и, в то же время, предотвращалась возможность нечестного влияния на выход , сверх того, что разрешено . Мы будем называть подобные вычисления зашифрованных данных неинтерактивные безопасные вычисления (NISC).

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

Стандартные методы безопасных расчетов и вычислений для зашифрованных данных выполняются достаточно хорошо, когда стороны гарантированно полу-честны. Например, практические протоколы NISC в этой ситуации могут быть получены путем объединения схем Яо [3] [4] и любого OT протокола [5] [6]. Менее коммуникабельные (и менее практичные) решения могут быть получены с помощью однородного шифрования для общих функций [7] или для ограниченного класса функций [8] [9] [10] [11].

Для некоторых из перечисленных выше протоколов защита от вредоносных может потребовать относительно небольших затрат. В протоколах на основе построения Яо это может быть сделано (в CRS модели) с помощью эффективного UC-безопасного OT протокола [12] (см. также [13]). Тем не менее, известные методы защиты от вредоносных либо требуют дополнительных циклов взаимодействия [14], либо крайне неэффективны. Например, это так и есть, если требуется доказать, используя NIZK доказательство, что построен действующий искаженный цикл [5] [15]. Такие доказательства кажутся очень сложными, даже для наилучших из известных NIZK техник. Более того, даже с качественной точки зрения, такие NIZK решения оставляют желать лучшего, так как они по своей сути требуют, чтобы использовались основные криптографические примитивы, а черный ящик при этом не использовался. Например, в то время как полу-честный вариант протокола Яо может быть реализован при помощи черного ящика параллельного ОТ протокола двух сообщений и псевдослучайного генератора (PRG), этот случай не подходит для NIZK доказательств, безопасных относительно вредоносных отправителей.

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

Нашей основной мотивацией для рассмотрения этой модели для NISC является вышеупомянутое существование эффективной UC-безопасной версии ОТ протокола для двух сообщений в CRS модели. Действительно, используя теорему UC построения [16], NISC/OT протоколы могут быть так объединены с OT протоколами, что NISC протоколы в модели CRS будут иметь те же шаблоны связи, что и в начальном примере.

Дополнительными преимуществами OT протоколов являются возможность реализовать ОТ в различных моделях и при различных стандартных предположениях, а также преимущества по эффективности, такие, как возможность предварительного вычисления необходимых ОТ [17] [18] и возможность самортизировать затраты на эти предварительные вычисления [19] [20] [21]. См. [22] для дальнейшего обсуждения.

Перейдем к вопросу возможности минимизации допущений, на которых NISC/OT протоколы могут быть основаны. В гибридной OT модели, любая функция, вычислимая за полиномиальное время, может быть эффективно реализована безоговорочно [23] [21] [22]. Тем не менее, не ясно, справедливо ли то же самое для протоколов с постоянными циклами. (Этот вопрос связан с соответствующим вопросом для случая с честными MPC [24], который, в свою очередь связан с другими открытыми вопросами [25]). Учитывая отсутствие прогресса в этом направлении, второй лучшей альтернативой является создние NISC / OT протоколов на основе любой односторонней функции, что эквивалентно PRG генератору. Как было отмечено ранее, протокол Яо предоставляет такие решения в полу-честной модели. Более того, в работе [22] (см. Приложение B [26]) показано, как получить аналогичный протокол для вредоносной NISC/OT модели; однако, этот протокол, по своей сути, не использует черный ящик для PRG генератора. Это приводит к следующему основному вопросу:

Существуют ли NISC/OT протоколы для общих функций, которые используются только в качестве черного ящика для PRG?

Второй целью данной работы является сдвиг асимптотического предела эффективности протоколов черного ящика с постоянными циклами за счет минимизации количества запросов к основным криптографическим примитивам. Существующие протоколы в OT-гибридой модели (например, [27] [14] и их варианты) требуют запросов в PRG (или симметричном шифровании) для каждого цикла в цепи, где k является статистическим параметром безопасности, гарантирующим для вредоносных отправителей ошибку, не превышающую значения в для погрешности имитации. Это сравненимо с лучшими протоколами в полу-честной модели [3] [4], что требует только PRG запросов на цикл.

Наши результаты

Нами получены следующие основные результаты.

  • Технико-экономические. Мы представляем первый общий NISC / OT протокол, который, единственный в своем роде, применяет черный ящик при PRG. Все предыдущие протоколы в OT-гибридной модели либо осуществляются без черного ящика для криптографических примитивов [22], либо требуют нескольких стадий взаимодействия (см. [14]).
  • Эффективность. Мы также рассмотрим вопрос о минимизации асимптотического числа PRG вызовов, делаемых такими протоколами. Мы показываем, что вызовов достаточно для каждого цикла в (большой) булевой схеме, вычисляющей , где k является статистическим параметром безопасности, гарантирующим для вредоносных отправителей ошибку, не превышающую значения в для погрешности имитации. Кроме того, число PRG запросов на цикл можно сделать постоянным для менее строгого понятия безопасности, позволяющего вредоносным отправителям произвольно коррелировать со случаем, когда обнаруживает обман для входного . Это улучшает также интерактивные протоколы с черными ящиками, требующими PRG запросов на цикл, даже для упрощенного понятия безопасности.

Объединяя полученные результаты с (параллельными) OT протоколами с двумя сообщениями в CRS модели, мы получим первые решения вопроса исходного вопрос, который имеет место только для использования стандартных криптографических примитивов в качестве черных ящиков.

Повторное использование открытых ключей. Стандартным допущением для безопасности, которое относится ко многим неинтерактивным протоколам в модели с открытым ключом (см. [28][29][30][31]), будет то, что повторное использование открытого ключа приемника для нескольких сообщений отправителя сложно осуществить, если отправитель может узнать выход приемника для этого сообщения. На самом деле, стандартная UC-безопасность наших протоколов применяется только когда используются различные сообщения для получателей для каждой сессии. Хотя выход приемника не раскрывает дополнительной информации о входе приемника (кроме той, что разрешена ), может быть раскрыта информация о случайности, встроенной в открытый ключ, который в свою очередь может поставить под угрозу безопасность приемника при наличии утечки в многоканальных выходах без обновления открытого ключа. Наши протоколы действительно восприимчивы к такого рода атакам.

Мы подчеркиваем, что повторное использование одного и того же открытого ключа для нескольких сообщений отправителя всегда безопасно (в плане обеспечения "реально идеальной" гарантии безопасности), если приемник обновляет открытый ключ после выявления вывода или использования его в другом протоколе. Это, кажется, очень мягкие требования во многих практических ситуациях, в которых сообщения посылаются редко или могут быть объединены, прежде чем принимать какие-либо действия.

Аналогично [31], мы можем предоставить многоразовые открытые ключи (для которых до t выходов могут быть выявлены до ключевых потребностей в обновлении), что гораздо проще, чем публикация t независимых открытых ключей. Отметим, однако, что (не с черным ящиком) NIZК и NISC протоколы вообще не применимы к такого рода атакам, что оставляет вопрос о наличии возможности получения аналогичного результата за счет использования черного ящика открытым.

Асимптотическая и практическая эффективности. Как обычно в теоретических работах в области криптографии, мы акцентируем внимание на оптимизации асимптотической эффективности и не пытаемся оптимизировать или даже анализировать неочевидные стороны. Более того, мы сосредотачиваемся на типичных случаях, когда размер схемы гораздо больше, чем размер входа, а он, в свою очередь, значительно больше, чем параметр безопасности, а также иногда мы игнорируем младшие дополнения, которые зависят от меньших величин. Эти оптимизационные цели могут конфликтовать с практической эффективностью. Вопрос оптимизации NISC протоколов для практической реализации остается открытым для дальнейшей работы.

Обзор методов

На высоком уровне, наши NISC / OT протоколы получены с использованием следующих модульных действий:

  1. Статистически безопасный NISC / OT протокол для функций. Здесь мы можем рассчитывать на предыдущий протокол из [22] (см. приложение B [26]). Мы также представляем асимптотический способ повышения эффективности, применяя метод MPC, как в работе [32]. Это представлено в разделе 3.
  2. Вычислительно безопасные NISC протоколы для общих функций в гибридной модели (когда сторонам разрешено делать только один запрос для идеального функционала). Здесь мы объединяем реализацию искаженного построения схемы Яо с использованием безусловного одноразового MAC, чтобы гарантировать, что вредоносный отправитель может либо доставить правильный выход приемнику, либо приемник обнаруживает обман и останавливает протокол. Однако эти протоколы позволяют вредоносным отправителям коррелировать события приемника, прерывая вход приемника. Приведем два варианта протокола: первый (раздел 5) допускает произвольные корреляции со входами приемника, и является наиболее эффективным протоколом, полученным в данной работе. Второй вариант (раздел 6) немного менее эффективен, но позволяет только корреляции, которые могут быть выражены как дизъюнкции цепей и их отрицания.
  3. Наконец, мы представим (раздел 7) эффективное общее снижение полной безопасности до безопасности, "корреляционно прерванной". Идея состоит в преобразовании исходной схемы в новую, случайную цепь, в которой дизъюнкция цепей или их отрицание не дает никакой информации о входе. Особый случай этого преобразования подразумевается в [33]. Мы сводим общий случай к мажоритарно-честному MPC в полу-честной модели и применяем его, используя последние эффективные протоколы из [34].

Мы также вводим (в разделе 4) прямое специальное построение NISC протоколов в гибридной модели, которая является асимптотически менее эффективной, но в тоже время проще, чем те, которые были получены путем объединения шагов 2 и 3.

Предварительные сведения

Ниже мы определим неинтерактивную безопасную схему вычислений (NISC). NISC схемы могут включать в себя достоверные установки, идеальные реализации некоторых функционалов . Мы будем обозначать такие NISC схемы как .

схемой для функции является двусторонний протокол для приемника и отправителя, следующего формата:

  • Приемник получает как вход , а отправитель получает вход .
  • Обе стороны ссылаются на экземпляр , с входами по своему выбору, и приемник получает выходы из .
  • Отправитель может послать дополнительное сообщение для приемника.
  • Приемник выполняет локальные вычисления и выводит или сообщение об ошибке.

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

  • принимает от приемника и от отправителя, и выводит для получателя и пустой вывод для отправителя. Если - это специальная ошибка ввода error, тогда она же и выводится для получателя.

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

Мы определим упрощенное понятие безопасности, которое полезно в контексте NISC схемы, но может также иметь и более широкий интерес.

Безопасность при остановке, зависящей от входа. Учитывая SFE функционал , мы определим функционал , который ведет себя следующим образом: во-первых принимает описание предикат от противника (например, в виде PPT алгоритма); после получения входов для всех сторон, вычисляет выходы сторон также, как это делает F, но, прежде чем отправить выходы сторонам, запускает для всех входов, если выводит abort, то заменяет вывод для честных сторон сообщением abort. В противном случае передает выход от F всем сторонам.

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

Безопасность с цепочечной дизъюнкцией срабатывания отмены. Для двусторонних SFE функционалов F, выводящих только получателю, мы определяем функционал который является ограничением , в котором алгоритм для задания прерывания ограничивается следующим образом: включает в себя набор пар вида , где будет цепочкой в фиксированной схеме C вычисления функции , и только, если существует такая пара , что при оценке по , цепочка принимает значение . Мы также рассмотрим более строгое понятие цепочечной дизъюнкции, где дизъюнкция может включать только входные цепочки.

Протокол решения черного ящика при использовании PRG. Мы заинтересованы в NISC / OT схемах, которые не полагаются на криптографические предположения, кроме относящихся к безопасности PRG. Кроме того, схема должна быть в состоянии использовать любой PRG, представленный ему в черном ящике. Формально, мы применяем сокращение полного черного ящика [35] от NISC / OT к PRG.

На пути к более конкретному анализу эффективности, мы требуем, чтобы NISC / OT протоколы были безопасными и измеряем сложность как функцию от и для размера схемы . Безопасность для поврежденных отправителей носит статистический характер. Для достижения указанной цели в отношении вычислительно ограниченных поврежденных получателей, мы должны использовать PRG, для которого преимущества любого PPT противника в различении выхода PRG случайной строки (соответствующей длины) равны . С этой целью PRG может иметь больший вычислительный параметр безопасности, k, который определяет длину его узлов (k будет функцией κ, но для простоты мы обозначим его как отдельный параметр). PRG, рассмотренные ниже, имеют длину входа и выхода .

Эффективность: Криптографические расходы и расходы на связь. Наиболее известной NISC / OT Схемой, защищенной от пассивного искажения, является построение схемы Яо (См. ниже). Есть три аспекта, в которых схема может быть более затратной по сравнению с искаженной схемой (OT):

  • Сложность . Например, если является параллельным OT функционалом, то количество экземпляров ОТ и общая длина ОТ строк позволяет реально оценить сложность . (Заметим, что схемы осуществляют только одно исполнение ). Если является более активным функционалом, то мы заинтересованы в оценке сложности, связанной с безопасной реализацией .
  • Затраты на связь. Мы включаем здесь все затраты на коммуникацию между двумя сторонами и между сторонами и . Мы определяем затраты на связь для NISC схемы, как отношение совокупных связей в NISC схеме к полным связям в искаженной цепи (OT) схемы Яо.
  • Криптографические затраты. Искаженный контур схемы Яо использует черный ящик для PRG. Для оценки функции, которая вычисляется по схеме C, он использует запросы PRG (с входной и выходной длинами ). Соотношение между числом таких запросов в схеме NISC и в искаженной схеме Яо может быть определено как криптографические затраты для NISC схемы.

Искаженная цепочка. Существует два основных типа искаженной схемы построения Яо в литературе, один из которых соответствует оригинальному построению Яо [3] [4] и один соответствует представленному в [36] [37]. Первый тип подразумевает ничтожную вероятность ошибки при оценке цепочки (так как "неправильный" ключ может расшифровывать текст, зашифрованный с помощью другого ключа, не будучи обнаруженным), тогда как последний включает указатели с ключами, показывающими, каким зашифрованный текстам они предназначены. В этой работе мы следуем последнему варианту (с несколькими простыми изменениями). Ниже мы рассмотрим версию искаженной схемы, которую мы будем использовать.

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

  • Для каждой цепочки (с входными проводами и выходным проводом ), для всех , осуществляется шифрование

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

  • Для каждого входного провода , для которого значение фиксировано (то есть, w является входом, принадлежащим отправителю), пара , где это значение для входа.

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

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

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

(1)

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

Статистический NISC / OT протокол Статистический NISC / OT протокол N C 0   {\displaystyle NC^{0}~\,\!}

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

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

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

Предыдущие результаты. Статистически безопасный NISC / OT протокол для функции во вредоносной модели подразумевается в [39]. (При помощи известных сокращений, он может быть распространен на функции с низкими классами сложности, такими как с многомерной сложностью). Более эффективный протокол дается в [22] (см. Приложение B [26]). Протокол из [22] также может обладать вычислительной безопасностью для общих функций, но это требует отсутствия черного ящика для использования псевдослучайного генератора. С этого момента мы сосредоточимся на классе функций .

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

Обзор Новый протокол

Мы представляем другой подход к NISC / OT протоколам, что снижает затраты с и до . Наш общий подход работает для абсолютно безопасного MPC протокола во вредоносной модели. Повышение эффективности будет получено за счет подключения добавления идеально безопасного протокола из [34].

Учитывая функции g(а,b), где , наше построение имеет аналогичную структуру высшего уровня, как в [22] [26]:

  1. Сначала берется абсолютно безопасный NISC/OT протокол для в получестной модели, в которой получатель использует свой исходный вход в качестве последовательности OT выборов. Несколько таких протоколов с постоянным значением могут быть найдены в литературе (См. [38] и ссылки в ней).
  2. Используется алгоритм отправителя для определения "проверенного OT" функционала COT, который аналогичен методу параллельного OT за исключением того, что он проверяет, чтобы пары строк (вместе с дополнительным свидетелем), предоставленные отправителем, удовлетворяли данному согласованному предикату. Если это не проходит проверку, тогда специальные сообщения об ошибке передаются получателю. Конкретно, мы будем использовать ACOT функционал, в котором свидетель отправителя включает в себя входы и случайности, и предикат проверяет, чтобы пары строк соответствовали предписаниям протокола. (Для большей эффективности будет полезно включить в свидетеля значения промежуточных стадий при осуществлении расчетов для отправителя. Эта стандартная методика может использоваться для преобразования произвольных предикат в один из ).
  3. Берется абсолютно безопасный MPC протокол для многостороннего функционала, соответствующего СОТ, и он используется для получения статистически безопасного двустороннего NISC / OT протокола для СОТ. Это основной вклад в текущем разделе, который будет потом подробно описан ниже.
  4. Используется для получения NISC / OT протокола для с безопасностью в рамках вредоносной модели. Это можно сделать простым способом с помощью СОТ для модуляции , при обеспечение того, чтобы отправитель не отклонялся от предписанного алгоритма. Обратим внимание, что протокол не использует черный ящик для , и, таким образом, в нашем случае с черным ящиком мы не можем применить его к протоколам , использующим криптографические примитивы.

Упрощенная безопасность

Технические (стандартные) тонкости, которые мы должны осуществить, - это наша непосредственная реализация не реализовывала функционал COT при стандартных понятиях безопасности, но работала для упрощенного свойства безопасности, которое мы называем безопасностью с "прерывающей входной дизъюнкцией (IVD)". Это похоже на понятие безопасности с дизъюнкцией (WVD), рассматриваемой в разделе 6, за исключением того, что здесь дизъюнктивный предикат применяется только для входных значений. То есть, идеальный функционал увеличивается, позволяя вредоносным отправителям указывать дизъюнктивные предикаты для входных бит получателя (например, ), что приводит к передаче значения ко входу получателя, удовлетворяющему предикатам (В противном случае передается выход исходного функционала).

Стандартный метод для повышения безопасности при IVD прерывании до полной безопасности позволяет получателю овладеть "секретной долей" своего входа (см. [39] [14]). Конкретно, получатель кодирует в больший вход таким образом, чтобы гарантировать, чтобы каждый дизъюнктивный предикат в являлся либо подходящим с большой вероятностью, либо же совершенно не зависящим от . Исходные функционалы затем увеличиваются до функционалов , когда сначала декодируется исходный вход, а затем вычисляется . (Для предотвращения мошенничества вредоносным получателем, функция декодирования должна выводить действительный вход для любой строки ).

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

Наконец, мы предлагаем конкретный метод кодирования в , как было указано выше. Простой метод, предложенный в [39] [14] , позволяет быть дополнительным делением на на долей (для ). Этот способ имеет тот же недостаток, что и увеличение длины на значение , которого мы хотим избежать. Некоторые альтернативы были предложены в литературе (см., например, [40]), но они по-прежнему увеличивают длину входа на постоянный множитель и значительно увеличивает размеры схемы. Вместо этого мы предлагаем следующий метод кодирования. Пусть будет независимым генератором порядка . То есть, для случайного , биты являются независимыми. Затем, кодирование определяется как , где , это равномерные и случайные строки длины . Соответствующий дешифровщик определяется, как .

Следующая лемма очевидно справедлива.

TemplateTheoremIcon.svg Теорема Лемма 1
Для всех дизъюнктивных предикат имеет место следующее: # Если включает в себя не более, чем k литералов, тогда совершенно не зависит от . # В противном случае, .
Доказательство
Без доказательства.


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

Приведенное выше следствие показывает, что с асимптотической точки зрения, повышение безопасности с IVD прерыванием при полной безопасности приводит, в конечном счете, к свободе, как с точки зрения размера схемы, так и с точки зрения длины входа получателя.

TemplateTheoremIcon.svg Теорема Следствие 1
Пусть - функционал схемы размера и размером входа получателя . Тогда существует функция и такая линейно вычислимая функция кодирования , что:
  • Полностью безопасный протокол для может быть получен из любого протокола для , безопасного при IVD прерывании, за счет того, что стороны в запускают со входами и .
  • Размер схемы для равен .
  • Длина входа получателя в равна .
Доказательство
Без доказательства.


Реализация СОТ через надежный MPC

Остается описать эффективный протокол для COT, который будет безопасным при IVD прерывании. В этом разделе, мы сводим эту задачу к идеально надежному MPC при наличии честного большинства.

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

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

  1. Отправитель запускает MPC протокол "в уме" (как в работе [32]), где его вход ( пары строк и свидетель ) служат входами для отправителя в протоколе . Создаются строки с данными от серверов для данного исполнения, также как и с данными для получателей.
  2. Пусть будет таким целым числом, что . Отправитель и получатель осуществляют один параллельный вызов OT, в котором получатель выбирает для каждого вид , (где бит выбора будет COT входом получателя), также как и все виды для серверов с вероятностью .
  3. Получатель проверяет наличие противоречий между видами, которые он получает (а именно, для каждой пары , соответствующей игрокам , все сообщения от до , обработанные в должны согласовываться с тем, что вычисляет честный в на основе ). Если находятся такие несоответствия, или если любой из видов получателей имеет выход , тогда и получатель выводит выход , в противном случае получатель выдает выход для выбранных получателей.

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

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

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

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

Случай 2: . В этом случае симулятор COT передает виды MPC для отправителя и всех серверов в симулятору MPC. MPC симулятор выделяет эффективный вход отправителя (то есть, пар строк и свидетеля ). Если этот вход не удовлетворяет предикату , то выводится (при идеальной правильности для входов также всегда будет выводиться ). Остается рассмотреть случай, когда предикат неизменный. Для этого СОТ симулятор берет каждый сервер с вероятностью (как это делает честный получатель в ) , и, если существуют какие-либо несоответствия между множеством Т выбранных видов, тогда получатель выводит , в противном случае симулятор также сравнивает виды для каждого из получателей с каждым из серверов в T. Он подготавливает дизъюнктивный предикат , состоящий из литералов, соответствующих получателям, которые имеют хотя бы одно такое несоответствие (то есть предикат выполняется точно, если получатель выберет один из проблемных видов; в обоих случаях это приводит к выводу ). К функционалу передается вход, полученный симулятором вместе с предикатой .

В заключение подведем итоги по оценке сложности нашего построения и сравним его с работой [23, приложение B] (по существу, два построения несравнимы по большинству параметров).

TemplateTheoremIcon.svg Теорема Теорема 1
Приведенный выше протокол будет безопасным с IVD прерыванием при вычислении любой функции , где . Его затраты на связь равны . (Напомним, что ). Число OT запросов будет равно .
Доказательство
Без доказательства.


TemplateTheoremIcon.svg Теорема Теорема 2
[23] Существует безопасный протокол с IVD прерыванием при вычислении любой NC0 функции , где , для которого затраты на вычисления равны и количество OT запросов равно .
Доказательство
Без доказательства.


Прямой протокол для Прямой протокол для N I S C / N C 0   {\displaystyle NISC/NC^{0}~\,\!}

Наше первое построение следует подходу отсечения и выбора в духе предыдущих постоянных протоколов, имеющих черные ящики и доступ к криптографическим примитивам [34,32]. Затраты, которые мы несем на это сравнительно простое решение, равны с точки зрения криптографии. В частности, мы покажем следующее.

TemplateTheoremIcon.svg Теорема Теорема 3
Для любой функции с полиномиальной схемой и с входными циклами для первого входа, существует такой функционал с -разрядным выходом и разрядным входом получателя, что есть такая NISC / HC схема для , которая использует черный ящик для PRG, где PRG применяется раз, и с связями. (Напомним, что k является статистическим параметром безопасности, и значение можно вычислить).
Доказательство
Без доказательства.


Мы отложим доказательство этой теоремы до раздела 8, где представлен более общий результат (см. теорему 6).

Простой протокол с прерыванием, зависящим от входаПростой N I S C / N C 0   {\displaystyle NISC/NC^{0}~\,\!} протокол с прерыванием, зависящим от входа

В этом разделе мы приводим NISC схему для , которая позволяет использовать прерывание, зависящее от входа. Эта схема очень эффективна: затраты на коммуникацию уменьшаются для искаженного контура схемы до малого постоянного значения, а криптографические затраты равны 1 (даже позволяя PRG выводить длинные строки). Мы приведем сначала схему NISC / HC для функционала , а затем применим из результаты раздела 3, чтобы получить NISC / OT схему.

TemplateTheoremIcon.svg Теорема Теорема 4
Для любой функции , имеющей полиномиальную схему с входными цепочками для первого входа, существует такой функционал с -разрядным выходом и -разрядным входом для получателя, что существует схема для , которая дает черный ящик для PRG, запрашивая PRG протокол раз, и с полными затратами на коммуникации .
Доказательство
Подробное доказательство представлено в полной версии этой статьи. На верхнем уровне эта схема позволяет получателю проверить, чтобы с каждым помеченным битом, не открытым в искаженной схеме, делалось следующее: каждый помеченный бит отмечается с помощью MAC (ключом, предоставленным получателем). Однако, так как этот бит должен быть сохранен в тайне до того момента, как соответствующая запись в искаженной схеме будет расшифрована, то доля тега сохраняется зашифрованной с помеченным битом, а остальные доли передаются получателю. Отправитель, не знающий MAC ключа, может создать одну долю для расшифровки, а функционал берет MAC ключ от получателя, вычисляет MAC теги и передает оставшиеся доли получателю. Прерывание зависящее от входа можно получить, если отправитель может использовать только неправильные MAC для части входов, которые приводят к тому, что получатель останавливается в случаях, когда входы расшифрованы.


с дизъюнктивным прерыванием цепочекN I S C / N C 0   {\displaystyle NISC/NC^{0}~\,\!} с дизъюнктивным прерыванием цепочек

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

Данное построение включает в себя статистическую безопасность, одновременно MAC для -битных сообщений. Нам будет важно реализовать эту MAC схему c использованием цепочек. Это может быть сделано как в работе [21], если сообщение сначала соответствующим образом кодируется. Так как кодировка сам по себе не является функционалом, мы требуем, чтобы отправитель предоставил как кодирование, так и значения всех цепочек в схеме, которые вычисляются при кодировании. Затем схема может проверить это кодирование и параллельно создать MAC теги.

В полной версии статьи мы докажем следующую теорему.

TemplateTheoremIcon.svg Теорема Теорема 5
Для любой функции , имеющей полиномиальную схему с входными цепочками для первого входа, существует такой функционал с -разрядным выходом и -разрядным входом для получателя, что существует NISC / \mathcal{H}_C схема для , которая использует черный ящик для PRG, применяя PRG алгоритмы раз, и с полными затратами на коммуникации в .
Доказательство
Без доказательства.


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

От безопасности при WDT прерывании к полной безопасности

В этом разделе мы рассмотрим общие методы преобразования любой NISC схемы, удовлетворяющей требованиям безопасности с дизъюнктивным прерыванием цепочек (WDT) в NISC схему с полной безопасностью, основанные на полу-честных защищенных протоколах MPC. Наши преобразования обобщают подход, предложенный в работах [25,26] (и наши рассуждения очень схожи) в контексте построения схем с отслеживанием состояний, которые остаются закрытыми, даже если противник может подделать значения в цепочках. Отметим, что построению [25] также приходится иметь дело со множеством других вопросов, которые не появляются в нашем случае, что приводит к дополнительным сложностям. Наше решение может рассматриваться как упрощение их построения.

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

Наши преобразования осуществляются на основе новой кодировки, что мы определяем ниже. Детали этой реализации представлены в полной версии работы.

TemplateDifinitionIcon.svg Определение «Определение 1 (WDT устойчивое кодирование)»
Случайное множество цепочек вместе с эффективным множеством алгоритмов кодирования и эффективным множеством детерминированных алгоритмов декодирования будет WDT устойчивым кодированием схемы , принимающей два входа, если выполнены следующие свойства:
  • (Корректность). Для любых из домена , мы имеем

  • (Безопасность при вредоносных получателях). Существует такая случайная эффективная машина , что для любого из (но не обязательно в образе ) существует такой из домена для , что для любого при , принадлежащем домену , выходное распределение для совпадает с распределением .
  • (Безопасность при WDT-вредоносных отправителях). Для любого множества цепочек из и их отрицаний, пусть будет событием, подразумевающим, что дизъюнкция значений, определенных при входе из , равным , выполнена. Вероятностное пространство берется из множества , а случайности пользуются алгоритмом. Для любого такого и для всех , и таких , что и принадлежат домену , мы имеем:

NISC с открытым кодом

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

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

Формально PC-NISC схема для функции состоит из следующих четырех PPT алгоритмов.

  • Setup: берет только параметр безопасности в качестве входа и выводит пару строк . Эти строки предназначены двум участникам (получателю и отправителю, соответственно).
  • Encode: берет вход и задает строку , выводит строку , кодирующую (или, возможно, сообщение об ошибке, если выводится неправильно).
  • Compute: берет шифровку , вход и задает строку , выводит "закодированный выход" (или сообщение об ошибке, если выводится неправильно).
  • Decode: берет закодированный выход и задает строку , выводит (или сообщение об ошибке, если выход закодирован неправильно).

В идеале, в PC-NISC схеме одиночное кодирование может быть использовано получателем для осуществления сложных расчетов. Для определения безопасности PC-NISC схемы, ниже мы определяем функционал , который позволяет делать запросы прежде, чем вредоносный отправитель начнет работать.

  • принимает вход от получателя.
  • Тогда, в каждом исполнении берется вход от отправителя и выводится получателю (и пустые выводы отправителю). Если же будет специальной командой error, тогда выход получателя также будет error.
  • Существует граница для числа входов , берущихся из коррумпированных отправителей, когда правильность находится под угрозой. Более формально, коррумпированному отправителю можно добавлять команду , где –это произвольный РРТ алгоритм, и после таких исполнений, в каждом последующем таком исполнении выводит получателю.

Теперь, с учетом PC-NISC схемы рассмотрим двусторонний протокол модели, которая просто делает пару доступной для двух сторон) и в которой получатель для входа , посылает отправителю; каждому полученному входу отправитель посылает получателю, а получатель выводит . Мы говорим, что является безопасной PC-NISC схемой, если протокол является UC безопасной реализацией функционала .

Также нам интересны NISC схемы для , где .

Определение для . Цель PC-NISC состоит в том, чтобы избежать возможности наличия получателя, когда отправитель выполняет схему. Однако, по-прежнему можно применять такую схему в -гибридной модели, если функционал позволяет получателю отправлять вход, а затем выполнять несколько циклов независимого взаимодействия с отправителем, задавая отдельный выход получателю в каждом цикле. Мы будем использовать эти соображения в качестве промежуточного шага в достижении PC-NISC/OT и PC-NISC/CRS схем, которые могут быть указаны в простой модели (то есть, без связи с гибридными моделями) в рамках алгоритма Setup. В модели PC-NISC/CRS, алгоритм Setup задает в качестве случайно генерируемых строк, в соответствии с некоторым распределением вероятностей, определенным схемой.

В PC-NISC/OTvar модели, Setup выводит несколько коррелированных случайных величин: в каждом случае получатель имеет два случайных бита и отправитель получает такие случайные биты , что . Они могут быть легко использованы в PC-NISC схеме для оценки OT функции, в которой получатель имеет бит выбора , а отправитель имеет два входа и , и получатель имеет . Следовательно, NISC / OT схема для функции может быть легко преобразована в PC-NISC/OTvar схему для , если количество сессий равно алгоритмы Encode и Compute включают и ; кроме того, Decode будет включать в себя сообщение, переданное отправителем в NISC / OT схеме; Decode предполагает в первую очередь применение для получения результатов от OT алгоритма перед проведением локальных вычислений в NISC / OT схеме.

Главной задачей при построении PC-NISC схемы, кроме тех, что уже имели место при построении NISC схем, является возможность поддержки большого числа вычислений для кодировки тех же объемов.

Во-первых, заметим, что NISC / OT схема для функционала из раздела 3 может быть расширена до PC-NISC/Otvar с поддержкой и добавлением числа связей и криптографических сложностей. Это делается за счет увеличения числа серверов в основном MPC, используемом в этой схеме.

В полной версии работы мы доказываем возможность применения полученных результатов (что на самом деле просто расширяет теорему 3.)

{Теорема|Теорема 6|Для любой функции , имеющей полиномиальную схему с входными цепочками для первого входа, существует такой функционал с -разрядным выходом и -разрядным входом для получателя, поддерживающий вычислений, что существует схема для , которая использоует черный ящик для PRG, выполняя PRG раз, при общих коммуникациях .|Без доказательства. }}

Обратим внимание, что данная NISC схема применима к и может быть изменена в PCNISC схему для и исполнений, как описывалось ранее. Таким образом, с учетом этой схемы, мы можем объединить ее с PC-NISC/OTvar для (также описанным ранее), чтобы получить PC-NISC/Otvar для . Доказательство теоремы 6 приводиться в полной версии статьи.

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

  1. Dept. of Computer Science, Technion, Haifa, Israel, E-mail: [1]
  2. Dept. of Computer Science, Technion, Haifa, Israel, E-mail: [2]
  3. University of California, Los Angeles, E-mail: [3]
  4. University of Illinois, Urbana-Champaign, E-mail: [4]


Литература

  1. Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation (Workshop, Georgia Inst. Tech., Atlanta, Ga., 1977), pp. 169–179. Academic, New York (1978)
  2. Sander, T., Young, A., Yung, M.: Non-interactive cryptocomputing for NC1. In: FOCS, pp. 554–567 (1999)
  3. 3,0 3,1 3,2 Yao, A.C.-C.: How to generate and exchange secrets. In: Proc. 27th FOCS, pp. 162–167. IEEE, Los Alamitos (1986)
  4. 4,0 4,1 4,2 Lindell, Y., Pinkas, B.: A proof of yao’s protocol for secure two-party computation. Electronic Colloquium on Computational Complexity (ECCC) (063) (2004)
  5. 5,0 5,1 Cachin, C., Camenisch, J., Kilian, J.,M¨uller, J.: One-Round Secure Computation and Secure Autonomous Mobile Agents. In: Montanari, U., Rolim, J.D.P.,Welzl, E. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 512–523. Springer, Heidelberg (2000)
  6. Gentry, C., Halevi, S., Vaikuntanathan, V.: i-hop homomorphic encryption and rerandomizable yao circuits. In: Rabin, T. (ed.) CRYPTO2010. LNCS, vol. 6223, pp. 155–172. Springer, Heidelberg (2010)
  7. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169–178. ACM, New York (2009)
  8. Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF Formulas on Ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)
  9. Ishai, Y., Paskin, A.: Evaluating Branching Programs on Encrypted Data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575–594. Springer, Heidelberg (2007)
  10. Melchor, C.A., Gaborit, P., Herranz, J.: Additively homomorphic encryption with d-operand multiplications. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 138–154. Springer, Heidelberg (2010)
  11. Peikert, C., Vaikuntanathan, V., Waters, B.: A Framework for Efficient and Composable Oblivious Transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008)
  12. Damg°ard, I., Nielsen, J.B., Orlandi, C.: Essentially Optimal Universally Composable Oblivious Transfer. In: Lee, P.J., Cheon, J.H. (eds.) ICISC 2008. LNCS, vol. 5461, pp. 318–335. Springer, Heidelberg (2009)
  13. 14,0 14,1 14,2 14,3 14,4 Lindell, Y., Pinkas, B.: An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)
  14. Horvitz, O., Katz, J.: Universally-Composable Two-Party Computation in Two Rounds. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 111–129. Springer, Heidelberg (2007)
  15. Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. Electronic Colloquium on Computational Complexity (ECCC) TR01-016 (2001), Previous version “A unified framework for analyzing security of protocols” availabe at the ECCC archive TR01-016. Extended abstract in FOCS 2001 (2001)
  16. Beaver, D., Goldwasser, S.: Multiparty computation with faulty majority. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 589–590. Springer, Heidelberg (1990)
  17. Beaver, D.: Precomputing Oblivious Transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97–109. Springer, Heidelberg (1995)
  18. Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: Proc. 28th STOC, pp. 479–488. ACM, New York (1996)
  19. Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA, pp. 448–457 (2001)
  20. 21,0 21,1 Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending Oblivious Transfers Efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003)
  21. 22,0 22,1 22,2 22,3 22,4 22,5 22,6 22,7 22,8 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)
  22. Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: ACM (ed.) Proc.19th STOC, pp. 218–229. ACM, New York (1987), See [15, ch. 7] for more details
  23. Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: STOC, pp. 503–513. ACM, New York (1990)
  24. Ishai, Y., Kushilevitz, E.: On the Hardness of Information-Theoretic Multiparty Computation. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 439–455. Springer, Heidelberg (2004)
  25. 26,0 26,1 26,2 26,3 Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer - efficiently, Preliminary full version on http://www.cs.uiuc.edu/˜mmp/
  26. Mohassel, P., Franklin, M.K.: Efficiency tradeoffs for malicious two-party computation. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 458– 473. Springer, Heidelberg (2006)
  27. Kilian, J., Micali, S., Ostrovsky, R.: Minimum resource zero-knowledge proofs (extended abstract). In: FOCS, pp. 474–479. IEEE, Los Alamitos (1989)
  28. Kalai, Y.T., Raz, R.: Succinct non-interactive zero-knowledge proofs with preprocessing for logsnp. In: FOCS, pp. 355–366. IEEE, Los Alamitos (2006)
  29. Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010)
  30. 31,0 31,1 Chung, K.-M., Kalai, Y., Vadhan, S.P.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010)
  31. 32,0 32,1 32,2 Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: STOC, pp. 21–30. ACM, New York (2007)
  32. Ishai, Y., Prabhakaran, M., Sahai, A., Wagner, D.: Private Circuits II: Keeping Secrets in Tamperable Circuits. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 308–327. Springer, Heidelberg (2006)
  33. 34,0 34,1 34,2 Damg°ard, I., Ishai, Y., Krøigaard, M.: Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 445–465. Springer, Heidelberg (2010)
  34. Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of Reducibility between Cryptographic Primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004)
  35. Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: ACM Conference on Electronic Commerce, pp. 129–139 (1999)
  36. 37,0 37,1 Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. In: IEEE Conference on Computational Complexity, pp. 260–274. IEEE Computer Society, Los Alamitos (2005)
  37. 38,0 38,1 Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: STOC, pp. 433–442. ACM, New York (2008)
  38. 39,0 39,1 39,2 Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20–31. ACM, New York (1988)
  39. Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure Two-Party Computation Is Practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009)
  40. Mossel, E., Shpilka, A., Trevisan, L.: On epsilon-biased generators in nc0. Random Struct. Algorithms 29(1), 56–81 (2006)