О целесообразности последовательных вычислений

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 12:00, 5 декабря 2015.
On the Feasibility of Consistent Computations
On the Feasibility of Consistent Сomputations.png
Авторы Sven Laur[@: 1] и
Helger Lipmaa[@: 2][@: 3]
Опубликован 2010 г.
Сайт Public Key Cryptography 2010
Перевели Николай Кудрявцев
Год перевода 2015 г.
Скачать оригинал


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

Введение

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

Таблица 1. Сравнение различных задач безопасности во вредоносной модели

Цель Конфиденциальность на входе Конфиденциальность на выходе Обработка жалоб Возможность обнаружения
Многосторонние протоколы
Безопасность
Последовательность
К-утечка
Скрытая модель
Конфиденциальность
Да
Возможны утечки
Возможны утечки
Нет
Нет
Да
Возможны утечки
Возможны утечки
Нет
Нет
Безопасно
Возможно
Возможно
Невозможно
Невозможно
Необязательно
Необязательно
Нет
Частично
Нет
Двухсторонние протоколы
Безопасность
Последовательность
К-утечка
Скрытая модель
Конфиденциальность
Да
Да
Возможны утечки
Нет
Нет
Да
Да
Возможны утечки
Нет
Нет
Безопасно
Возможно
Возможно
Невозможно
Невозможно
Да
Да
Нет
Да
Нет

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

Наш вклад. Главным нашим вкладом является новая модель безопасности, дающая более строгие гарантии соответствия полублагонамеренной модели, всем типам скрытых моделей[2] и модели К-утечки[3], как в таблице 1.
Мы также представляем реальные эффективные протоколы для согласующейся адаптивной забывчивой передачи и согласующегося условного раскрытия тайн. Особенным является то, что все наши конструкции являются более эффективными, чем их полностью защищённые аналоги. Например, новая согласующаяся забывчивая передача защищена от неограниченных вредоносных клиентов, используя по 2 сообщения за запрос, и имеет канал передачи и вычислительную мощность, сопоставимую с основным протоколом защищённой забывчивой передачи. В качестве главного технического средства мы используем списочные схемы передачи, позволяющие передавать список элементов так, что получая короткий сертификат, они могут позже подтвердить значение одного из элементов списка. Кроме стандартных протоколов скрытия и связки свойств нам нужны также двусмысленность и добываемость. Посмотрите секцию 3 для подробностей и конструкция.

Обозначения. В данном документе «» означает параметр защиты, – сокращение для неодинаковых врагов. Сокращение означает, что может быть задано полиномом. Сокращение означает, что асимптотически убывает быстрее, чем любой обратный полином.
Полная версия и история. Полная версия документа может быть найдена здесь[4]. Первая версия этого электронного издания от марта 2006 уже определяет совместимость (хотя и под другим названием). Система аргумента из двух сообщений из[5] была создана под действием первой версии электронного издания.

Определение последовательных вычислений

Получение защиты от злоумышленников обычно предполагает большое количество вычислений, так как должен действовать универсальный механизм обнаружения мошенничества такой, что обычные пользователи могли бы обнаружить мошенничество даже если оно не оказывает влияния на их выходные данные. Возможным компромиссом между эффективностью и защитой может являться защита пользователей только от тех действий, которые затрагивают их данные. В результате злоумышленники всё еще могут вызвать выборочные сбои протоколов, при которых действия обычных пользователей не выполняются, если их входные данные находятся в определённом диапазоне. Мы используем сравнение идеала и реалий для формализации концепта совместимых вычислений для различных протоколов. Заметим, что мы используем стандартны определения[6] [7] с изменёнными идеализированными реализациями, дающими дополнительные возможности злоумышленнику, как изображено на рисунке 1.
Для краткости и точности мы представляем понятия без углубления в излишние детали. К примеру, мы опускаем все низкоуровневые детали идеальных и реальных исполнений, так как они тщательно обсуждаются в справочных материалах[6] [7]. Другие конкретные детали обсуждаются отдельно в конце секции.


Рис.1. Идеальная модель для совместных двусторонних вычислений. Злоумышленник P2 может вызвать остановку передачи выборочных данных, изменив предикат . В стандартной модели доминирующая сторона может вызвать общую остановку передачи данных, если в ней непосредственно участвует несколько сторон.

