Безопасные многосторонние вычисления

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

Основа безопасных многосторонних вычислений зародилась в конце 1970-х годов с работы над ментальным покером — криптографической работой, которая моделирует игровые/вычислительные задачи на расстоянии, не требуя доверенной третьей стороны. Традиционно криптография заключалась в сокрытии контента, тогда как этот новый тип вычислений и протокола заключается в сокрытии частичной информации о данных при вычислениях с данными из многих источников и правильном получении результатов. К концу 1980-х годов Майкл Бен-Ор, Шафи Голдвассер и Ави Вигдерсон , а также независимо Дэвид Чаум , Клод Крепо и Иван Дамгорд опубликовали статьи, показывающие, «как безопасно вычислить любую функцию в настройках безопасных каналов».

История

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

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

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

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

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

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

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

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

F(x, y, z) = max(x, y, 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 является одним из игроков, участвующих в системе (или контролирующих внутренние стороны). Эта коррумпированная сторона или стороны могут вступить в сговор с целью нарушения безопасности протокола. Позволять $n$ быть числом сторон в протоколе и $t$ количество сторон, которые могут быть враждебными. Протоколы и решения на случай $t<n/2$ (т.е. когда предполагается честное большинство) отличаются от тех, где такое предположение не делается. Этот последний случай включает в себя важный случай двухсторонних вычислений, когда один из участников может быть коррумпирован, и общий случай, когда неограниченное количество участников коррумпировано и вступают в сговор с целью нападения на честных участников.

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

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

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

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

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

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

Протоколы

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

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

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

См. также: Искаженная схема

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация безопасного многостороннего анализа данных вычислений.

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

Демонстрационные и производственные системы

Анализ	Хранители данных	Поставщик технологий	Год введения	Примечания	Все еще используется?
Отчет Бостонского совета по женской рабочей силе	Работодатели Бостона	Бостонский университет	2016
Наборы данных округа Аллегейни	Несколько наборов данных из разных окружных офисов	Галуа и Центр двухпартийной политики	2018

Библиотеки программного обеспечения

Имя	Разработчик	Год введения	Примечания	Все еще поддерживается?
SEPIA — безопасность посредством агрегирования частной информации
SCAPI — API безопасных вычислений
PALISADE — библиотека гомоморфного шифрования
MP-SPDZ — универсальная платформа для многосторонних вычислений.	CSIRO61 Данные	2018	40 вариантов протокола, упор на функциональность машинного обучения	По состоянию на 2023 год

См. также

• Частный перекрёсток
• Цифровая валюта
• Гомоморфное шифрование
• Протокол многостороннего справедливого обмена
• Не обращающий внимания трансфер
• Забывчивая псевдослучайная функция
• Вычислительная геометрия, сохраняющая конфиденциальность
• Проблема миллионеров Яо
• Технологии повышения конфиденциальности
• Дифференциальная конфиденциальность

Дальнейшее чтение

• VMCrypt — библиотека Java для масштабируемых безопасных вычислений. Лиор Малка.
• Введение в SMC Кристиан Зелински.
• SEPIA Java-библиотека для SMC, использующая общий доступ к секретам.
• MPCLib: библиотека многосторонних вычислений . Библиотека, написанная на C# и C++, которая реализует несколько строительных блоков, необходимых для реализации безопасных протоколов многосторонних вычислений.
• EMP-toolkit Инструментарий для эффективных многосторонних вычислений.
• Виртуальные вечеринки в SMC Протокол для виртуальных вечеринок в SMC.
• MPyC: безопасные многосторонние вычисления в Python (и блокнотах Jupyter ). Пакет с открытым исходным кодом для MPC, использующий настраиваемый тип сопрограмм Python.
• Протоколы Бога Ник Сабо (в архиве).
• Проект SIMAP ; Безопасное управление и обработка информации (SIMAP) — это проект, спонсируемый Датским национальным исследовательским агентством (в архиве).
• MPC с нуля: каждый может это сделать! Стивен Тонг.

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

• JavascriptMPC — JavascriptMPC Фреймворк golang MPC, который может компилировать файлы Javascript в искаженные схемы.
• Решатели Secure Distributed CSP (DisCSP) — веб-приложение с апплетом-интерпретатором для проектирования и запуска собственных полноценных безопасных многосторонних вычислений (на основе декларативного языка SMC). Использует безопасную арифметическую оценку схемы и микс-сети.
• Проект Fairplay — включает пакет программного обеспечения для безопасных двусторонних вычислений, в котором функция определяется с использованием языка описания функций высокого уровня и оценивается с использованием протокола Яо для безопасной оценки логических схем.
• Язык безопасных многосторонних вычислений — проект по разработке «предметно-ориентированного языка программирования для безопасных многосторонних вычислений» и связанной с ним криптографической среды выполнения.
• Myst Project — апплет JavaCard, реализующий безопасную многостороннюю генерацию, подпись и расшифровку ключей.