Взгляд на конфиденциальные вычисления с точки зрения теории игр

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:57, 27 сентября 2015.
Towards a Game Theoretic View of Secure Computation
Towards a Game Theoretic View of Secure Computation.png
Авторы Gilad Asharov [@: 1] [прим. 1],
Ran Canetti [@: 2] [прим. 2],
Carmit Hazay [@: 3]
Опубликован 2011 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать Оригинал

__NUMBEREDHEADINGS__

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

Введение

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

Однако, несмотря на подобные различия, существуют примеры плодотворного взаиморазвития дисциплин (см., например, [1], [2]). Так, логичным шагом будет использование криптографических методов для решения традиционных проблем теории игр. В частности, в работах Додиса (Dodis) и др. [3], Измалкова (Izmalkov) и др. [4] [5], Абрахама (Abraham) и др. [6], а также Халперна и Пасса (Halpern and Pass) [7] избрано это направление исследований и показано, как многосторонний протокол, использующий методы криптографии, может быть использован для замены устройства доверенных взаимоотношений, или посредника, в конструкции механизма.

Другим направлением исследований является расширение традиционных формализмов теории игр с целью охватить в контексте теории игр криптографические интересы и идеи, принимая во внимание факт того, что участники протокола ограничены с точки зрения вычислений, а вычислительные ресурсы - дорогостоящи ([3], [7], [8]).

Еще одно направление работ ставит целью использование идей и подходов теории игр для расширения таких традиционных задач криптографии, как конфиденциальность и честность соединений. Работы данного направления делают акцент на концепции рационального честного обмена секретами (или рационального разделения секрета) ([9], [10], [11], [12], [13], [14], [15], [16]). Здесь целью является разработка такого протокола обмена секретами, в котором "рациональные игроки" были бы "заинтересованы" в соблюдении протокола; предполагается, что игроки заинтересованы в частях секрета других, при этом стараясь не допустить разглашения собственной части секрета. На практике предполагается, что участники имеют определенные предпочтения и что некоторые количественные характеристики этих предпочтений изначально известны разработчику протокола. Более того, такие предварительные знания оказываются крайне важными для отбраковывания изначально невозможных вариантов ([16], [17]).

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

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

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

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

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

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

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

Известные понятия честности для двустороннего протокола такой модели (например, в [20], [21]) требуют существования такого состояния соединения, в котором обе стороны прошли бы путь от полного незнания выхода до его известности. Это сильное определение, которое во многих ситуациях невозможно выполнить. Вместо этого, мы попробуем предложить менее строгие определения честности, позволяющие сторонам постепенно получать части информации об их желаемых выходах, но при этом делать это "честным" путем. И в самом деле, такой подход кажется логичным как с точки зрения теории игр (как игра с нулевой суммой), так и с криптографической точки зрения благодаря парадигме постепенного раскрытия (см., например, [22], [23], [24], [20], [16] и ссылки внутри этих статей).

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

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

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

