Безопасные многосторонние вычисления (MPC) — это ветвь криптографии. В отсутствие доверенной третьей стороны все еще возможно безопасно выполнять совместные вычисления данных и выводить результаты в соответствии с логикой общедоступных вычислений.
Даже если данные, вводимые участвующими сторонами, известны только им, они все равно могут получить желаемые результаты вычислений с помощью алгоритма шифрования, но исходные зашифрованные данные не могут быть выведены, что обеспечивает безопасность конфиденциальности.
MPC возникла из проблемы миллионеров, поднятой академиком Яо Цижи в 1982 году. С момента создания теории MPC было получено несколько технических ответвлений, включая запутанные схемы, совместное использование секрета, гомоморфное шифрование, непреднамеренную передачу, пересечение наборов конфиденциальности и дифференциальную конфиденциальность.
схема обфускации
Схема запутывания (обмен секретами, SS) также известна как схема шифрования Яо. Она была предложена профессором Яо Цижи в 1986 году, поэтому ее также называют схемой Яо.
Его ядро состоит в том, чтобы скомпилировать функцию безопасного вычисления в виде логической схемы и зашифровать саму схему. Есть две операции для запутанных цепей:
Один из них — сгенерировать запутанную схему, сначала сгенерировать логическую схему с определенной функцией, а затем на ее основе преобразовать логический элемент (истинное значение) в запутанный элемент (ложное значение) для создания запутанной схемы;
Другая операция называется операцией оценки, которая сначала создает запутанную схему, а затем использует запутанную схему для вычисления выходных данных.
Схема запутывания также может пониматься как криптографический протокол, который формирует безопасный вычислительный протокол на основе схемы запутывания и выводит многосторонний протокол безопасности из исходного двухстороннего протокола безопасности.
делиться секретами
Разделение секрета (SS) было предложено Шамиром и Блейкли в 1979 году. Алгоритм разделения секрета состоит в том, чтобы упростить чрезвычайно сложную схему до простой и эффективной математической идеи.
Его основная форма состоит в том, чтобы разделить каждое число на несколько чисел и распределить эти числа среди нескольких участников, и каждый участник может получить только часть исходных данных.
В результате восстановить реальные данные можно только путем объединения всех распределенных данных, что необходимо.
Из-за различных способов разделения секрета совместное использование секрета делится на совместное использование секрета на основе полиномиальной интерполяции и совместное использование секрета.
Аддитивный арифметический обмен секретами может выполнять линейные операции, а аддитивный логический обмен секретами может выполнять нелинейные операции, такие как сравнение величин.
Аддитивное совместное использование секретов требует только выполнения простых операций и имеет низкие вычислительные затраты, поэтому оно широко используется в MPC. Недостатком совместного использования секрета является то, что количество раундов взаимодействия связано с глубиной схемы.
непреднамеренная передача
Забывчивая передача (0T) была предложена Рабином в 1981 году. Отправитель сообщения имеет несколько сообщений, получатель может получить только одно из значений, а отправитель не знает информацию о выборе получателя.
Его производная технология, коррелированный забывчивый перенос (COT), может генерировать случайные числа с отношениями.
OT и COT являются важными криптографическими компонентами, которые могут передавать метки проводов для GC, генерировать соответствующие случайные числа для SS и реализовывать протокол MPC только с использованием технологии OT.
В процессе оптимизации производительности OT технология OT Extension вводит симметричное шифрование для снижения вычислительных издержек, а молчаливая технология OT Extension расширяет начальные числа случайных чисел локально, чтобы уменьшить коммуникационные издержки.
Гомоморфное шифрование
Концепция гомоморфного шифрования (HE) была предложена Ривестом и др. в 1978 г., что позволяет напрямую выполнять вычисления с зашифрованными данными без расшифровки.
В процессе разработки последовательно предлагались некоторые схемы гомоморфного шифрования и неглубокие схемы гомоморфного шифрования, пока Джентри не сконструировал первую полностью гомоморфную схему шифрования в 2009 году.
Преимущество гомоморфного шифрования заключается в том, что оно может разработать протокол MPC с лучшим числом раундов с наименьшими затратами на связь, а недостатком является то, что гомоморфизм умножения приведет к увеличению вычислительных затрат и затрат на хранение.
Дифференциальная конфиденциальность
Технология дифференциальной конфиденциальности (DP) — это новый метод криптографии, предложенный Dwork в 2006 году для решения проблемы утечки конфиденциальности базы данных.
Механизм заключается в добавлении шума определенного распределения к исходным данным или результатам расчетов, чтобы гарантировать, что каждый участник не сможет проанализировать, включен ли конкретный объект в набор данных через полученные данные.
Дифференциальная конфиденциальность включает локальную дифференциальную конфиденциальность и дифференциальную конфиденциальность результатов вычислений.
Локальная дифференциальная конфиденциальность относится к добавлению шума к данным перед агрегированием и расчетом, который используется в сценариях, когда сборщик данных не заслуживает доверия;
Дифференциальная конфиденциальность результатов вычислений означает добавление шума к окончательным результатам вычислений перед их публикацией.
Пересечение набора конфиденциальности
Пересечение частных множеств (PSI) — классическая проблема в области многосторонних безопасных вычислений.Она требует от участников совместного вычисления пересечения множеств нескольких участников без раскрытия локального множества друг другу.Раскрытие информации, отличной от пересечения любой вовлеченной стороне.
PSI — одна из ключевых технологий конфиденциальных вычислений и ключевая вспомогательная технология для вертикального федеративного обучения.
В сценарии вертикального федеративного обучения PSI также называется выравниванием выборки или заполнением базы данных, то есть каждый участник должен сначала найти пересечение между соответствующими наборами идентификаторов обучающей выборки.
Последующее продольное обучение объединенной модели выполняется на основе вычисленного пересечения идентификаторов обучающей выборки.
доказательство с нулевым разглашением
Доказательство с нулевым разглашением относится к вычислительной технологии, с помощью которой доказывающий может убедить проверяющего в правильности утверждения, не предоставляя проверяющему никакой полезной информации.
Принцип доказательств с нулевым разглашением заключается в построении многостороннего протокола, то есть серии шагов, которые необходимо предпринять нескольким вовлеченным сторонам для выполнения задачи, выполнив эти шаги.
Доказывающий доказывает верификатору и убеждает его, что он знает или обладает определенным сообщением, но процесс доказательства не может раскрыть никакой информации о проверенном сообщении верификатору.
резюме
В настоящее время наиболее типичным сценарием применения технологии MPC является машинное обучение с сохранением конфиденциальности (PPML).
С точки зрения применения алгоритма многосторонние безопасные вычисления широко используются в совместной статистике, совместных запросах, совместном моделировании, совместных сценариях, таких как прогнозирование, они также могут поддерживать общие вычислительные потребности пользовательской вычислительной логики.
Эта статья представляет собой обзор многосторонних безопасных вычислений. Далее будут представлены технические характеристики и способы использования технологии MPC для реализации решений PPML.
использованная литература
[1] Guo Juanjuan, Wang Qiongxiao и др. Применение безопасных многосторонних вычислительных машин в машинном обучении, Компьютерные исследования и разработки, 2021.06
[2] Альянс конфиденциальных вычислений, Белая книга по конфиденциальным вычислениям (2021 г.), 2021.07.