Безопасное многостороннее вычисление (также известное как безопасное вычисление , многостороннее вычисление (MPC) или вычисление с сохранением конфиденциальности ) - это подполе криптографии с целью создания методов, позволяющих сторонам совместно вычислять функцию над своими входными данными, сохраняя при этом те входы частные. В отличие от традиционных криптографических задач, где криптография обеспечивает безопасность и целостность связи или хранения, а противник находится за пределами системы участников (перехватчик на отправителе и получателе), криптография в этой модели защищает конфиденциальность участников друг от друга.
Основа для безопасных многосторонних вычислений началась в конце 1970-х годов с работы над ментальным покером, криптографической работы, которая имитирует игровые / вычислительные задачи на расстоянии без использования доверенной третьей стороны. Обратите внимание, что традиционно криптография заключалась в сокрытии контента, в то время как этот новый тип вычислений и протокола заключается в сокрытии частичной информации о данных при вычислениях с данными из многих источников и правильном создании выходных данных.
Протоколы специального назначения для конкретных задач появились в конце 1970-х годов. [1] Позже безопасное вычисление было официально представлено как безопасное двухстороннее вычисление (2PC) в 1982 году (для так называемой проблемы миллионеров , конкретной проблемы, которая является логическим предикатом) и в целом (для любых возможных вычислений) в 1986 году Эндрю Яо . [2] [3]Эта область также называется оценкой функции безопасности (SFE). За двухпартийным случаем последовало обобщение на многопартийность Голдрайхом, Микали и Вигдерсоном. Вычисления основаны на секретном совместном использовании всех входных данных и доказательствах с нулевым разглашением для потенциально злонамеренного случая, когда большинство честных игроков в случае злонамеренного противника заверяют, что плохое поведение обнаружено, и вычисления продолжаются с устранением нечестного человека или его ввод обнаружен. В этой работе была предложена очень простая общая схема, которой должны следовать практически все будущие многосторонние протоколы для безопасных вычислений. [4]В этой работе был представлен подход, известный как парадигма GMW, для компиляции протокола многосторонних вычислений, защищенного от получестных злоумышленников, в протокол, защищенный от злонамеренных злоумышленников. За этой работой последовал первый надежный безопасный протокол, который любезно допускает ошибочное поведение, не раскрывая чьи-либо выходные данные, посредством работы, которая изобрела для этой цели часто используемую «идею совместного использования» [5] и протокол, позволяющий одной из сторон скрывать его ввод безоговорочно. [6] Парадигма GMW в течение многих лет считалась неэффективной из-за огромных накладных расходов, которые она вносила в базовый протокол. Однако показано, что можно достичь эффективных протоколов [7]и это делает это направление исследований еще более интересным с практической точки зрения. Приведенные выше результаты относятся к модели, в которой злоумышленник ограничен вычислениями за полиномиальное время и наблюдает за всеми коммуникациями, поэтому модель называется "вычислительной моделью". Кроме того, было показано , что протокол передачи данных не обращает внимания на эти задачи. [8] Приведенные выше результаты показали, что с помощью описанных выше вариантов можно достичь безопасных вычислений, когда большинство пользователей честны.
Следующим вопросом, который нужно было решить, был случай защищенных каналов связи, когда двухточечная связь недоступна для противника; в этом случае было показано, что решения могут быть достигнуты с использованием до 1/3 сторон, которые ведут себя некорректно и злонамеренно, и в решениях не используются криптографические инструменты (поскольку доступна безопасная связь). [9] [10] Добавление широковещательного канала позволяет системе выдерживать до 1/2 меньшинства некорректного поведения [11], в то время как ограничения связности графа связи были исследованы в книге «Совершенно безопасная передача сообщений». [12]
С годами концепция многосторонних протоколов общего назначения стала плодородной областью для исследования основных и общих свойств проблем протокола, таких как универсальная компонуемость или мобильный злоумышленник, как при активном совместном использовании секретов . [13]
С конца 2000-х годов и, конечно же, с 2010 года и далее, область протоколов общего назначения переместилась в сторону повышения эффективности протоколов с учетом практических приложений. Были предложены все более эффективные протоколы для MPC, и теперь MPC можно рассматривать как практическое решение различных реальных проблем (особенно тех, которые требуют только линейного разделения секретов и, в основном, локальных операций на общих ресурсах с небольшим взаимодействием между сторонами. ), такие как распределенное голосование, частные торги и аукционы, совместное использование подписи или функции дешифрования и поиск частной информации . [14] Первое крупномасштабное и практическое применение многосторонних вычислений (продемонстрированное на реальной проблеме аукциона) имело место в Дании в январе 2008 года.[15] Очевидно, что необходимы как теоретические понятия и исследования, так и прикладные конструкции (например, условия для переноса MPC в часть повседневного бизнеса были поддержаны и представлены в [16] ).
В MPC, заданного числа участников, р 1 , р 2 , ..., р Н , у каждого есть личные данные , соответственно , d 1 , d 2 , ..., d N . Участники хотят вычислить значение публичной функции для этих частных данных: F (d 1 , d 2 , ..., d N ), сохраняя при этом свои собственные входные данные в секрете.
Например, предположим, что у нас есть три стороны, Алиса, Боб и Чарли, с соответствующими входными данными x, y и z, обозначающими их зарплаты. Они хотят узнать самую высокую из трех зарплат, не раскрывая друг другу, сколько зарабатывает каждый из них. Математически это означает, что они вычисляют:
Если бы была какая-то доверенная сторонняя сторона (скажем, у них был общий друг Тони, который, как они знали, мог хранить секреты), каждый из них мог бы сообщить свою зарплату Тони, он мог бы вычислить максимум и сообщить это число всем им. Цель MPC - разработать протокол, в котором, обмениваясь сообщениями только друг с другом, Алиса, Боб и Чарли все еще могут изучать F (x, y, z), не раскрывая, кто что делает, и не полагаясь на Тони. Они не должны узнавать больше, участвуя в своем протоколе, чем они узнали бы, взаимодействуя с неподкупным, абсолютно заслуживающим доверия Тони.
В частности, все, что стороны могут узнать, - это то, что они могут узнать из результатов и своих собственных входов. Итак, в приведенном выше примере, если выходное значение - z , то Чарли узнает, что его z является максимальным значением, тогда как Алиса и Боб узнают (если x , y и z различны), что их вход не равен максимуму, и что удерживаемый максимум равен z . Базовый сценарий можно легко обобщить на случай, когда стороны имеют несколько входов и выходов, а функция выдает разные значения разным сторонам.
Неформально говоря, основными свойствами, которые стремится обеспечить протокол многосторонних вычислений, являются:
Существует широкий спектр практических приложений, варьирующихся от простых задач, таких как подбрасывание монеты, до более сложных, таких как электронные аукционы (например, расчет рыночной клиринговой цены), электронное голосование или интеллектуальный анализ данных с сохранением конфиденциальности. Классическим примером является проблема миллионеров: два миллионера хотят знать, кто богаче, таким образом, чтобы ни один из них не узнал чистую стоимость активов другого. Решением этой ситуации, по сути, является безопасная оценка функции сравнения.
Чтобы быть эффективным, протокол многосторонних вычислений должен быть безопасным. В современной криптографии безопасность протокола связана с доказательством безопасности. Доказательство безопасности - это математическое доказательство, в котором безопасность протокола сводится к безопасности его базовых примитивов. Тем не менее, не всегда возможно формализовать проверку безопасности криптографического протокола на основе знания стороны и правильности протокола. Для протоколов MPC среда, в которой работает протокол, связана с парадигмой реального / идеального мира. [17]Нельзя сказать, что стороны ничего не узнают, так как им нужно узнать результат операции, а результат зависит от входов. Кроме того, правильность вывода не гарантируется, поскольку правильность вывода зависит от входов сторон, и следует предполагать, что входы повреждены.
Парадигма реального мира / идеального мира утверждает два мира: (i) В модели идеального мира существует неподкупная доверенная сторона, которой каждый участник протокола отправляет свои входные данные. Эта доверенная сторона вычисляет функцию самостоятельно и отправляет каждой стороне соответствующий результат. (ii) Напротив, в реальной модели нет доверенной стороны, и все стороны могут обмениваться сообщениями друг с другом. Протокол считается безопасным, если можно узнать о частных входах каждой стороны в реальном мире не больше, чем можно узнать в идеальном мире. В идеальном мире между сторонами не происходит обмена сообщениями, поэтому обмен сообщениями в реальном мире не может раскрыть какую-либо секретную информацию.
Парадигма реального мира / идеального мира обеспечивает простую абстракцию сложностей MPC, позволяющую создавать приложение под предлогом, что протокол MPC в его ядре на самом деле является идеальным исполнением. Если приложение является безопасным в идеальном случае, оно также будет безопасным, если вместо него будет запущен реальный протокол.
Требования безопасности к протоколу MPC строги. Тем не менее, в 1987 году было продемонстрировано, что любая функция может быть надежно вычислена с защитой от злоумышленников [4] и других начальных работ, упомянутых ранее. Несмотря на эти публикации, MPC не был разработан для того, чтобы быть достаточно эффективным для практического использования в то время. Безоговорочно или теоретически безопасный протокол MPC тесно связан с проблемой совместного использования секрета , а точнее - проверяемого совместного использования секрета (VSS), который многие защищенные протоколы MPC используют против активных злоумышленников.
В отличие от традиционных криптографических приложений, таких как шифрование или подпись, следует предполагать, что противник в протоколе MPC является одним из игроков, вовлеченных в систему (или контролирующих внутренние стороны). Эта коррумпированная сторона или стороны могут вступить в сговор с целью нарушения безопасности протокола. Позвольте быть количество сторон в протоколе и количество сторон, которые могут быть состязательными. Протоколы и решения для случая (т.е. когда предполагается честное большинство) отличаются от тех, в которых такое предположение не делается. Этот последний случай включает в себя важный случай двухсторонних вычислений, когда один из участников может быть поврежден, и общий случай, когда неограниченное количество участников повреждено и вступает в сговор, чтобы атаковать честных участников.
Противников, с которыми сталкиваются различные протоколы, можно разделить на категории в зависимости от того, насколько они готовы отклониться от протокола. По сути, существует два типа противников, каждый из которых приводит к разным формам безопасности (и каждый подходит для разных сценариев реального мира):
Защита от активных противников обычно приводит к снижению эффективности, что приводит к скрытой безопасности [18].расслабленная форма активной безопасности. Скрытая система безопасности фиксирует более реалистичные ситуации, когда активные противники готовы обмануть, но только если их не поймают. Например, может быть нанесен ущерб их репутации, что помешает дальнейшему сотрудничеству с другими честными сторонами. Таким образом, протоколы, которые являются скрыто защищенными, предоставляют механизмы, гарантирующие, что если некоторые из сторон не будут следовать инструкциям, это будет замечено с высокой вероятностью, скажем, 75% или 90%. В некотором смысле скрытые противники - это активные противники, которые вынуждены действовать пассивно из-за внешних не криптографических (например, деловых) проблем. Этот механизм устанавливает мост между обеими моделями в надежде найти протоколы, которые на практике будут достаточно эффективными и безопасными.
Как и многие криптографические протоколы , безопасность протокола MPC может зависеть от различных допущений:
Набор честных сторон, которые могут выполнять вычислительную задачу, связан с концепцией структуры доступа . Структуры противника могут быть статическими, когда противник выбирает своих жертв до начала многосторонних вычислений, или динамическими, когда он выбирает своих жертв в ходе выполнения многосторонних вычислений, что усложняет защиту. Противоборствующая структура может быть определена как пороговая структура или как более сложная структура. В пороговой структуре злоумышленник может повредить или прочитать память ряда участников до некоторого порога. Между тем, в сложной структуре он может влиять на определенные заранее определенные подмножества участников, моделируя различные возможные сговоры.
Между протоколами, предложенными для двухсторонних вычислений (2PC) и многосторонних вычислений (MPC), есть существенные различия. Кроме того, часто для важных протоколов специального назначения необходимо разработать специализированный протокол, который отличается от общих протоколов (голосование, аукционы, платежи и т. Д.).
Двухсторонняя настройка особенно интересна не только с точки зрения приложений, но и потому, что в двухсторонней настройке могут применяться специальные методы, которые не применяются в многостороннем случае. Действительно, безопасное многостороннее вычисление (фактически ограниченный случай оценки безопасной функции, когда оценивается только одна функция) впервые было представлено в двухсторонней настройке. Оригинальная работа часто цитируется как взятая из одной из двух статей Яо; [19] хотя документы на самом деле не содержат того, что сейчас известно как протокол искаженных схем Яо .
Базовый протокол Yao защищен от получестных злоумышленников и чрезвычайно эффективен с точки зрения количества раундов, которое является постоянным и не зависит от оцениваемой целевой функции. Функция рассматривается как логическая схема с двоичными входами фиксированной длины. Логическая схема - это набор вентилей, соединенных тремя разными типами проводов: проводами входа схемы, проводами вывода схемы и промежуточными проводами. Каждый вентиль получает два входных провода и один выходной провод, который может быть разветвлен (то есть проходить к нескольким воротам на следующем уровне). Простая оценка схемы выполняется путем оценки каждого элемента по очереди; предполагая, что ворота были упорядочены топологически. Элемент представлен в виде таблицы истинности, так что для каждой возможной пары битов (исходящих от входных проводов)вентиль) таблица назначает уникальный выходной бит; что является значением выходного провода ворот. Результатами оценки являются биты, полученные в выходных проводах схемы.
Яо объяснил, как исказить схему (скрыть ее структуру), чтобы две стороны, отправитель и получатель, могли узнать выход схемы и ничего больше. На высоком уровне отправитель подготавливает искаженную схему и отправляет ее получателю, который не обращает внимания на схему, изучая кодировки, соответствующие как его выходу, так и выходу отправителя. Затем он просто отправляет обратно кодировки отправителя, позволяя отправителю вычислить свою часть вывода. Отправитель отправляет отображение кодировок выходных данных получателя в биты получателю, позволяя получателю получить их выходные данные.
Более подробно искаженная схема вычисляется следующим образом. Основным ингредиентом является схема симметричного шифрования с двойным ключом. Для данного элемента схемы каждое возможное значение его входных проводов (0 или 1) кодируется случайным числом (меткой). Значения, полученные в результате оценки логического элемента для каждой из четырех возможных пар входных битов, также заменяются случайными метками. Искаженная таблица истинности логического элемента состоит из шифрования каждой выходной метки с использованием ее входных меток в качестве ключей. Положение этих четырех шифров в таблице истинности рандомизировано, поэтому информация о шлюзе не просачивается.
Чтобы правильно оценить каждый искаженный шлюз, схема шифрования имеет следующие два свойства. Во-первых, диапазоны функции шифрования под любыми двумя разными ключами не пересекаются (с подавляющей вероятностью). Второе свойство говорит о том, что можно эффективно проверить, был ли данный зашифрованный текст зашифрован с использованием данного ключа. С этими двумя свойствами приемник, после получения меток для всех входных проводов схемы, может оценить каждый вентиль, сначала выяснив, какой из четырех зашифрованных текстов был зашифрован с его ключами меток, а затем расшифровав, чтобы получить метку выходного провода. . Это делается незаметно, поскольку все, что получатель узнает во время оценки, - это кодирование битов.
Входные биты отправителя (т. Е. Создателей схемы) могут быть просто отправлены в виде кодирования оценщику; в то время как кодирование получателя (т. е. оценщиков цепей), соответствующее его входным битам, получается с помощью протокола Oblivious Transfer (OT) « 1 из 2» . Протокол OT 1-из-2 позволяет отправителю, обладающему двумя значениями C1 и C2, отправить то, которое запрошено получателем (значение ba в {1,2}) таким образом, чтобы отправитель не знает, какое значение было передано, а получатель узнает только запрошенное значение.
Если кто-то рассматривает злонамеренных злоумышленников, необходимо предоставить дополнительные механизмы для обеспечения правильного поведения обеих сторон. По конструкции легко обеспечить безопасность отправителя, если протокол OT уже защищен от злонамеренного злоумышленника, поскольку все, что может сделать получатель, - это оценить искаженную схему, которая не сможет достичь выходных проводов схемы, если он отклонится от инструкций. . Совершенно иная ситуация со стороны отправителя. Например, он может послать неверную искаженную схему, вычисляющую функцию, раскрывающую вход получателя. Это означало бы, что конфиденциальность больше не сохраняется, но поскольку схема искажена, приемник не сможет это обнаружить. Тем не мение,можно эффективно применять доказательства с нулевым разглашением, чтобы сделать этот протокол безопасным от злонамеренных злоумышленников с небольшими накладными расходами по сравнению с получестным протоколом.[7]
Большинство протоколов MPC, в отличие от протоколов 2PC, особенно при безусловной настройке частных каналов, используют совместное использование секретов. В методах, основанных на совместном использовании секретов, стороны не играют особых ролей (как в Яо - создателя и оценщика). Вместо этого данные, связанные с каждым проводом, распределяются между сторонами, а затем используется протокол для оценки каждого шлюза. Функция теперь определяется как «схема» над конечным полем, в отличие от двоичных схем, используемых для Яо. Такая схема называется арифметической схемой в литературе и состоит из «вентилей» сложения и умножения, в которых оперируемые значения определены над конечным полем.
Разделение секрета позволяет распределить секрет между несколькими сторонами, распределяя акции между каждой стороной. Обычно используются два типа схем разделения секрета; Разделение секретов Шамира и дополнительное разделение секретов. В обоих случаях доли являются случайными элементами конечного поля, которые составляют секрет в поле; интуитивно безопасность достигается, потому что любой неквалифицированный набор акций выглядит случайно распределенным.
Схемы совместного использования секрета могут допускать, чтобы противник контролировал до t сторон из общего числа n сторон, где t варьируется в зависимости от схемы, противник может быть пассивным или активным, и различные предположения делаются относительно силы противника. Схема совместного использования секрета Shamir защищена от пассивного противника, когда и активного противника, когда достигается теоретико-информационная безопасность, а это означает, что даже если противник имеет неограниченную вычислительную мощность, он не может узнать какую-либо информацию о секрете, лежащем в основе доли. Протокол BGW, [20]который определяет, как вычислять сложение и умножение на секретных долях, часто используется для вычисления функций с секретными долями Шамира. Аддитивные схемы совместного использования секретов могут допускать, чтобы злоумышленник контролировал все стороны, кроме одной, то есть при сохранении защиты от пассивного и активного противника с неограниченной вычислительной мощностью. Некоторые протоколы требуют фазы настройки, которая может быть защищена только от вычислительно ограниченного противника.
В ряде систем реализованы различные формы MPC со схемами разделения секрета. Самым популярным из них является SPDZ [21], который реализует MPC с дополнительными секретными разделами и защищен от активных злоумышленников.
В 2014 году для сети Биткойн или для честной лотереи была описана «модель справедливости в безопасных вычислениях, в которой противная сторона, которая прерывает получение выходных данных, вынуждена платить заранее определенный денежный штраф» . [22]
За последние годы в системах 2PC и MPC было сделано много успехов.
Одна из основных проблем при работе с протоколами на основе Yao заключается в том, что функция, которая должна быть безопасно оценена (которая может быть произвольной программой), должна быть представлена в виде схемы, обычно состоящей из вентилей XOR и AND. Поскольку большинство реальных программ содержат циклы и сложные структуры данных, это весьма нетривиальная задача. Система Fairplay [23]был первым инструментом, предназначенным для решения этой проблемы. Fairplay состоит из двух основных компонентов. Первый из них - это компилятор, позволяющий пользователям писать программы на простом языке высокого уровня и выводить эти программы в виде логической схемы. Затем второй компонент может искажать схему и выполнять протокол для безопасной оценки искаженной схемы. Помимо двухсторонних вычислений на основе протокола Яо, Fairplay также может выполнять многосторонние протоколы. Это делается с использованием протокола BMR [23], который расширяет пассивно защищенный протокол Yao на активный случай.
За годы, прошедшие после введения Fairplay, в базовый протокол Yao было внесено множество улучшений в виде как повышения эффективности, так и методов активной безопасности. К ним относятся такие методы, как метод свободного XOR, который позволяет значительно упростить оценку вентилей XOR, и сокращение искаженных строк, уменьшая размер искаженных таблиц с двумя входами на 25%. [24]
Подход, который до сих пор кажется наиболее плодотворным в обеспечении активной безопасности, исходит из комбинации техники искажения и парадигмы «вырезать и выбрать». Эта комбинация, кажется, делает конструкции более эффективными. Чтобы избежать вышеупомянутых проблем, связанных с нечестным поведением, многие искажения одной и той же схемы отправляются от конструктора к оценщику. Затем около половины из них (в зависимости от конкретного протокола) открываются для проверки согласованности, и если это так, подавляющее большинство закрытых с высокой вероятностью верны. Результатом является большинство голосов всех оценок. Обратите внимание, что здесь требуется большая часть вывода. Если есть разногласия по выходным данным, получатель знает, что отправитель жульничает, но он не может жаловаться, так как в противном случае это приведет к утечке информации на его входе.
Такой подход к активной безопасности был предложен Линделлом и Пинкасом. [25] Этот метод был реализован Pinkas et al. в 2009 году [24] это обеспечило первую активно защищенную двухстороннюю оценку схемы Advanced Encryption Standard (AES), считающуюся очень сложной (состоящей из около 30 000 логических элементов AND и XOR), нетривиальной функцией (также с некоторыми потенциальных приложений), на вычисление уходит около 20 минут и требуется 160 схем для получения вероятности обмана.
Поскольку оцениваются многие схемы, стороны (включая получателя) должны фиксировать свои входные данные, чтобы гарантировать, что во всех итерациях используются одни и те же значения. Эксперименты Пинкаса и др. Сообщается [24], что узкое место протокола заключается в проверках согласованности. Им пришлось отправить по сети около 6 553 600 обязательств с различными ценностями, чтобы оценить схему AES. В недавних результатах [26] эффективность активно защищенных реализаций на основе Yao была улучшена еще больше, потребовалось всего 40 схем и гораздо меньше обязательств для получения вероятности обмана. Улучшения проистекают из новых методологий для выполнения выборки по переданным цепям.
В последнее время основное внимание уделялось высокопараллельным реализациям на основе искаженных схем, предназначенных для работы на процессорах с большим количеством ядер. Кройтер и др. [27] описывают реализацию, работающую на 512 ядрах мощного кластерного компьютера. Используя эти ресурсы, они могли оценить 4095-битное расстояние редактирования.функция, схема которой насчитывает почти 6 миллиардов вентилей. Для этого они разработали специальный, лучше оптимизированный компилятор схем, чем Fairplay, и несколько новых оптимизаций, таких как конвейерная обработка, при которой передача искаженной схемы по сети начинается, в то время как остальная часть схемы все еще генерируется. Время вычисления AES было сокращено до 1,4 секунды на блок в активном случае при использовании кластерной машины с 512 узлами и до 115 секунд при использовании одного узла. Шелат и Шен [28] улучшили это, используя обычное оборудование, до 0,52 секунды на блок. В той же статье сообщается о пропускной способности 21 блок в секунду, но с задержкой 48 секунд на блок.
Между тем, другая группа исследователей исследовала использование графических процессоров потребительского уровня для достижения аналогичных уровней параллелизма. [29]Они используют расширения OT и некоторые другие новые методы для разработки своего протокола, специфичного для графического процессора. Похоже, что этот подход обеспечивает сопоставимую эффективность с реализацией кластерных вычислений с использованием аналогичного количества ядер. Однако авторы сообщают только о реализации схемы AES, которая имеет около 50 000 вентилей. С другой стороны, необходимое здесь оборудование гораздо более доступно, поскольку подобные устройства уже можно найти на настольных компьютерах или игровых консолях многих людей. Авторы получают синхронизацию 2,7 секунды на блок AES на стандартном настольном компьютере со стандартным графическим процессором. Если они позволяют снизить уровень безопасности до уровня, похожего на скрытую безопасность, они получают время выполнения 0,30 секунды на блок AES. В корпусе пассивной безопасности есть отчеты об обработке цепей с 250 миллионами вентилей,и со скоростью 75 миллионов ворот в секунду.[30]