Безопасные многосторонние вычисления - Secure multi-party computation

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

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

История

Протоколы специального назначения для конкретных задач появились в конце 1970-х годов.^[1] Позже безопасные вычисления были официально представлены как безопасное двухстороннее вычисление (2PC) в 1982 г. (для т.н. Проблема миллионеров, конкретная задача, которая является булевым предикатом), и в целом (для любых возможных вычислений) в 1986 г. Эндрю Яо.^[2][3] Эта область также называется оценкой функции безопасности (SFE). За двухпартийным случаем последовало обобщение на многопартийность Голдрайхом, Микали и Вигдерсоном. Вычисления основаны на секретном совместном использовании всех входных данных и доказательствах с нулевым разглашением для потенциально злонамеренного случая, когда большинство честных игроков в случае злонамеренного противника заверяют, что плохое поведение обнаружено, и вычисления продолжаются с устранением нечестного человека или его ввод обнаружен. В этой работе была предложена очень простая общая схема, которой должны следовать практически все будущие многосторонние протоколы для безопасных вычислений.^[4] За этой работой последовал первый надежный безопасный протокол, который любезно допускает ошибочное поведение, не раскрывая чьи-либо выходные данные, посредством работы, которая изобрела для этой цели часто используемую "идею доли общих ресурсов".^[5] и протокол, который позволяет одной из сторон безоговорочно скрывать свой ввод.^[6] Вышеупомянутые результаты относятся к модели, в которой злоумышленник ограничен вычислениями за полиномиальное время и наблюдает за всеми коммуникациями, поэтому модель называется "вычислительной моделью". Далее протокол не обращая внимания на передачу показала свою готовность к этим задачам.^[7] Приведенные выше результаты показали, что с помощью описанных выше вариантов можно достичь безопасных вычислений, когда большинство пользователей честны.

Следующим вопросом, который нужно было решить, был случай защищенных каналов связи, когда двухточечная связь недоступна злоумышленнику; в этом случае было показано, что решения могут быть достигнуты, если до 1/3 сторон будут вести себя некорректно и злонамеренно, и в решениях не используются криптографические инструменты (поскольку доступна безопасная связь).^[8][9] Добавление широковещательного канала позволяет системе терпеть до 1/2 меньшинства, нарушающего правила поведения,^[10] в то время как ограничения связности на коммуникационном графе исследовались в книге Совершенно безопасная передача сообщений.^[11]

С годами понятие многосторонних протоколов общего назначения стало плодородной областью для исследования свойств основных и общих проблем протокола, таких как универсальная компоновка или мобильный противник как в активный обмен секретами.^[12]

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

Определение и обзор

В MPC заданное количество участников p₁, п₂, ..., п_N, у каждого есть личные данные соответственно d₁, d₂, ..., d_N. Участники хотят вычислить значение публичной функции на этих частных данных: F (d₁, d₂, ..., d_N), сохраняя при этом свои собственные данные в секрете.

Например, предположим, что у нас есть три стороны, Алиса, Боб и Чарли, с соответствующими входными данными x, y и z, обозначающими их зарплаты. Они хотят узнать самую высокую из трех зарплат, не раскрывая друг другу, сколько зарабатывает каждый из них. Математически это означает, что они вычисляют:

F (х, у, z) = макс (х, у, z)

Если бы существовала какая-то доверенная внешняя сторона (скажем, у них был общий друг Тони, который, как они знали, мог хранить секреты), каждый из них мог бы сообщить свою зарплату Тони, он мог бы вычислить максимум и сообщить это число всем им. Цель MPC - разработать протокол, в котором, обмениваясь сообщениями только друг с другом, Алиса, Боб и Чарли все еще могут учиться F (х, у, z) не раскрывая, кто что делает, и не полагаясь на Тони. Они не должны узнавать больше, участвуя в своем протоколе, чем они узнали бы, взаимодействуя с неподкупным, абсолютно заслуживающим доверия Тони.

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

