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

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

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

История

Протоколы специального назначения для конкретных задач появились в конце 1970-х годов. Позже безопасное вычисление было официально представлено как безопасное двухстороннее вычисление (2PC) в 1982 году (для так называемой проблемы миллионеров , конкретной проблемы, которая является логическим предикатом) и в целом (для любых возможных вычислений) в 1986 году. Эндрю Яо . Эта область также называется оценкой функции безопасности (SFE). За двухпартийным случаем последовало обобщение на многопартийность Голдрайхом, Микали и Вигдерсоном. Вычисления основаны на секретном совместном использовании всех входных данных и доказательствах с нулевым разглашением для потенциально злонамеренного случая, когда большинство честных игроков в случае злонамеренного противника заверяют, что плохое поведение обнаружено, и вычисления продолжаются с устранением нечестного человека или его ввод обнаружен. В этой работе была предложена очень простая общая схема, которой должны следовать практически все будущие многосторонние протоколы для безопасных вычислений. В этой работе был представлен подход, известный как парадигма GMW, для компиляции протокола многосторонних вычислений, защищенного от получестных злоумышленников, в протокол, защищенный от злонамеренных злоумышленников. За этой работой последовал первый надежный безопасный протокол, который любезно допускает ошибочное поведение, не раскрывая чьи-либо выходные данные, посредством работы, которая изобрела для этой цели часто используемую `` идею доли общих ресурсов '' и протокол, который позволяет одной из сторон безоговорочно скрывать свои входные данные. . Парадигма GMW в течение многих лет считалась неэффективной из-за огромных накладных расходов, которые она вносила в базовый протокол. Однако показано, что можно достичь эффективных протоколов, и это делает это направление исследований еще более интересным с практической точки зрения. Приведенные выше результаты относятся к модели, в которой злоумышленник ограничен вычислениями за полиномиальное время и наблюдает за всеми коммуникациями, и поэтому модель называется "вычислительной моделью". Кроме того, было показано , что протокол передачи данных без внимания подходит для этих задач. Приведенные выше результаты показали, что с помощью описанных выше вариантов можно достичь безопасных вычислений, когда большинство пользователей честны.

Следующим вопросом, который нужно было решить, был случай защищенных каналов связи, где двухточечная связь недоступна для противника; в этом случае было показано, что решения могут быть достигнуты с использованием до 1/3 сторон, которые ведут себя некорректно и злонамеренно, и в решениях не используются криптографические инструменты (поскольку доступна безопасная связь). Добавление широковещательного канала позволяет системе выдерживать до 1/2 меньшинства некорректного поведения, тогда как ограничения связности в графе связи были исследованы в книге Perfectly Secure Message Transmission.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Протоколы

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

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

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

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

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

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

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

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

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

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

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

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

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

В ряде систем реализованы различные формы MPC со схемами разделения секрета. Самым популярным является SPDZ, который реализует MPC с дополнительными секретными разделами и защищен от активных злоумышленников.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Простое описание проблемы миллионера
Ссылки Хельгера Липмаа о многопартийных вычислениях
Ник Сабо, «Протоколы Бога» в Wayback Machine (архив 30 декабря 2006 г.)
EMP-toolkit - эффективный инструментарий многосторонних вычислений. Включает реализацию основных примитивов MPC, а также протоколов с получестной безопасностью и вредоносной безопасностью.
Безопасные распределенные решатели CSP (DisCSP) - веб-приложение с апплетом-интерпретатором для разработки и запуска собственных полноценных безопасных многосторонних вычислений (на основе декларативного языка SMC). Использует безопасное вычисление арифметических схем и смешанные сети.
VMCrypt Библиотека Java для масштабируемых безопасных вычислений. Лиор Малка.
Проект Fairplay - включает пакет программного обеспечения для безопасных двусторонних вычислений, где функция определяется с использованием языка описания функций высокого уровня и оценивается с использованием протокола Yao для безопасной оценки логических схем.
Проект SIMAP ; Безопасное управление и обработка информации (SIMAP) - это проект, спонсируемый Датским национальным исследовательским агентством, направленный на внедрение безопасных многосторонних вычислений.
Secure Multiparty Computation Language - проект по разработке «предметно-ориентированного языка программирования для безопасных многосторонних вычислений» и связанной с ним криптографической среды выполнения.
VIFF: Virtual Ideal Functionality Framework - платформа для асинхронных многосторонних вычислений (код доступен в рамках 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 («Теоремы полноты для некриптографических отказоустойчивых распределенных вычислений») с кодом исправления ошибок Велча-Берлекампа. алгоритм для кодов BCH. Поддерживает несколько игроков и идентификацию «читеров» по византийскому протоколу. Авторы: Эрез Алон, Дорон Фридланд и Яэль Смит.
SEPIA Библиотека Java для SMC, использующая совместное использование секретов. Базовые операции оптимизированы для большого количества параллельных вызовов (код доступен под LGPL ).
Введение в SMC на GitHub
Myst Project - апплет JavaCard, реализующий безопасное многостороннее создание ключей, подпись и дешифрование.
Важная библиография Безопасные многосторонние вычисления

Languages

In other projects