Идеализированные реализации. В идеализированном двустороннем протоколе, связанном с совместным вычислением, обе стороны посылают входные данные третьему доверенному источнику TTP, а он рассчитывает выходные данные . Далее участник-злоумышленник посылает случайное описание о сбоях третьей стороне (TTР), которая производит внутренние вычисления . При условии третья сторона(TTP) прекращает вычисления и посылает добросовестному участнику. При условии третья сторона (TTP) высылает выходные данные в точности так же, как при стандартной идеализированной модели. При этом злоумышленник все еще может вызвать прекращение передачи данных, и получить выходные данные.
Однако, эти весьма спорные аспекты связаны с добросовестностью и возможностью обнаружения. Протокол гарантирует добросовестную избирательную остановку, если злоумышленник может изменить только единый предикат , так как третья сторона (TTP) приостанавливает вычисления и посылает всем участникам, если . В иных случаях злоумышленные стороны могут по-отдельности изменить разные предикаты с перебоями каждой стороне , из-за чего одни участники могут получить выходные данные, а другие – нет. Заметим, что разоблачить участников сговора не всегда возможно при многосторонних протоколах, тогда как в двусторонних протоколах это получается всегда. Совместный протокол обеспечивает обнаружение, если третья сторона (TTP) посылает для вместе с данными о злоумышленнике, который изменил остановочный предикат, и при условии, что .
Последовательность также может быть формализована для адаптивных вычислений, если выходные данные каждого раунда могут зависеть от входных данных, введенных в прошлых раундах. Если говорить вкратце, мы определяем совместимость только для протоколов «клиент-сервер», где сервер изначально фиксирует клиентские входные данные, а клиент затем сам решает вопросы забывчивой передачи. Эта модель часто применяется на практике, например, при продаже электронных товаров или при управлении частного процесса логического вывода[8] [1]. Чтобы запустить такой протокол, сервер посылает клиентские данные третьей стороне TTP. После этого клиент(ы) могут послать различные запросы третьей стороне TTP. Когда запрос получен, третья сторона ТТР посылает в сервер сообщение с уведомлением, и последний может сгенерировать описание остановочного предиката . Далее третья сторона TTP оценивает предикат и посылает обратно клиенту, если , в противном случае клиент получает . Отметим одну немаловажную деталь: способность рассматривать остановочные предикаты один за другим необходима только в адаптивной модели «скрытых врагов», где есть несколько участников, и сервер моет быть взломан в ходе вычислений.


Определение формальной безопасности. Как правило, безопасность протокола определяется сравнением распределения выходных данных в автономном режиме и распределением данных в идеализированной реализации. Грубо говоря, фиксируя параметр защиты и позволяя распределить входные данные всех сторон, включая злоумышленника . W.l.o.g., мы приходим к выводу, что каждый блок входных данных – это пара , где вспомогательный блок данных моделирует внутренние состояние участника перед запуском протокола, а – это реально введенные в протокол данные. Теперь, если мы зафиксируем конкретные детали так, как предписано протоколом и требует того уровень защиты, протокол и злоумышленник вместе будут контролировать только общее распределение выходных данных всех участников, включая . При этом определяет общее распределение общих выходных данных, определяемых злоумышленником в идеализированной реализации, и соответствующая идеализированная реализация . Мы имеем в виду, что семейство протоколов надежно внедряет , если для любого нестандартизированного полиномного злоумышленника существует нестандартизированный полиномный злоумышленник adversary , такой как при любом семействе распределения входных данных , распределение выходных данных и нельзя различить вычислениями. Если распределения выходных данных не могут быть различены вычислениями или совпадают, можно говорить о статистической или идеальной безопасности. В результате семейство протоколов корректно внедряет , если в любом семействе распределение входных данных и распределения выходных данных совпадают при условии, что злоумышленники не активны (не наносят никому вреда) в обеих реализациях.


Базовые характеристики. Заметим, что единственное различие между формальными определениями последовательности и безопасностью во вредоносных моделях – это описание реализации идеализированной среды. Таким образом. Мы можем считать последовательный протокол безопасной реализацией модифицированных функций, что позволяет четко задать характеристики остановочных предикатов. В результате, результаты стандартной сочетаемости сохраняются, и каждый последовательный протокол в последовательной композиции может быть заменен на идеализированная реализация. Однако, получившийся гибридный протокол необязательно совпадает с последовательной реализацией идеализированной среды. Например, если мы выполним два протокола «клиент-сервер» один за другим, входные данные сервера не обязательно будут одинаковы в обеих реализациях. Кроме того, вредоносный сервер может определить два остановочных процесса вместо одного.
Главное преимущество последовательных вычислений перед более слабыми моделями защиты – это гарантия внешней правильности данных. При построении идеализированной модели последовательных вычислений добросовестный участник достигает поглощающего состояния, если его/ее выходные данные согласуются с входными данными, используемыми в начале протокола. Таким образом, успешное выполнение протокола гарантирует корректность и в идеализированной реализации. Следовательно, добросовестный участник может доказать, что было совершено злонамеренное действие, без помощи других участников. Кроме того, любой последовательный протокол может быть дополнен механизмом обработки жалоб, который раскрывает только суть жалобы.

TemplateTheoremIcon.svg Теорема Теорема 1
Допустим, что семейство протоколов корректно, и осуществление функциональности последовательно, т.е. все сообщения подписываются их создателями. Тогда добросовестный участник может доказать совершение злонамеренного действия по отношению к нему (изменение его выходных данных) без помощи других участников в случае, если система подписи сообщений безопасна. Такой аргумент превращается в метод доказательства без раскрытия секретной информации, если в сообщениях, полученные добросовестным участником, ничего не говорится о его входных данных.
Доказательство
Схематично. Для обоснования отметим, что из соображений безопасности ни один участник не может подделывать сообщения, посылаемые другими участниками. Следовательно, если добросовестный участник раскрывает входные данные и случайность вместе со всеми полученными сообщениями, любой участник может проверить корректнсть его/ее вычислений. Поскольку протокол правильно выполнен , недобросовестные участники не могут сконфигурировать недопустимые выходные данные. Этот аргумент превращается в метод доказательства без раскрытия секретной информации, поскольку его достаточно, чтобы предоставить все полученные сообщения и доказать, что есть правильные входные данные и произвольность, которая ведет к недопустимому состоянию. Соответствующее положение представлено на языке класса NP, и потому представляет собой доказательство без раскрытия секретной информации. Можно утверждать, что сообщения доказательства не раскрывают никакой информации о входных данных участника.

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