Затем мы рассмотрим три разных криптографических определения честности и выясним их корреляцию с данным выше определением теории игр.

  • Сначала сформулируем простое "игровое" определение честности, которое ограничевает выгоду произвольного (другими словами, не обязательно "рационального") противника, приводящего к остановам при ошибках, в игре, близко модулирующей введенные ранее типы взаимодействия теории игр. Основное отличие между понятиями в том, что в реалиях криптографии противник скорее произвольный, нежели рациональный. Тем не менее, мы покажем эквивалентность этих определений.
  • Затем мы покажем, что это определение на самом деле соответствует концепции постепенного раскрытия. То есть, протокол удовлетворяет свойствам постепенного раскрытия, если на каждом шаге вероятность любой стороны предсказать выход прирастает с крайне малой скоростью. Мы покажем, что протокол является честным (как и в предыдущих определениях) тогда и только тогда, когда он удовлетворяет свойствам постепенного раскрытия. Стоит отметить, что понятие постепенного раскрытия является, по сути, основой классических протоколов Бивера ( Beaver), Голдвассера (Goldwasser) и Левина (Levin) ([22], [23]). Оно также является ключевой частью в работе Ашарова (Asharov) и Линдела (Lindell) ([16]). Из-за недостака места мы не приводим здесь определние постепенного раскрытия; ознакомиться с формальным описанием можно в полной версии [25].
  • После всего этого мы сформулируем определение честности для идеальной модели, которое допускает постепенное раскрытие секретов. В этом понятии под идеальной возможной функции (functionality) понимается использование "алгоритма выборки" из идеальной модели противника. Затем возможная функция получает входы сторон и запускает на этих входах, и получает при помощи выходы, которые должны быть переданы двум сторонам. Затем функция делает соответствующие выходы доступными для двух сторон. (То есть, как только выходы становятся доступными, стороны имеют к ним доступ в любое время.) Корректность и честность, гарантирующиеся при таком взаимодействии, целиком зависят от свойств . Таким образом, от требуется быть "честной" и "корректной" в том смысле, что обе стороны получают корректные выходы с примерно равной (и фиксированной) вероятностью. Затем мы покажем, как новые, полученные экспериментальным путем определения воплощают понятие постепенного раскрытия. (Заметим, что обратное не обязательно выполняется при безопасных вычислениях в модели с остановами при ошибках, даже без учета честности.)

Положительный результат. Наконец, мы рассмотрим реализацию этих понятий. В этом разделе мы сперва приведем утверждение, что результаты Клива (Cleve) и Ашарова (Asharov) и Линдела (Lindell) ([17], [16]) остаются недостижимыми даже относительно новых понятий до тех пор, пока обе стороны обязаны получать выход. Затем мы отметим, что наши определения не теряют своей поезности даже в том случае, когда сторонам не гарантировано получение корректного выхода при честной игре. Неожиданно, но в случаях, когда стороны узнают правильный выход с вероятностью или меньше (то есть корректность сохраняется с вероятностью от до ), наше основанное на вычислениях определение честности достижимо без каких-либо изменений или привлечения третьей, доверенной, стороны. Мы продемонстрируем семейство двухсторонних протоколов, параметры которых выбраны с учетом такой вероятности корректноси, такое, что в нем выполняются новые определения честности. Например, для случая, когда корректность гарантирована с вероятностью , мы разработаем честный протокол, с вероятностбю обеих сторон получить корректное значение и вероятностью получения обеими сторонами некорректного значения. Другой протокол удостоверяется в том, что каждая сторона получает корректный выход с вероятностью , и что при каждом исключении только одна сторона получает корректное выходное значение. Эти сценарии никогда раньше не достигались (даже в [21]) и могут оказаться полезными.

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

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

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

Организация. В разделе 2 представлены концепции решений из криптографии и теории игр. В разделе 4 представлены результаты, касающиеся честности: (I) - понятие из теории игр, (II) - эквивалентное определение из криптографии, (III) - новое, основанное на симуляциях, определение, и (IV) - изучение этих определений честности. Свойство постепенного раскрытия, его отношение к честности и некоторые другие детали можно найти в полной версии [25].

Модель и пути решения задачи

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

Криптографические определения

Мы дадим несколько стандартных криптографических определений конфиденциальности протоколов.

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

Криптографическая безопасность. Мы представим определения конфиденциальности и корректности в игровых терминах. При этом ограничив круг рассмотрения детерминированными функциями. Согласно определению из [18], вид -ой стороны во время исполнения над обозначается и равен , где соответствует внутреннему случайному значению -ой стороны, а - -ое полученному сообщению.

TemplateDifinitionIcon.svg Определение «Определение 1 (Конфиденциальность)»

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

1. Для каждого неоднородного вероятностно полиномиального то времени (PPT) противника , конролирующего сторону
где и
2. Для каждого неоднородного вероятностно полиномиального то времени (PPT) противника , конролирующего сторону
где и
TemplateDifinitionIcon.svg Определение «Определение 2 (Корректность)»

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

Определения из теории игр

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