Неформально говоря, основными свойствами, которые стремится обеспечить протокол многосторонних вычислений, являются:

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

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

Определения безопасности

Протокол многосторонних вычислений должен быть безопасным, чтобы быть эффективным. В современной криптографии безопасность протокола связана с доказательством безопасности. Доказательство безопасности - это математическое доказательство, в котором безопасность протокола сводится к безопасности его базовых примитивов. Тем не менее, не всегда удается формализовать криптографический протокол проверка безопасности на основе знания стороны и правильности протокола. Для протоколов MPC среда, в которой работает протокол, связана с парадигмой реального / идеального мира.^[16] Нельзя сказать, что стороны ничего не узнают, так как им нужно узнать результат операции, а результат зависит от входов. Кроме того, правильность вывода не гарантируется, поскольку правильность вывода зависит от вводов сторон, и следует предполагать, что вводы повреждены.

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

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

Требования безопасности к протоколу MPC строги. Тем не менее, в 1987 году было продемонстрировано, что любая функция может быть безопасно вычислена с защитой от злоумышленников.^[4] и другие начальные работы, упомянутые ранее. Несмотря на эти публикации, MPC не был разработан для того, чтобы быть достаточно эффективным, чтобы его можно было использовать на практике в то время. Безусловная или теоретически безопасная информация MPC тесно связана с проблемой секретный обмен, и, более конкретно поддающийся проверке секретный обмен (VSS), который многие защищенные протоколы MPC используют против активных злоумышленников.

В отличие от традиционных криптографических приложений, таких как шифрование или подпись, следует предполагать, что противник в протоколе MPC является одним из игроков, вовлеченных в систему (или контролирующих внутренние стороны). Эта коррумпированная сторона или стороны могут вступить в сговор с целью нарушения безопасности протокола. Позволять ${\displaystyle n}$ быть количеством сторон в протоколе и ${\displaystyle t}$ количество сторон, которые могут быть состязательными. Протоколы и решения для случая ${\displaystyle t<n/2}$ (т.е. когда предполагается честное большинство) отличаются от тех, где такое предположение не делается. Этот последний случай включает важный случай двухсторонних вычислений, когда один из участников может быть поврежден, и общий случай, когда неограниченное количество участников повреждено и вступает в сговор, чтобы атаковать честных участников.

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

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

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

Как и многие криптографические протоколы, безопасность протокола MPC может основываться на различных предположениях:

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

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

Протоколы

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

Двухстороннее вычисление

Основная статья: Безопасные двухсторонние вычисления

Смотрите также: Искаженная схема

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

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

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

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

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

Входные биты отправителя (т. Е. Создателей схемы) могут быть просто отправлены в виде кодирования оценщику; тогда как кодирование получателя (то есть оценщиков цепей), соответствующее его входным битам, получается через 1-из-2 Забывающая передача (OT) протокол. Протокол OT 1-из-2 позволяет отправителю, обладающему двумя значениями C1 и C2, отправить то, которое запрошено получателем (значение ba в {1,2}) таким образом, чтобы отправитель не знает, какое значение было передано, а получатель узнает только запрошенное значение.

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

Многосторонние протоколы

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

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

Схемы совместного использования секретов позволяют противнику контролировать до т вечеринки из п всего партий, где т варьируется в зависимости от схемы, противник может быть пассивным или активным, и о силе противника делаются разные предположения. Схема совместного использования секретов Шамира защищена от пассивного противника, когда ${\displaystyle t<{\frac {n}{2}}}$ и активный противник, когда ${\displaystyle t<{\frac {n}{3}}}$ при достижении теоретико-информационной безопасности, что означает, что даже если злоумышленник имеет неограниченные вычислительные мощности, он не может узнать какую-либо информацию о секрете, лежащем в основе доли. Протокол BGW,^[19] который определяет, как вычислять сложение и умножение на секретных долях, часто используется для вычисления функций с секретными долями Шамира. Аддитивные схемы совместного использования секретов могут допускать, чтобы злоумышленник контролировал все, кроме одной стороны, то есть ${\displaystyle t<n}$, сохраняя безопасность от пассивного и активного противника с неограниченной вычислительной мощностью. Некоторые протоколы требуют фазы настройки, которая может быть защищена только от вычислительно ограниченного противника.