Связь с другими аспектами безопасности. Понятие «скрытого врага» было введено давно и обсуждалось во многих контекстах. Первые определения относились к многосторонней среде [9] [10], и только недавно оно было изменено для работы в двусторонней среде Оманном и Линделлом [2]. В частности, определение t-распознаваемости, представленное в [9] и различные определения - распознаваемости, данные в источнике [2], гарантируют высокую степень вероятности обнаружения злонамеренного поведения, меняющего выходные данные добросовестных пользователей. Однако, ни одно из этих определений не ограничивает количество информации, получаемое при попытке совершения жульничества. Таким образом, наше определение совместных вычислений – компонент, усиливающий эти определения, что гарантирует безопасность входных данных. Другой термин, связанный с безопасностью – это модель -утечки[3], где злоумышленник может получить до битов дополнительной информации о входных данных добросовестных пользователей. Как и в последовательных вычислениях, злоумышленник не может изменить выходные данные, не будучи разоблачённым. Однако, в отличие от совместных вычисления, информация гарантированно попадает в руки мошенника, и его атака не распознается. Таким образом, модель -утечки данных дает меньше гарантии сохранения безопасности. См. сводную информацию в Таблице 1.

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

Схемы обязательств для списков

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

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

  1. Ответчик генерирует и отсылает к .
  2. генерирует обязательство и два сертификата и .
  3. выигрывает, если обязательство открыто для разных значений .

Таким образом, местоположения совпадают , но для открытия и .

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

  1. Ответчик генерирует и отсылает к .
  2. посылает два списка с ответчику.
  3. Ответчик генерирует случайный бит , вычисляет и посылает значение обязательства .
  4. В следующей фазе может сделать несколько запросов для в случае, если для любого запрашиваемого индекса .
  5. выигрывает, если он\она правильно отгадывает значение бита .


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

Нормальное исполнение:

  1. Ответчик генерирует и отсылает к .
  2. посылает оракулу , который вычисляет и отвечает .

Симулированное исполнение:

  1. Ответчик генерирует и отсылает к .
  2. Оракул вычисляет и при условии, что от , вычисляет и отвечает .

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

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

  1. Ответчик генерирует и новую случайную ленту .
  2. получает и в качестве входных данных и как случайную ленту и выводит транзакцию списка вместе с размером .
  3. получает и в качестве входных данных и выводит .
  4. При получении данных выводит сертификаты .
  5. Злоумышленник выигрывает, если выводит как минимум один сертификат, нерасходящийся с транзакцией и отвечающий элементу списка, неправильно отгаданному тем, кто извлекает, т.е. если .

На данный момент неизвестно, как конструировать не интерактивную избыточную схему фиксации, которая могла бы быть извлечена с безымянного компьютера. [16]Однако, если рассматривать интерактивные схемы фиксации, где отправитель использует доказательство без раскрытия секретной информации и знает, как открыть все элементы из фиксированного списка, мы смогли бы воссоздать устройство извлечения информации по определению. Используя подходящие техники доказательства без раскрытия секретной информации, как показано в[17], вся коммуникация между получателем и отправителем может стать сублинейной, хотя дополнительные расчеты могут быть слишком громоздкими для практического применения.
Поскольку безопасность доказательства информации часто считается слабой моделью [18], мы считает иные определения совместимыми. Схему обязательства для списков можно считать слабо приспособленной для извлечения с безымянного компьютера, если для полиномиально-временного злоумышленника и границы погрешности , существует извлекающее устройство , т.е. для любого распределения входных данных и для любого семейства дополнительных последовательностей , злоумышленник выигрывает в «борьбе» за извлечение данных с вероятностью до и временем счета в раз медленнее, чем .[16]

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

TemplateTheoremIcon.svg Теорема Теорема 2
Допустим, что – это привязочная схема обязательств, а – обычная схема обязательств. Тогда приобретает статистическую скрытность, т.е. идеальную скрытность; вычисляемая привязка; статистическая двузначность и идеальная двузначность .
Доказательство
Скрытность и привязка очевидны. При рассмотрении двузначности отметим, что данный ключ двузначности для , возможно использовать для генерации списка фальшивых обязательств для низшего уровня, который позже может быть открыт для любых значений, используя функцию .


Схема обязательств для списка не обязательно должна быть скрыта. Таким образом, мы можем использовать древовидную схему случайных данных, чтобы сжать большие списки до кратких хэш-сумм. Соответствующий тип конструирования основан на бесконфликтном семействе хэш-функций и длине сертификатов, размером . Схема обязательства Pedersen [19] – это отличный вариант традиционной схемы обязательства, поскольку является идеально двузначной в последовательности исходных значений для расчётов CRS, и его можно просто настроить для стандартной модели. Точнее, общедоступный параметр – это обычно выбираемый элемент группы , и соответствующий двузначный путь обхода системы защиты является дискретным логарифмом . В качестве первого варианта параметры могут быть сгенерированы отправителем и получателем вместе с использованием безопасного тройного мультипликационного протокола, чтобы умножить два случайных элемента. В качестве альтернативного варианта клиент может настроить , так как система обязательства Pedersen скрыта. Но тогда мы лишимся двузначности, пока не захотим найти дискретный логарифм в экспоненциальном времени.

