Применение MPC: пересечение частных множеств и машинное обучение

MPC превращает теорию в практику. Пересечение конфиденциальных множеств (PSI) и машинное обучение с сохранением конфиденциальности — два наиболее распространённых сегодня в промышленности применения MPC.

PSI: Алиса располагает множеством A, а Боб — множеством B. Они вычисляют A∩B, не узнавая элементы A\B или B\A. Метод используется Google и Apple для отслеживания контактов, обнаружения рекламного мошенничества и обмена сведениями об угрозах.

Хеширование обоих множеств и их сравнение небезопасны, если множества малы: злоумышленник перебирает все элементы. Безопасный PSI должен скрывать даже размер пересечения (или раскрывать только само пересечение).

Скрытая PRF (OPRF): Боб вычисляет PRF для элементов Алисы, не узнавая сами элементы. Алиса получает PRF(k, x) для каждого x∈A. Затем она сравнивает эти значения с заранее вычисленными Бобом PRF(k, y) для y∈B.

PSI на основе схем вычисляет пересечение (the intersection) внутри схемы MPC, позволяя выполнять дальнейшие вычисления над элементами пересечения, например суммировать суммы покупок, не раскрывая, какие элементы пересекаются.

PPML обучает модели или выполняет вывод на данных от нескольких сторон. Федеративное обучение сохраняет данные локально, а MPC идёт дальше: даже модель или агрегированные градиенты разделяются на секретные доли.

Протокол безопасной агрегации Google 2017 года: каждый client разделяет своё обновление градиента на секретные доли. Сервер восстанавливает только the сумму. Отдельные обновления никогда не раскрываются, даже серверу.

CrypTen (Facebook/Meta) и MOTION поддерживают запуск нейронных сетей в стиле PyTorch на входных данных, разделённых на секретные доли. Линейные слои требуют мало ресурсов, а нелинейности (ReLU) требуют преобразования из булевой арифметики в обычную арифметику.

ReLU(x) = max(0,x) требует сравнения x с 0 — нелинейной операции, не относящейся к арифметическим. Это выполняется с помощью схем с запутанными цепями или разложения на биты и составляет основную стоимость PPML.

Private Relay от Apple использует PSI. Meta применяет MPC для конфиденциального измерения эффективности рекламы. Протокол IETF PRIO, используемый в телеметрии Firefox, применяет статистику, агрегированную из секретных долей.

В PSI на основе OPRF какая сторона хранит ключ PRF и что узнаёт другая сторона?

PSI позволяет сторонам конфиденциально вычислять пересечение множеств с помощью OPRF. PSI на основе схем позволяет выполнять дальнейшие вычисления над данными пересечения. PPML использует MPC для агрегации при федеративном обучении и вывода модели на зашифрованных входных данных. ReLU — главное узкое место по стоимости PPML.