В ряде систем реализованы различные формы MPC со схемами разделения секрета. Самый популярный - СПДЗ,^[20] который реализует MPC с дополнительными секретными долями и защищен от активных противников.

Другие протоколы

В 2014 году была описана «модель справедливости в безопасных вычислениях, в которой противоборствующая сторона, которая прерывает получение выходных данных, вынуждена платить заранее определенный денежный штраф», была описана для Биткойн сети или для честной лотереи.^[21]

Практические системы MPC

За последние годы в системах 2PC и MPC было сделано много успехов.

Протоколы на основе Яо

Одна из основных проблем при работе с протоколами на основе Yao заключается в том, что функция, которая должна быть безопасно оценена (которая может быть произвольной программой), должна быть представлена ​​в виде схемы, обычно состоящей из элементов XOR и AND. Поскольку большинство реальных программ содержат циклы и сложные структуры данных, это весьма нетривиальная задача. Система Fairplay^[22] был первым инструментом, предназначенным для решения этой проблемы. Fairplay состоит из двух основных компонентов. Первый из них - это компилятор, позволяющий пользователям писать программы на простом языке высокого уровня и выводить эти программы в виде логической схемы. Затем второй компонент может искажать схему и выполнять протокол для надежной оценки искаженной схемы. Помимо двухсторонних вычислений на основе протокола Yao, Fairplay также может выполнять многосторонние протоколы. Это делается с использованием протокола BMR,^[22] который расширяет пассивно защищенный протокол Yao на активный случай.

За годы, прошедшие после введения Fairplay, в базовый протокол Yao было внесено множество улучшений в форме как повышения эффективности, так и методов активной безопасности. К ним относятся такие методы, как метод свободного XOR, который позволяет значительно упростить оценку вентилей XOR, и сокращение искаженных строк, уменьшая размер искаженных таблиц с двумя входами на 25%.^[23]

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

Такой подход к активной безопасности был предложен Линделлом и Пинкасом.^[24] Этот метод был реализован Pinkas et al. в 2009,^[23] Это обеспечило первую активно защищенную двухстороннюю оценку схемы Advanced Encryption Standard (AES), которая рассматривается как очень сложная (состоящая из около 30 000 логических элементов AND и XOR), нетривиальная функция (также с некоторыми потенциальными приложениями). 20 минут на вычисление и требуется 160 схем для получения ${\displaystyle 2^{-40}}$ вероятность обмана.

Поскольку оценивается множество схем, стороны (включая получателя) должны фиксировать свои входные данные, чтобы гарантировать, что во всех итерациях используются одни и те же значения. Эксперименты Пинкаса и др. сообщил^[23] показать, что узкое место протокола заключается в проверках согласованности. Чтобы оценить схему AES, им пришлось отправить по сети около 6 553 600 обязательств с различными ценностями. В последних результатах^[25] эффективность активно защищенных реализаций на основе Yao была улучшена еще больше, потребовалось всего 40 схем и гораздо меньше обязательств, чтобы получить ${\displaystyle 2^{-40}}$ вероятность обмана. Улучшения проистекают из новых методологий выполнения выборки по переданным схемам.