Последовательная настраиваемая «забывчивая передача»

Протоколы «забывчивой передачи» часто используются как своеобразные строительные блоки для создания комплексных протоколов. В протоколе последовательной настраиваемой забывчивой передачи сервер имеет базу входных данных -битных последовательностей, и клиент может запрашивать до элементов из данной базы данных. Клиенту доступны только данные в рамках а на сервер не должно поступать никакой информации из базы.

Протокол 1: Новый протокол последовательной настраиваемой «забывчивой передачи»

Входные данные клиента: самостоятельно выбранные лучшим образом индексы .
Входные данные сервера: база данных .
Общие входные данные: описание и .

Защищенные настройки
При необходимости доверенный распространитель частично выстраивает настройки для . Доверенный распространитель распределяет общедоступные параметры между всеми участниками.
Фаза фиксации
Сервер вычисляет и отправляет транзакцию клиенту. Затем сервер вычисляет для каждого и хранит базу данных частичных значений дефиксации .
Фаза запроса. Чтобы извлечь -ный элемент из базы данных:

  1. Клиент посылает запрос на сервер.
  2. Сервер возвращает ответ .
  3. Клиент рассчитывает и . Если , то клиент выводит , в противном случае он выводит .

В частности клиент может запросить, если его запрос не подпадает в рамки . В асимптотических настройках все параметры должны быть полиномиальными в параметре безопасности . Два ключевых определения в протоколе последовательной настраиваемой «забывчивой передачи» - это безопасность и конфиденциальность. Протокол конфиденциального обмена может гарантировать лишь, что злоумышленник не сможет получить информацию за рамками но не гарантирует, что добросовестный участник получит информацию , если сам сервер поражен вредоносным ПО. Поэтому такие протоколы не подходят для практического применения.
В большинстве безопасных для вредоносных моделей протоколов настраиваемой «забывчивой передачи» сервер сначала обрабатывает индивидуальные элементы базы данных, а затем помогает клиенту «расшифровать» отдельные элементы, см. пример в[20][21]. Обычная альтернатива – использовать схему обязательства с сублинейной последовательностью вместе с техниками доказательства без раскрытия секретной информации, как показано в [17]. Однако получившийся в результате протокол с низким уровнем передачи – это только теоретическое решение со слишком громоздкими дополнительными вычислениями, что не подходит для практической реализации.
В качестве практического решения мы покажем, как конвертировать любой конфиденциальный протокол «забывчивой передачи» в последовательный протокол с низкими дополнительными и коммуникационными вычислениями, см. Протокол 1. Используя протоколы [22][23] для «забывчивой передачи», мы получаем эффективный протокол с оптимальной связью. Проще говоря, будем считать, что лежащий в основе конфиденциальный 1-из- протокол забывчивой передачи имеет 2 перемещения и определяется тройными алгоритмами (query,reply,decode), т.к. для любого и , мы имеем . Это определение не налагает каких-либо ограничений, так как большинство практических протоколов «забывчивой передачи» исполняются в этой форме, и генерализация многоступенчатых протоколов очевидна. Еще один способ упростить операции – использовать фазу доверенных настроек для генерации общедоступных параметров. Можно исключить необходимость в доверенном распространителе, создав безопасный многосторонний протокол, но явное использование доверенных настроек делает доказательства безопасности модулярными.
Идея, лежащая в основе протокола, довольно проста. Во-первых, сервер использует схему обязательств для списков , чтобы зафиксировать все входные данные . Тогда сервер рассчитывает промежуточную базу данных сертификатов, связанных с каждым . В фазе запроса клиент и сервер исполняют протокол «забывчивой передачи» с входными данными сервера , чтобы извлечь –ный сертификат . Если это значение открывает элемент базы данных , он соответствует обязательству и запросу , тогда мы выводим , в противном случае выводим .

TemplateTheoremIcon.svg Теорема Теорема 3
Если протокол «забывчивой передачи» является защищенным по вычислениям в совместной установочной модели и схеме обязательств для списков , он зафиксированный и двузначный, то Протокол 1 является настраиваемым в -из- протоколе «забывчивой передачи» в полиномиальной модели безопасности при условии, что .
Доказательство
Чтобы доказать это, мы фиксируем параметр безопасности , учитывая, что есть злоумышленник , и показываем, как конвертировать его в злоумышленника из идеальной реализации , т.к. распределение выходных данных слишком близкое для любой пары выходных данных .

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

  1. Запустить фазу установки для получения общедоступных параметров для и .
  2. Выбрать произвольность и хранить .
  3. Послать третьей стороне и настроить предикаты останова через связь между клиентом и злоумышленником , которая , если с входными данными получает .
  4. Вывести любые выходные данные в связи с .

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

Безопасность сервера. Поскольку выходные данные сервера в идеальной и реальной моделях пусты, можно анализировать только выходные данные злоумышленника . Мы рассматриваем смешанное исполнение протокола, где все разновидности заменяются идеальными реализациями протокола «забывчивой передачи» с базой данных . Поскольку протокол конфиденциален в общей модели настроек, существует злоумышленник и выходные данные и нельзя различить вычислениями.
Чтобы завершить доказательство, мы конструируем реального злоумышленника в идеальном исполнении и показываем, что выходные данные и нельзя различить вычислениями. На самом деле злоумышленник в идеализированной реализации действует следующим путем:

  1. Создает двузначный ключ и транслирует .
  2. Вычисляет и посылает злоумышленнику .
  3. Если запрашивает , получает От третьей стороны и получает .
  4. Возвращает выходные данные .

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

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

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