TemplateDifinitionIcon.svg Определение «Определение 3 (Равновесие Нэша для игры нормальной формы с полной информацией)»

Пусть имеет вид, описанный выше, и пусть - пара стратегий, таких, как описано выше. Тогда находится в равновесии Нэша, если для всех и всех стратегий выполнено условие , где и .

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

TemplateDifinitionIcon.svg Определение «Определение 4 (Равновесие Нэша для игры экстенсивной формы с неполной информацией)»

Пусть имеет вид, описанный выше, и пусть - распределение над . Также, пусть - пара стратегий экстенсивной формы, как описано выше. Тогда находится в равновесии Нэша для , если для всех и всех стратегий выполнено условие , где взяты из распределения , - стратегия стороны с типом , и и

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

TemplateDifinitionIcon.svg Определение «Определение 5 (Вычислительное равновесие Нэша для игры экстенсивной формы с неполной информацией)»

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

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

TemplateDifinitionIcon.svg Определение «Определение 6»

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

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

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

TemplateDifinitionIcon.svg Определение «Определение 7 (Протоколы Нэша)»

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

Идеальное равновесие подыгр и связанные с ним концепции решения. Привлекательной концепцией решения для игр экстенсивной формы (еще называемых интерактивными протоколами) является идеальное равновесие, позволяющее проводить аналитическую обработку без придания внимания так называемым «пустым угрозам». Более того, несколько подходящих для нашей вычислительной системы вариантов определений были недавно сформулированы в других работах (см. [8], [26]). Тем не менее, в нашем конкретном случае игр с остановами при ошибках мы отметим, что любое равновесие Нэша идеально в подыграх. И в самом деле, как только одна из сторон прерывает выполнение, у другой стороны пропадает всякая возможность «нанести ответный удар», что делает пустые угрозы бессмысленными. (Напомним, что алгоритмы генерации выхода не являются «стратегическими», таковым является только решение о прерывании.)

Взгляд на конфиденциальность и корректность с точки зрения теории игр

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

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

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

TemplateDifinitionIcon.svg Определение «Определение 8 (Конфиденциальное множество распределений)»

Конфиденциальным множеством распределений для для двухсторонней функции называется множество , где и выходом является пара , в которой .

Конфиденциальное множество распределений для определяется аналогично.

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

TemplateDifinitionIcon.svg Определение «Определение 9 (Конфиденциальная функция полезности)»

Пусть - двухсторонний протокол и - двухсторонняя функция. Тогда для всех таких, что , и для всех предполагаемых алгоритмов math> \mathcal{B} \,\!</math> конфиденциальная функция полезности для стороны с входом определяется следующим образом:

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

TemplateDifinitionIcon.svg Определение «Определение 10 (Конфиденциальные с точки зрения теории игр протоколы)»

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

Конфиденциальный с точки зрения теории игр протокол для определяется аналогично. Протокол является конфиденциальным с точки зрения теории игр, если он конфиденциален с точки зрения теории игр для обеих сторон - и .

TemplateTheoremIcon.svg Теорема Теорема 11

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

Доказательство
Доказательство может быть найдено в полной версии [25].


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

TemplateDifinitionIcon.svg Определение «Определение 12 (Корректное множество распределений)»

Пусть - детерминированная двухсторонняя функция. Тогда корректным множеством распределений называется множество , где и из выходят w.p. 1.

Заметим, что противник, приводящий к остановам при ошибках, не может повлиять на корректность протокола, если играет честно с исключением в виде возможности прерывания. Тогда при приходе сообщения о прерывании возникает следующая ситуация: (I) либо честная сторона уже знает свой выход и, таким образом, корректность должна быть гарантирована, либо (II) честная сторона еще не знает выхода, для которой выводится он выводится через вместе с предположениями по выходу (что соответствует легальному выходу по Определению 2). Заметим, что это предположение отличается от предположения, добавленного в Определении 9 конфиденциальной функции полезности, так как здесь мы подразумеваем, что протокол разъясняет честной стороне, как вести себя в случае прерывания. Более того, некорректный протокол при наличии приводящего к остановам при ошибках противника предполагает, что протокол некорректен независимо от действий сторон (где действием может быть продолжение выполнения либо прерывание).

