Безопасные многосторонние вычисления
- title
- Безопасные многосторонние вычисления
- type
- concept
- summary
- Криптографические протоколы, где n сторон вычисляют f(x₁,...,xₙ) без раскрытия входных данных; на выходе известен только результат
- tags
- cryptography, mpc
- sources
- stoffel-beaver-triples
- created
- 2026-05-10
- updated
- 2026-05-10
- lang
- ru
- translation_of
- secure-multiparty-computation
- source_updated
- 2026-05-10
- translated
- 2026-09-01
- translator
- lllm/antigravity/gemini-3.7-flash-medium
MPC - зонтичный термин для протоколов, в которых n сторон вычисляют f(x₁, ..., xₙ) так, что каждая сторона узнаёт только результат вычисления и ничего не узнаёт о входных данных остальных. Классический пример - задача миллионеров Яо (кто богаче, не раскрывая своих доходов); современные сценарии включают конфиденциальные аукционы, федеративную аналитику, пороговую подпись ECDSA и торговлю в dark pool'ах.
Преобладают два основных подхода к построению:
Замаскированные схемы (Garbled circuits, Yao 1986) вычисляют булеву схему вентиль за вентилем: одна сторона "зашумляет" таблицу истинности каждого вентиля, а вторая дешифрует её с помощью забывающего чтения (oblivious transfer). Изначально протокол был двухсторонним, затем его обобщили через протоколы семейства BMR/SPDZ. Лучше всего подходит для неглубоких схем; раундовая сложность константна относительно глубины схемы, но объём передаваемых данных растёт с увеличением размера схемы.
Схемы на основе разделения секрета (BGW 1988, GMW 1987) используют схемы secret-sharing, где сложение выполняется бесплатно, а для умножения применяются beaver-triples или снижение степени многочлена по BGW. Подходят для глубоких арифметических схем; раундовая сложность растёт с глубиной умножений, но объём работы на каждом раунде невелик.
Современные продакшен-стеки (SPDZ, MASCOT, MP-SPDZ, пороговые библиотеки на базе криптосистемы Paillier) объединяют офлайн-фазу генерации троек с онлайн-фазой вычислений. Офлайн-фаза ресурсоёмкая, но не зависит от входных данных; онлайн-фаза дешёвая и выполняется непосредственно во время обработки запроса. stoffel-mpc - один из проектов, предоставляющих этот паттерн в виде сервиса.
Модели нарушителя имеют значение: semi-honest (честный с любопытством) предполагает, что стороны следуют протоколу, но пытаются извлечь информацию из того, что видят; malicious (активный нарушитель) допускает произвольные отклонения от протокола. Большинство академических протоколов рассчитаны на модель semi-honest с опциональными расширениями на базе MAC для защиты от активного нарушителя (модель SPDZ с "dishonest majority", нечестным большинством).
Смежные, но другие концепции:
- Гомоморфное шифрование (FHE) позволяет одной стороне выполнять вычисления над зашифрованными данными другой стороны; MPC распределяет вычисления между участниками
- ZKP (доказательства с нулевым разглашением) доказывают истинность утверждений без раскрытия свидетелей (witnesses); могут комбинироваться с MPC для получения проверяемых результатов
- Дифференциальная приватность добавляет шум к результатам; ортогональна тому, были ли сами вычисления приватными
Ссылки: secret-sharing, beaver-triples, mpc-beaver-triples, post-quantum-cryptography.