TemplateTheoremIcon.svg Теорема Вывод 2
Если протокол «забывчивой передачи» конфиденциален по вычислениям в общей модели настроек, а схема обязательств для списков (слабо) извлекаема методом «белого ящика» и двухзначна, протокол 1 является последовательным настраиваемым -из- протоколом «забывчивой передачи» в (слабой) полиномиальной модели безопасности.
Доказательство
Отметим, что пара алгоритмов может считаться злоумышленником, который генерирует обязательство для списков , а затем открывает элементы согласно уведомлению . Поскольку схема обязательств извлекаема методом «белого ящика», существует извлекающее устройство , которое при определенных параметрах , выходных данных сервера и случайной последовательности , выдает список элементов , т.к. в конце исполнения принимает с малой долей вероятности. Это извлекающее устройство может быть использовано при конструировании симулятора из Теоремы 3 вместо

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

Сравнение с другими протоколами. Если полиномиальный в , мы можем использовать очень эффективные в плане связи обязательства для списков, которые растянут входные данные .Сочетая его с самым эффективным конфиденциальным протоколом «забывчивой передачи» [22], мы получим протокол с коммуникационной сложностью . Кроме того, если мы пренебрежем настройками, то для амортизированной цикличной сложности она составит два сообщения за запрос. Последнее гораздо лучше для коммуникационной сложности конфиденциальных настраиваемых протоколов «забывчивой передачи» [24][25][26][27], если судить по методам доказательства без разглашения секретной информации. При явном использовании теоремы PCP (первичных управляющих программ) можно достичь полилогарифмичной коммуникации [17], но такой подход оптимален лишь в плане асимптомичности.
Рассматривая вычислительную сложность, отметим, что дополнительные вычисления (по сравнению с конфиденциальными протоколами) совершаются на фазе фиксации. Для схемы обязательств для списков, основанной на древовидной схеме случайных данных, эти дополнительные вычисления заключаются в операциях хеширования и фиксации. Если количество запросов фиксировано, или , дополнительных затрат помимо вычисления фиксации не существует. Если же сервер обрабатывает неограниченное количество запросов, ему нужно доказать, что он знает, как открыть обязательства. В доказательствах с низкой эффективностью коммуникации сервер посылает все значения с низким уровнем коммуникации клиенту и доказывает, что ему известно каждое значение дефиксации. Клиент сначала проверяет, что корень дерева Меркла (ТТН) верен, а затем проверяет отдельные доказательства. Такие методы доказательства без раскрытия секретной информации особенно эффективны для реализации схемы Petersen. Опять же непроизводительные издержки – это операции . Используя подходящие методы конверсии (перекодирования)[17], мы можем достичь полилогарифмической коммуникации, увеличив дополнительные вычисления полиномиальным фактором. И хотя конструкция по-прежнему основана на теореме PCP , лежащее в основе доказательство проще – серверу не приходится доказывать корректность в каждой фазе запроса.
Оманн и Линделл описывали протокол «забывчивой передачи» -из-[2], являющийся безопасным в скрытой модели. И хотя гарантии безопасности меньше, чем для последовательного протокола (см. Таблицу 1), в их протоколе содержатся 7 сообщений и гораздо большая коммуникационная сложность. Справедливости ради стоит сказать, что из этих сообщений три использованы для внедрения доверенных настроек для протокола «забывчивой передачи», а 4 сообщения остаются для каждого запроса и злоумышленника, который может менять их входные данные в течение реализации протокола.

Последовательное условное разглашение секретных данных

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