Таким образом, логичным будет предположить следующую модель работы функции полезности: стороны извлекают большую пользу, если они выводят корректное значение, и теряют при выводе некорректного значения. Таким образом, - стратегия не достигнет равновесия Нэша в случае некорректного протокола, так как стороны получат большую выгоду, не участвуя в выполнении. Говоря более формально:

TemplateDifinitionIcon.svg Определение «Определение 13 (Корректная функция полезности)»

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

-
-

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

Отсюда становится ясно, что протокол является игрой с остановами при ошибках, если он корректен, и наоборот. Формально это описано ниже. В свою очередь, для определяется аналогично.

TemplateTheoremIcon.svg Теорема Теорема 14

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

Доказательство
Доказательство может быть найдено в полной версии [25].


Изучение честности в двухсторонних случаях

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

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

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

Затем в разделе 4.3. мы введем новое, основанное на моделировании, понятие для описания конфиденциальности протоколов, следующих нашим основанным на играх понятиям честности, определённым ранее. Это новое понятие необходимо, так как (основанные на играх) честные протоколы в большинстве своём не могут быть симулированы согласно традиционному основанному на симуляциях определению [18]. Мы рассматриваем понятие «частичной информации» в идеальном случае с соблюдением некоторых частей из понятия конфиденциальности. Также мы докажем, что протоколы, удовлетворяющие этому новому определению, также являются честными согласно основанному на играх определению.

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

Честность с точки зрения теории игр

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

TemplateDifinitionIcon.svg Определение «Определение 15 (Честный набор множеств распределений)»

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

- (на каждом шаге, на котором возможны два выхода для ).
- (на каждом шаге, на котором возможны два выхода для ).

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

, где и .

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

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

TemplateDifinitionIcon.svg Определение «Определение 16 (Честная функция полезости)»

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

где такие, как описано в Определении 15, и . Кроме того, полезность для равна .

Так как функция полезности для определена, только нет стимула менять свою стратегию. Более того, мы рассматриваем здесь последовательность игр, в которой всегда предсказывает свой выход по , так называемый «оригинальный» протокол. Это значит, что всегда играет честно с криптографической точки зрения. Теперь мы готовы определить протокол, честный с точки зрения теории игр для :