В последнее время основное внимание уделялось высокопараллельным реализациям на основе искаженных схем, предназначенным для работы на Процессоры с большим количеством ядер. Кройтер и др.^[26] описать реализацию, работающую на 512 ядрах мощного кластерного компьютера. Используя эти ресурсы, они могли оценить 4095-битный редактировать расстояние функция, схема которой насчитывает почти 6 миллиардов вентилей. Для этого они разработали специальный, лучше оптимизированный компилятор схем, чем Fairplay, и несколько новых оптимизаций, таких как конвейерная обработка, при которой передача искаженной схемы по сети начинается, в то время как остальная часть схемы все еще генерируется. Время вычисления AES было сокращено до 1,4 секунды на блок в активном случае при использовании кластерного компьютера с 512 узлами и до 115 секунд при использовании одного узла. Шелат и Шен^[27] улучшите это, используя обычное оборудование, до 0,52 секунды на блок. В той же статье сообщается о пропускной способности 21 блок в секунду, но с задержкой 48 секунд на блок.

Между тем, другая группа исследователей исследовала использование потребительского уровня GPU для достижения аналогичных уровней параллелизма.^[28] Они используют расширения OT и некоторые другие новые методы для разработки своего протокола, специфичного для графического процессора.Похоже, что этот подход обеспечивает сопоставимую эффективность с реализацией кластерных вычислений с использованием аналогичного количества ядер. Однако авторы сообщают только о реализации схемы AES, которая имеет около 50 000 ворот. С другой стороны, необходимое здесь оборудование гораздо более доступно, поскольку подобные устройства уже можно найти на настольных компьютерах или игровых консолях многих людей. Авторы получают синхронизацию 2,7 секунды на блок AES на стандартном рабочем столе со стандартным графическим процессором. Если они позволяют снизить уровень безопасности до уровня, похожего на скрытую безопасность, они получают время выполнения 0,30 секунды на блок AES. В случае пассивной безопасности есть отчеты об обработке цепей с 250 миллионами вентилей и со скоростью 75 миллионов вентилей в секунду.^[29]

Смотрите также

• Цифровая валюта
• Гомоморфное шифрование
• Ментальный покер
• Протокол многостороннего честного обмена
• Незаметный перевод
• Вычислительная геометрия с сохранением конфиденциальности
• Проблема миллионеров Яо

использованная литература