серверу недоступны никакие данные. Протоколы CDS часто используются, чтобы конвертировать протоколы «клиент-сервер» в «получестных» моделях в протоколы, сохраняющие конфиденциальность входных данных во вредоносной модели, см. дополнительную информацию в[28][29].
В рамках данного исследования мы заинтересованы, прежде всего, в прямом использовании CDS-протоколов. CDS-протокол дает возможность распределить секретные данные, только если входные данные клиента отвечают определенным требованиям, т.е. клиент имеет право доступа к секретным данным. Например, рассмотрим видео-ролик в рамках информационного обслуживания в режиме "запрос-ответ", где клиенту предоставляется ключ к видео-потоку, только если у него/нее не отрицательный баланс:. Однако сервер не может определить конкретный баланс клиента. Протокол CDS, описанный в [30][31] состоит из двух команд, а запрос клиента состоит из двух зашифрованных текстов . Поскольку CDS-протоколы по типу [21] основаны на аддитивно гомоморфной криптосистеме, сервер может совершить ограниченное количество криптовычислений, чтобы сформировать зашифрованные тексты, которые расшифровывают секретные данные, если условие соблюдено. Таким образом, клиенту часто приходится посылать дополнительные шифровки дополнительных входных данных , чтобы помочь серверу. Например, . Поскольку решения[32][33] гарантируют только конфиденциальность во вредоносной модели, сложно доказать, что сервер недобросовестно отклоняет доступ, или что сервер просто не может опровергнуть ложность обвинений.
Теперь рассмотрим расширенный CDS-протокол, где сервер сначала пытается открыто зафиксировать , а CDS-протокол должен раскрыть соответствующее значение дефиксации. Поскольку доказательство Теоремы 3 и Выводы 2 является общим, получившийся в результате протокол является последовательным, согласно все тем же выводам. Если набор достоверных входных данных клиента является экспоненциальным, техника полного извлечения информации из Теоремы 3 становится невозможной, и метод, где сервер доказывает, что он/она может открыть обязательство, является единственным выходом. Последнее нельзя назвать серьезной проблемой, т.к. многие обычные схемы обязательства имеют серьезные доказательства знания данных. Например, двузначная схема обязательства Pedersen обладает таким свойством. Также отметим, что серверу не нужно доказывать знание значения дефиксации каждому. Достаточно будет, если сервер докажет это авторитетному участнику во время фазы инициализации. Если мы может гарантировать, что такие участники являются хотя бы наполовину добросовестными, тогда можно оптимизировать доказательство.
Кроме того, по Теореме 1 клиент может доказать третьим лицам, что со стороны сервера совершаются злоумышленные действия. Поскольку любой участник может повторить вторую фазу CDS-протокола, как описано в[34][35] с разными секретными данными , соответствующий метод доказательства добросовестности без раскрытия секретной информации очень эффективен. Клиент, имеющий жалобу, должен раскрыть проверяющему, а затем дополнительно доказать (если нужно, методом доказательства без раскрытия секретной информации), что от сервера приходит некорректный ответ.
Возможность обрабатывать жалобы делает CDS-протоколы очень полезными на ТВ или в передаче военных данных с политикой общего доступа, где верительные данные выдаются путем генерирования случайных ключей. Эта проблема известна всем как контроль конфиденциального вывода[1]. В этих условиях у сервера есть база данных скрытых ключей, которые используются для шифровки разного контента, в том числе документов разного уровня конфиденциальности. Клиенты получают различные верительные данные, и задача сервера – выдать корректные ключи. В целях безопасности серверу не должно быть известно, какие документы доступны разным клиентам. В то же время сервер должен блокировать доступ к документам тем клиентам, у которых нет соответствующих верительных данных. Клиенту в свою очередь нужно уметь различать отказ сервера от его атаки, где он совершает злоумышленные действия, а также законные отказы, когда у клиента нет права получить соответствующий ключ. Кроме того, чтобы сервис смог противостоять внутренним атакам, клиенту нужно доказать третьей стороне, что отказ является незаконным.
Обращаем внимание на то, что доказательство знания информации можно пропустить, если возможно заставить сервер сконструировать обязательства ключей полудобросовестным путем во время инициализации либо организационными способами, либо ревизией системы. Поскольку эффективные CDS-протоколы существуют для всех -предикатов[36], мы пришли к выводу, что подотчетный контроль конфиденциального вывода вполне возможен. Что важно – решение будет вполне практичным, если клиент, посылающий жалобу, намерен раскрыть свои входные данные.

Обсуждение и открытые проблемы

Оба решения «забывчивой передачи» и условного разглашения секретных данных основаны на простом принципе: сервер сначала создает список возможных ответов, а затем фиксируется на нем. Поскольку ответы не зависят друг от друга, клиент может проверить, является ли ответ корректным, а серверу нужно лишь доказать, что ему известны значения дефиксации, и что не все ответы согласуются с входными данными сервера. Как только ответы будут отвечать определенным требованиям, или клиент не сможет проверить, ли получит ли он/она значение дефиксации для верного ответа, конструкция последовательного протокола усложнится.
В любом случае, такой протокол должен вызывать схему обязательств для списков. На самом деле мы можем видеть, что любой протокол «клиент-сервер» для вычисления служит как обязательство списка с элементами где имеет все возможные значения. Для протокола с тремя действиями первое сообщение – это обязательство, а второе и третье сообщения соответствуют интерактивной процедуре открытия. Второе и третье сообщения могут быть соединены в одно значение дефиксации при условии, что клиент и сервер в сговоре не могут обмануть третью сторону, которой известно первое сообщение. Поскольку запрос не должен разглашать информацию о других входных данных, конструкция таких схем обязательств с гарантией корректности внутренней информации кажется очень нетривиальной задачей. Таким образом, вопрос о том, может ли кто-нибудь сконструировать последовательные протоколы трех действий для других задач, является очень интересным. Таким образом получится показать, какие типы ограничений можно внутренне менять при конструировании схемы обязательств. Другим открытым вопросом остается то, как много информации узнается из жалоб, отправляемых клиентами, и как ограничить утечку информации в этом случае. При определении корректности из жалобы вычисляются выходные данные полиномиального случайного предиката. Как показывает практика, мы можем дальше ограничить набор осуществимых предикатов . Например, можно обеспечить корректность информации без запоминания в протоколе «забывчивой передачи». Так, протокол «клиент-сервер» является корректным без запоминания, если предикаты останова не зависят от предыдущих запросов, т.е., , а серверу недоступны результаты разных запросов.

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

Аналогичные результаты наблюдаются у протоколов, состоящих из нескольких CDS протоколов. Однако корректность без запоминания данных требует неких затрат. Многие эффективные протоколы «забывчивой передачи»[37][38][23] и CDS-протоколы [39][40] основаны на гомоморфном шифровании. В этих протоколах фаза доверенных настроек проверяет, знает ли клиент на самом деле секретный ключ. Эта фаза сменяется соответствующим значением информации на практике. Если в каждом под-протоколе есть пара разных ключей, предшествующая фаза становится сложной. Таким образом, более разумно разделить ключ между несколькими реализациями протоколов, см. детальное описание в[41].
Но, поступив так, мы потеряем свойство корректности без запоминания, и возникнет закономерный вопрос: сможем ли мы установить обязательные остановочные предикаты? Поскольку все эти протоколы посылают входные данные клиента в зашифрованной форме серверу, и ответы также зашифрованы, легко установить аффинные предикаты. При списке зашифрованных данных сервер может размножить ответы