TemplateDifinitionIcon.svg Определение «Определение 17 (Честность с точки зрения теории игр для

Пусть и будут такими, как описано выше. Тогда будем говорить, что честный с точки зрения теории игр для , если является протоколом Нэша для и и всех PPT-алгоритмов , где .

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

TemplateDifinitionIcon.svg Определение «Определение 18 (Честный с точки зрения теории игр протокол)»

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

Новое, «неотличимое», определение честности

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

TemplateDifinitionIcon.svg Определение «Определение 19 (Нетривиальные возможные функции)»

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

Теперь мы готовы представить формальное определение честности:

TemplateDifinitionIcon.svg Определение «Определение 20 (Игровое определение честности)»

Пусть - нетривиальная двухсторонняя функция, и пусть - двухсторонний протокол. Тогда для всех входных кортежей (см. Определение 19) и всех приводящих к остановам при ошибках PPT-противниках мы определим следующую игру:

Игра :
1. Два бита выбираются случайны образом.
2. Протокол запускается на входах для и для , где знает вид .
3. Всегда, когда выдает значение , получает сообщение . (В этом случае запишет свое предположение для на выходе.)
4. Выходом игры будет:
- , если (I) и (II) не выдает на выход .
- , если (I) и (II) выдает на выход .
- в любом другом случае (обе стороны выводят корректные значения, либо обе стороны выдают на выход некорректные значения).

Будем говорить, что честно вычисляет , если для всех PPT-противников существует бесконечно малая функция такая, что для всех достаточно больших выжодов верно следующее неравенство:

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

TemplateTheoremIcon.svg Теорема Теорема 21

Пусть - двухсторонняя функция и - протокол, корректно вычисляющий . Тогда является честным с точки зрения теории игр (удовлетворяет Определению 18) тогда и только тогда, когда честно вычисляет при наличии приводящих к остановам противников (удовлетворяет Определению 20).

Доказательство
Доказательство может быть найдено в полной версии [25].


Новое, основанное на моделировании, определение честности

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

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

Из-за недостатка времени мы приведем только основные моменты этого определения. Полную версию можно увидеть в [25]. Для машины мы сформулируем следующие требования:

1. Корректность: мы требуем, чтобы для некоторых , где - входы сторон, посылаемые доверенной стороне, и - выходы . Другими словами, вычисляющая «образцы» машина никогда не выдает для некоторой стороны значение, не коррелирующее с её входом.
2. Честность: мы требуем, чтобы существовала бесконечно малая функция такая, что для всех достаточно больших выполнено следующее условие:
где , противник контролирует сторону и вероятность случайным образом берется из .

Теперь определение безопасности можно задать стандартным образом:

TemplateDifinitionIcon.svg Определение «Определение 22»

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

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

TemplateTheoremIcon.svg Теорема Теорема 23
Пусть , будут такими, как указано выше. Тогда, если симулируем (в отношении Определения 22), тогда честен с точки зрения игр (в отношении Определения 20).
Доказательство


Возможность реализации наших определений

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

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

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

TemplateDifinitionIcon.svg Определение «Определение 24»

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

где обозначает выход стороны при значении на входе , пока на стороне стоит , и обе стороны играют честно.

Наша теорема невозможности:

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


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

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

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

Идеальная возможная функция
- Входные данные: от приходят . От приходят .
- Функция:
  • Подбрасывает монету , равную с вероятностью , и равную с вероятностью .
  • Бросаем еще одну монету случайно равномерно из .
  • Если : выходы устанавливаются равными соответственно.
  • Если : выходы устанавливаются равными соответственно.
  • Если (стороны получают разные по корректности выходы), то:
  • Бросаем еще одну монету случайно равномерно из .
  • Выход стороны устанавливается в .
  • Выход стороны устанавливается в .

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

TemplateTheoremIcon.svg Теорема Теорема 26
Пусть - нетривиальная двухсторонняя функция. Тогда для каждого протокол является -корректным протоколом на основе -гибридной модели, и является моделируемым (в смысле Определения 22).
Доказательство


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

  1. Department of Computer Science, Bar-Ilan University, Israel, E-mail: asharog@cs.biu.ac.il
  2. Department of Computer Science, Tel-Aviv University, Israel, E-mail: canetti@tau.ac.il
  3. Department of Computer Science, Aarhus University, Denmark, E-mail: carmit@cs.au.dk

Примечания

  1. При поддержке Европейского Исследовательского Совета (European Research Council - ERC) в рамках проекта LAST.
  2. При поддержке Института Информационной безопасности компании Check Point, BSF, ISF и гранта имени Марии Кюри.

Литература

  1. 1,0 1,1 Katz, J.: Bridging Game Theory and Cryptography: Recent Results and Future Directions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 251–272. Springer, Heidelberg (2008)
  2. Dodis, Y., Rabin, T.: Cryptography and Game Theory. In: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
  3. 3,0 3,1 3,2 Dodis, Y., Halevi, S., Rabin, T.: A Cryptographic Solution to a Game Theoretic Problem. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 112–130. Springer, Heidelberg (2000)
  4. Izmalkov, S., Micali, S., Lepinski, M.: Rational Secure Computation and Ideal Mechanism Design. In: 46th FOCS, pp. 585–595 (2005)
  5. Izmalkov, S., Lepinski, M., Micali, S.: Verifiably Secure Devices. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 273–301. Springer, Heidelberg (2008)
  6. Abraham, I., Dolev, D., Gonen, R., Halpern, J.Y.: Distributed Computing Meets Game Theory: Robust Mechanisms for Rational Secret Sharing and Multiparty Computation. In: PODC, pp. 53–62 (2006)
  7. 7,0 7,1 Halpern, J., Pass, R.: Game Theory with Costly Computation. In: ICS, pp. 120–142 (2010)
  8. 8,0 8,1 8,2 Gradwohl, R., Livne, N., Rosen, A.: Sequential Rationality in Cryptographic Protocols. In: FOCS, pp. 623–632 (2010)
  9. Halpern, J., Teague, V.: Efficient Rational Secret Sharing in Standard Communication Networks. In: 36th STOC, pp. 623–632 (2004)
  10. Gordon, S.D., Katz, J.: Rational Secret Sharing, Revisited. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 229–241. Springer, Heidelberg (2006)
  11. Lysyanskaya, A., Triandopoulos, N.: Rationality and Adversarial Behavior in Multi-party Computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 180–197. Springer, Heidelberg (2006)
  12. Kol, G., Naor, M.: Games for exchanging information. In: 40th STOC, pp. 423–432 (2008)
  13. Kol, G., Naor, M.: Cryptography and Game Theory: Designing Protocols for Exchanging Information. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 320–339. Springer, Heidelberg (2008 )
  14. Ong, S.J., Parkes, D.C., Rosen, A., Vadhan, S.P.: Fairness with an Honest Minority and a Rational Majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 36–53. Springer, Heidelberg (2009)
  15. Fuchsbauer, G., Katz, J., Naccache, D.: Efficient Rational Secret Sharing in Standard Communication Networks. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 419–436. Springer, Heidelberg (2010)
  16. 16,0 16,1 16,2 16,3 16,4 Asharov, G., Lindell, Y.: Utility Dependence in Correct and Fair Rational Secret Sharing. Journal of Cryptology 24(1), 157–202 (2011)
  17. 17,0 17,1 Cleve, R.: Limits on the Security of Coin Flips when Half the Processors are Faulty. In: 18th STOC, pp. 364–369 (1986)
  18. 18,0 18,1 18,2 18,3 18,4 Goldreich, O.: Foundations of Cryptography. Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)
  19. Goldwasser, S., Micali, S.: Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information. J. Comput. Syst. Sci. 28(2), 270–299 (1984)
  20. 20,0 20,1 Gordon, S.D., Katz, J.: Partial Fairness in Secure Two-Party Computation. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 157–176. Springer, Heidelberg (2010)
  21. 21,0 21,1 Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure twoparty computation. In: STOC, pp. 413–422 (2008)
  22. 22,0 22,1 Beaver, D., Goldwasser, S.: Multiparty computation with faulty majority. In: 30th FOCS, pp. 468–473 (1989)
  23. 23,0 23,1 Goldwasser, S., Levin, L.A.: Fair computation of general functions in presence of immoral majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77–93. Springer, Heidelberg (1991)
  24. Garay, J.A., MacKenzie, P.D., Prabhakaran, M., Yang, K.: Resource fairness and composability of cryptographic protocols. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 404–428. Springer, Heidelberg (2006)
  25. 25,0 25,1 25,2 25,3 25,4 25,5 25,6 Asharov, G., Canetti, R., Hazay, C.: Towards a Game Theoretic View of Secure Computation (full version) (in ePrint)
  26. 26,0 26,1 Pass, R., Shelat, A.: Renegotiation-Safe Protocols. In: Innovations in Computer Science, ICS 2011 (2011)

27. Canetti, R.: Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology 13(1), 143–202 (2000)
28. Fudenberg, D., Tirole, J.: Game Theory. The MIT Press, Cambridge (1991)
29. Goldreich, O., Micali, S., Wigderson, A.: How to Play any Mental Game – A Completeness Theorem for Protocols with Honest Majority. In: 19th STOC, pp. 218–229 (1987)
30. Goldreich, O., Kahan, A.: How To Construct Constant-Round Zero-Knowledge Proof Systems for NP. Journal of Cryptology 9(3), 167–190 (1996)
31. Goldwasser, S., Micali, S., Rachoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM J. Computing 18(1), 186–208 (1989)