1. А. Шамир, Р. Ривест и Л. Адлеман, «Mental Poker», технический отчет LCS / TR-125, Массачусетский технологический институт, апрель 1979 г.
2. Эндрю С. Яо, Протоколы для безопасных вычислений (расширенная аннотация)
3. Эндрю Чи-Чи Яо: Как создавать и обмениваться секретами (расширенное резюме). FOCS 1986: 162-167 [1]
4. Одед Гольдрайх, Сильвио Микали, Ави Вигдерсон: Как играть в любую мысленную игру или Теорема полноты для протоколов с честным большинством. STOC 1987: 218-229. [2]
5. Цви Галил, Стюарт Хабер, Моти Юнг: Криптографические вычисления: безопасные отказоустойчивые протоколы и модель открытого ключа. КРИПТО 1987: 135-155[3]
6. Дэвид Чаум, Иван Дамгард, Йерун ван де Грааф: Многосторонние вычисления, обеспечивающие конфиденциальность ввода каждой стороны и правильность результата. 87-119 [4]
7. Джо Килиан: Основание криптографии на забвении передачи. STOC 1988: 20-31 [5]
8. Д. Чаум, К. Крепо и И. Дамгард. «Многосторонние безоговорочно безопасные протоколы». Stoc 1988.
9. Майкл Бен-Ор, Шафи Голдвассер, Ави Вигдерсон: Теоремы полноты для некриптографических отказоустойчивых распределенных вычислений (расширенная аннотация). STOC 1988: 1-10
10. Таль Рабин, Майкл Бен-Ор: проверяемые протоколы совместного использования секретов и многосторонние протоколы с честным большинством (Расширенная аннотация). STOC 1989: 73-85 [6]
11. Дэнни Долев, Синтия Дворк, Орли Ваартс, Моти Юнг: Совершенно безопасная передача сообщений. J. ACM 40 (1): 17-47 (1993).[7]
12. Рафаил Островский, Моти Юнг: Как противостоять мобильным вирусным атакам. PODC 1991. С. 51-59. [8]
13. Клаудио Орланди: Полезны ли многосторонние вычисления на практике?, ICASSP 2011
14. Питер Богетофт, Дэн Лунд Кристенсен, Иван Дамгард, Мартин Гейслер, Томас Якобсен, Миккель Кройгаард, Янус Дам Нильсен, Йеспер Буус Нильсен, Курт Нильсе, Якоб Пагтер, Майкл Шварцбах и Томас Тофт (2008). «Многосторонние вычисления становятся реальностью». Архив криптологии ePrint (Отчет 2008/068).
15. Моти Юнг: От ментального покера к основному бизнесу: зачем и как развертывать протоколы безопасных вычислений? Конференция ACM по компьютерной и коммуникационной безопасности 2015: 1-2https://dl.acm.org/citation.cfm?doid=2810103.2812701
16. Майкл Бакес, Биргит Пфицманн и Майкл Вайднер. "Общая теорема композиции для безопасных реактивных систем. »В конференции по теории криптографии, стр. 336-354. Springer, Berlin, Heidelberg, 2004.
17. Y. Aumann & Y. Lindell. «Защита от тайных противников». TCC 2007.
18. Эндрю С. Яо, «Как генерировать секреты и обмениваться ими», Материалы 27-го ежегодного симпозиума по основам информатики SFCS '86, стр. 162–167, 1986.
19. Бен-Ор, Майкл; Гольдвассер, Шафи; Вигдерсон, Ави (1 января 1988 г.). Теоремы полноты для некриптографических отказоустойчивых распределенных вычислений. ACM. С. 1–10. Дои:10.1145/62212.62213. ISBN  978-0897912648. S2CID  207554159.
20. I. Дамгард, В. Пастро, Н. Смарт и С. Закариас, "Многосторонние вычисления на основе гомоморфного шифрования", Crypto 2012, т. Springer LNCS 7417, стр. 643-662, 2012.
21. Иддо Бентов, Ранджит Кумаресан (2014). «Как использовать биткойн для разработки честных протоколов» (PDF). Криптология и печать (129): 1–38. Получено 9 октября 2014.
22. А. Бен-Дэвид, Н. Нисан и Б. Пинкас, «FairplayMP: система для безопасных многосторонних вычислений», ACM CCS 2008, стр. 257–266, 2008.
23. Б. Пинкас, Т. Шнайдер, Н. Смарт и С. Уильямс, «Безопасные двусторонние вычисления практичны», Asiacrypt 2009, т. Springer LNCS 5912, стр. 250–267, 2009 г.
24. Ю. Линделл и Б. Пинкас, «Эффективный протокол для безопасных двусторонних вычислений в присутствии злоумышленников», Eurocrypt 2007, vol. Springer LNCS 4515, стр. 52-78, 2007.
25. Ю. Линделл, «Протоколы быстрого выбора для злонамеренных и скрытых злоумышленников», Crypto 2013, vol. Springer LNCS 8043, стр. 1-17, 2013.
26. Б. Кройтер, а. Шале и Ч.-Х. Шен, "Миллиард шлюзов безопасных вычислений со злоумышленниками", Симпозиум по безопасности USENIX, 2012 г., стр. 285–300, 2012 г.
27. А. Шелат и Ч.-Х. Шен, «Быстрые двусторонние безопасные вычисления с минимальными допущениями», ACM CCS 2013, стр. 523–534, 2013.
28. Т. Фредериксен и Дж. Нильсен, «Быстрые и злонамеренно защищенные двусторонние вычисления с использованием графического процессора», ACNS 2013, vol. Springer LNCS 7954, стр. 339–356, 2013.
29. Ю. Хуанг, Дж. Кац и Д. Эванс, "Эффективные безопасные двухсторонние вычисления с использованием симметричного выбора и вырезания", CRYPTO, т. Springer LNCS 8043, стр. 18-35, 2013.

внешние ссылки