Для случайного элемента пространства сообщений. В результате ответы будут неизменными, когда ,и они будут распределены иначе. Как следствие, сервер легко сможет установить предикаты останова, соответствующие аффинным комбинациям полученных зашифрованных текстов . Размножив ответы несколькими такими зашифрованными текстами, сервер также может установить связь между такими аффинными комбинациями.
Отметим, что такие атаки могут совершаться только в дополнительно гомоморфной схеме шифровки. Таким образом, можно спросить, является ли это полным описанием предикатов останова или нет. Разумеется, вопрос этот касается только детерминированных предикатов, т.к. любая форма коммуникации «клиент-сервер» может быть формализована как случайный предикат. В детерминированных предикатах есть смысл сравнить поведение определенной системы шифрования данных с идеализированным прототипом, который дополняется в ходе шифрования, расшифровки и оракулов добавления зашифрованных текстов.Гомоморфная криптосистема имеет особенные свойства криптовычислений, если вредоносный сервер может установить детерминированные предикаты, которые нельзя установить, когда лежащая в основе система шифрования идеальна. Поскольку существуют системы шифрования, позволяющие вычислять криптографическим методом квадратичные полиномы[16] и даже полиномы любой длины[42], существуют системы шифрования с особенными свойствами. Однако во всех случаях эти свойства обусловлены построением системы шифрования. Таким образом, будет логичным предположить, что стандартные аддитивные криптосистемы, например криптосистема Пэйе[43], не имеют особенных свойств, и набор осуществимых предикатов ограничен, чтобы аффинировать тесты и их связи. Отрицание этого факта является интересным, так как это позволит расширить набор криптографически вычисляемых предикатов.
Благодарность. Оба автора выражают признательность Европейскому фонду регионального развития через Эстонский центр передового опыта компьютерных технологий (EXCS). Второй автор выражает благодарность Эстонскому научному сообществу, грант № .

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

  1. University of Tartu, Estonia
  2. Cybernetica AS, Estonia
  3. Tallinn University, Estonia