• Простое описание проблемы миллионера
• Ссылки Хельгера Липмаа о многосторонних вычислениях
• Ник Сабо, "Протоколы Бога" на Wayback Machine (архивировано 30 декабря 2006 г.)
• EMP-инструментарий - Эффективный набор инструментов для многосторонних вычислений. Включает реализацию основных примитивов MPC, а также протоколов с получестной безопасностью и вредоносной безопасностью.
• Безопасные распределенные решатели CSP (DisCSP) - веб-приложение с апплетом-интерпретатором для разработки и запуска собственных полноценных безопасных многосторонних вычислений (на основе декларативного языка SMC). Использует безопасное вычисление арифметических схем и смешанные сети.
• VMCrypt Библиотека Java для масштабируемых безопасных вычислений. Лиор Малка.
• Проект Fairplay - Включает программный пакет для безопасных двухсторонних вычислений, где функция определяется с использованием языка описания функций высокого уровня и оценивается с использованием протокола Yao для безопасной оценки логических схем.
• Проект SIMAP; Безопасное управление и обработка информации (SIMAP) - это проект, спонсируемый Датским национальным исследовательским агентством, направленный на внедрение безопасных многосторонних вычислений.
• Безопасный язык многосторонних вычислений - проект по разработке «предметно-ориентированного языка программирования для безопасных многосторонних вычислений» и связанной с ним криптографической среды выполнения.
• VIFF: виртуальная идеальная функциональная структура - Платформа для асинхронных многосторонних вычислений (код доступен под LGPL ). Предлагает арифметические операции с секретными общими значениями, включая безопасное сравнение.
• MPyC: Безопасные многосторонние вычисления в Python (и Блокноты Jupyter ) - Пакет с открытым исходным кодом для MPC, использующий настраиваемый тип сопрограмм Python, поддерживающий расширенные приложения, такие как деревья решений ID3, линейное программирование, нейронные сети CNN / MLP, AES, односторонние хэш-цепочки и многие другие. Запущен в мае 2018 года.
• SCALE-MAMBA MPC: алгоритмы безопасных вычислений от LEuven - Платформа для различных протоколов MPC, включая семейство SPDZ (код доступен под BSD ). Предлагает арифметические операции с секретными общими значениями, включая безопасное сравнение и поддержку арифметики с фиксированной и плавающей запятой.
• Sharemind: анализируйте конфиденциальные данные без ущерба для конфиденциальности - Распределенная виртуальная машина с возможностью выполнять операции с сохранением конфиденциальности. Имеет сохраняющий конфиденциальность язык программирования для инструментов интеллектуального анализа данных. Включает инструменты разработчика.
• MPCLib: библиотека многосторонних вычислений - Библиотека, написанная на C # и C ++, которая реализует несколько строительных блоков, необходимых для реализации безопасных протоколов многосторонних вычислений. MPCLib имеет механизм моделирования дискретных событий, который можно использовать для моделирования протоколов MPC в виртуальных сетях.
• Виртуальные вечеринки в SMC Протокол для виртуальных сторон в SMC (безопасные многосторонние вычисления)
• Реализация MPC на основе Java Реализация протокола MPC на основе Java, основанная на теореме Michael.B, Shafi.G и Avi.W («Теоремы полноты для некриптографических отказоустойчивых распределенных вычислений») с кодовым алгоритмом исправления ошибок Welch-Berlekamp для кодов BCH. Поддерживает несколько игроков и идентификацию «читеров» по ​​византийскому протоколу. Авторы: Эрез Алон, Дорон Фридланд и Яэль Смит.
• СЕПИЯ Библиотека java для SMC с использованием секретного доступа. Базовые операции оптимизированы для большого количества параллельных вызовов (код доступен под LGPL ).
• Введение в SMC на GitHub
• Myst Project - Аплет JavaCard, реализующий безопасное многостороннее создание ключей, подпись и дешифрование.
• Основная библиография Безопасные многосторонние вычисления