Литература

  1. 1,0 1,1 1,2 Woodruff, D.P., Staddon, J.: Private Inference Control. In Proc. of ACMCCS2004, pp. 188–197, ACM Press, 2004.
  2. 2,0 2,1 2,2 2,3 Aumann, Y., Lindell, Y.: Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries. In Proc. of TCC 2007. LNCS, vol. 4392, pp. 137–156, Springer, 2007.
  3. 3,0 3,1 Mohassel, P., Franklin, M.K.: Efficiency Tradeoffs for Malicious Two-Party Com- putation. In Proc. of PKC 2006. LNCS, vol. 3958, pp. 458–473, Springer-Verlag, 2006.
  4. Laur, S., Lipmaa, H.: On the Feasibility of Consistent Computations. Eprint 2006/088
  5. Di Crescenzo, G., Lipmaa, H.: Succinct NP Proofs from An Extractability As- sumption. In Proc. of CIE 2008. LNCS, vol. 5028, pp. 175–185, Springer-Verlag, 2008.
  6. 6,0 6,1 Canetti, R.: Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology 13(1), pp. 143–202, 2000
  7. 7,0 7,1 Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001
  8. Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In Proc. of EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135, Springer- Verlag, 2001.
  9. 9,0 9,1 Franklin, M.K., Yung, M.: Communication complexity of secure computation. In Proc. of STOC 1992, pp. 699–710, ACM Press, 1992.
  10. Canetti, R., Ostrovsky, R.: Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? In Proc. of STOC 1999, pp. 255–264, ACM Press, 1999.
  11. Goldreich, O.: On Expected Probabilistic Polynomial-Time Adversaries: A Sugges- tion for Restricted Definitions and Their Benefits. In Proc. of TCC 2007. LNCS, vol. 4392, pp. 174–193, Springer-Verlag, 2007.
  12. Crescenzo, G.D., Ishai, Y., Ostrovsky, R.: Non-Interactive and Non-Malleable Commitment. In Proc. of STOC 1998, pp. 141–150, ACM Press, 1998.
  13. Santis, A.D., Crescenzo, G.D., Persiano, G.: Necessary and Sufficient Assumptions for Non-iterative Zero-Knowledge Proofs of Knowledge for All NP Relations. In Proc. of ICALP 2000. LNCS, vol. 1853, pp. 451–462, Springer-Verlag, 2000.
  14. 14,0 14,1 Santis, A.D., Crescenzo, G.D., Persiano, G.: Necessary and Sufficient Assumptions for Non-iterative Zero-Knowledge Proofs of Knowledge for All NP Relations. In Proc. of ICALP 2000. LNCS, vol. 1853, pp. 451–462, Springer-Verlag, 2000.
  15. Buldas, A., Laur, S.: Knowledge-Binding Commitments with Applications in Time- Stamping. In Proc. of PKC 2007. LNCS, vol. 4450, pp. 150–165, Springer-Verlag, 2007.
  16. 16,0 16,1 16,2 Boneh, D., Goh, E.J., Nissim, K.: Evaluating 2-DNF Formulas on Ciphertexts. In Proc. of TCC 2005. LNCS, vol. 3378, pp. 325–341, Springer-Verlag, 2005.
  17. 17,0 17,1 17,2 17,3 Naor, M., Nissim, K.: Communication Preserving Protocols for Secure Function Evaluation. In Proc. of STOC 2001, pp. 590–599, ACM Press, 2001.
  18. Bellare, M., Goldreich, O.: On Defining Proofs of Knowledge. In Proc. of CRYPTO 1992. LNCS, vol. 740, pp. 390–420, Springer-Verlag, 1993.
  19. Pedersen, T.P.: Non-Interactive And Information-Theoretic Secure Verifiable Se- cret Sharing. In Proc. of CRYPTO 1991. LNCS, vol. 576, pp. 129–140, Springer- Verlag, 1991.
  20. Camenisch, J., Neven, G., Shelat, A.: Simulatable Adaptive Oblivious Transfer. In Proc. of EUROCRYPT 2007. LNCS, vol. 4515, pp. 573–590, Springer-Verlag, 2007.
  21. Peikert, C., Vaikuntanathan, V., Waters, B.: A Framework for Efficient And Com- posable Oblivious Transfer. In Proc. of CRYPTO 2008. LNCS, vol. 5157, pp. 554–571, Springer-Verlag, 2008.
  22. 22,0 22,1 Gentry, C., Ramzan, Z.: Single-Database Private Information Retrieval with Con- stant Communication Rate. In Proc. of ICALP 2005. LNCS, vol. 3580, pp. 803–815, Springer-Verlag, 2005.
  23. 23,0 23,1 Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Communication. In Proc. of ISC 2005. LNCS, vol. 3650, pp. 314–328, Springer-Verlag, 2005.
  24. Crepeau, C., van de Graaf, J., Tapp, A.: Committed Oblivious Transfer and Private Multi-Party Computation. In Proc. of CRYPTO 1995. LNCS, vol. 963, pp. 110– 123, Springer-Verlag, 1995.
  25. Cramer, R., Damgard, I.: Linear zero-knowledge – a note on efficient zero- knowledge proofs and arguments. In Proc. of STOC 1997, pp. 436–445, ACM Press, 1997.
  26. Cachin, C., Camenisch, J.: Optimistic Fair Secure Computation. In Proc. of CRYPTO 2000. LNCS, vol. 1880, pp. 93–111, Springer-Verlag, 2000.
  27. 25.Ogata, W., Kurosawa, K.: Oblivious Keyword Search. Journal of Complexity 20(2–3), pp. 356–371, 2004.
  28. Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In Proc. of EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135, Springer- Verlag, 2001.
  29. Laur, S., Lipmaa, H.: A New Protocol for Conditional Disclosure of Secrets And Its Applications. In Proc. of ACNS 2007. LNCS, vol. 4521, pp. 207–225, Springer- Verlag, 2007.
  30. Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In Proc. of EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135, Springer- Verlag, 2001.
  31. Laur, S., Lipmaa, H.: A New Protocol for Conditional Disclosure of Secrets And Its Applications. In Proc. of ACNS 2007. LNCS, vol. 4521, pp. 207–225, Springer- Verlag, 2007.
  32. Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In Proc. of EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135, Springer- Verlag, 2001.
  33. Laur, S., Lipmaa, H.: A New Protocol for Conditional Disclosure of Secrets And Its Applications. In Proc. of ACNS 2007. LNCS, vol. 4521, pp. 207–225, Springer- Verlag, 2007.
  34. Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In Proc. of EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135, Springer- Verlag, 2001.
  35. Laur, S., Lipmaa, H.: A New Protocol for Conditional Disclosure of Secrets And Its Applications. In Proc. of ACNS 2007. LNCS, vol. 4521, pp. 207–225, Springer- Verlag, 2007.
  36. Laur, S., Lipmaa, H.: A New Protocol for Conditional Disclosure of Secrets And Its Applications. In Proc. of ACNS 2007. LNCS, vol. 4521, pp. 207–225, Springer- Verlag, 2007.
  37. Stern, J.P.: A New And Efficient All Or Nothing Disclosure of Secrets Protocol. In Proc. of ASIACRYPT ’98. LNCS, vol. 1514, pp. 357–371, Springer-Verlag, 1998.
  38. Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In Proc. of EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135, Springer- Verlag, 2001.Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In Proc. of EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135, Springer- Verlag, 2001.
  39. Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In Proc. of EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135, Springer- Verlag, 2001.
  40. Laur, S., Lipmaa, H.: A New Protocol for Conditional Disclosure of Secrets And Its Applications. In Proc. of ACNS 2007. LNCS, vol. 4521, pp. 207–225, Springer- Verlag, 2007.
  41. Laur, S., Lipmaa, H.: A New Protocol for Conditional Disclosure of Secrets And Its Applications. In Proc. of ACNS 2007. LNCS, vol. 4521, pp. 207–225, Springer- Verlag, 2007.
  42. Gentry, C.: Fully Homomorphic Encryption Using Ideal Lattices. In Proc. of STOC 2009, pp. 169–178, ACM Press, 2009.
  43. Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In Proc, of EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238, Springer- Verlag, 1999.