Как вычислить сумму и рейтинг без раскрытия единого бита данных: безопасные многосторонние вычисления (MPC) и проблема миллионеров Яо

«Несколько онкологических центров хотят объединить геномные данные своих пациентов для проведения статистического исследования (GWAS), но законы о защите персональных данных (GDPR / HIPAA) категорически запрещают передавать за пределы клиники даже один байт исходных данных». «Конкурирующие коммерческие банки хотят совместно отслеживать межбанковские цепочки отмывания денег, не раскрывая друг другу списки клиентов и графы транзакций».

На первый взгляд это кажется логическим противоречием: чтобы вычислить функцию $f(x_1, x_2, \dots, x_n)$, разве не должна некая доверенная третья сторона (Trusted Third Party, TTP) сначала собрать все входные данные $x_i$ в открытом виде? Однако в конце 1980-х годов современная криптография доказала поразительную теорему: даже при полном отсутствии доверенной третьей стороны не доверяющие друг другу участники могут совместно вычислить любую вычислимую функцию $f(x_1, \dots, x_n)$ так, что каждый узнает точный результат, но никто не получит ни единого дополнительного бита информации о чужих секретных входах $x_i$.

Эта область называется безопасными многосторонними вычислениями (Secure Multi-Party Computation, MPC). В этой статье мы начнем с двух классических мысленных экспериментов и выведем два фундаментальных математических двигателя MPC: пороговое разделение секрета $(t, n)$ Ади Шамира (интерполяция Лагранжа, протокол BGW и мультипликативные тройки Бивера) и булев подход на основе забывчивой передачи ($\text{OT}_1^2$) Рабина и искаженных схем (Garbled Circuits) Яо.

1. Два парадоксальных мысленных эксперимента: «Средняя зарплата без начальника» и «Проблема миллионеров Яо»

1.1 Мысленный эксперимент 1: Как узнать среднюю зарплату троих, не раскрывая личных доходов

Трое инженеров $A, B$ и $C$ хотят узнать свою среднюю годовую зарплату $\bar{x} = \frac{x_A + x_B + x_C}{3}$, но никто из них не готов раскрыть свою индивидуальную зарплату $x_A, x_B$ или $x_C$ остальным. С помощью аддитивного разделения секрета (маскирования одноразовым блокнотом / One-Time Pad) они решают задачу без посредников:

Случайная маска и первый шепот ($A \to B$): Участники выбирают большое публичное число $M$ (например, $M = 10^9$). Инженер $A$ тайно генерирует равномерно распределенное случайное число $r \xleftarrow{\$} \mathbb{Z}_M$, прибавляет к нему свою зарплату $x_A$ и шепчет инженеру $B$ только величину $s_1 = (x_A + r) \bmod M$. Поскольку $r$ распределено равномерно в кольце $\mathbb{Z}_M$, сумма $s_1$ также распределена идеально равномерно независимо от значения $x_A$: по теореме Шеннона взаимная информация равна нулю ($I(X_A; S_1) = 0$). Инженер $B$ узнает ровно <strong>ноль бит</strong> о $x_A$.
Цепочка сложений ($B \to C \to A$): $B$ прибавляет свою зарплату $x_B$ и шепчет $s_2 = (x_A + x_B + r) \bmod M$ участнику $C$; $C$ прибавляет $x_C$ и сообщает $s_3 = (x_A + x_B + x_C + r) \bmod M$ обратно участнику $A$.
Снятие маски: $A$ вычитает свое случайное число $r$ по модулю $M$, получает точную сумму $S = x_A + x_B + x_C$ и объявляет среднее значение $\bar{x} = S / 3$.

[!NOTE] Почему необходимы минимум 3 участника ($n \ge 3$)? Если бы участников было всего двое ($A$ и $B$), то даже если бы неподкупный ангел сообщил им только среднее $\bar{x} = \frac{x_A + x_B}{2}$, $A$ мгновенно вычислил бы $x_B = 2\bar{x} - x_A$. Это свойство самой математической функции, а не уязвимость протокола. MPC гарантирует, что в процессе вычислений не утекает ни одного бита сверх того, что логически следует из собственного входа и финального ответа.

1.2 Мысленный эксперимент 2: «Проблема миллионеров» Эндрю Яо (1982)

Сложение линейно, но как быть с нелинейным сравнением? В 1982 году будущий лауреат премии Тьюринга Эндрю Чи-Чи Яо (Andrew Yao) в работе “Protocols for Secure Computations” сформулировал знаменитую проблему миллионеров: два миллионера, Алиса (состояние $x$ млн долларов) и Боб (состояние $y$ млн долларов), хотят вычислить только один булев бит $f(x, y) = [x > y] \in \{0, 1\}$ (кто богаче?), не прибегая к третьей стороне и не раскрывая ни точных сумм $x, y$, ни даже разницы $x - y$.

2. Математическая формализация безопасности: Парадигма симуляции Идеального и Реального миров

Чтобы строго доказать отсутствие любых утечек, Гольдрайх, Микали и Вигдерсон (GMW 1987) ввели парадигму симуляции Идеального и Реального миров (Ideal/Real Simulation Paradigm):

  flowchart TD
    subgraph IdealWorld["Идеальный мир (Ideal World): эталон абсолютной приватности"]
        direction TB
        PA1["Участник P1 (секретный вход x1)"] -->|"Защищенный канал"| TTP["Неподкупная идеальная функциональность F"]
        PA2["Участник P2 (секретный вход x2)"] -->|"Защищенный канал"| TTP
        PAn["Участник Pn (секретный вход xn)"] -->|"Защищенный канал"| TTP
        TTP -->|"Возвращает только y = f(x1,...,xn)"| Out1["Все узнают только выход y (нулевая утечка по определению)"]
        Out1 --> Sim["Симулятор S (создает фальшивый лог только по входам скомпрометированных сторон и выходу y)"]
    end

    subgraph RealWorld["Реальный мир (Real World): криптографический протокол Π"]
        direction TB
        RB1["Участник P1 (секретный вход x1)"] <-->|"Шифротексты и случайные доли"| RB2["Участник P2 (секретный вход x2)"]
        RB2 <-->|"Шифротексты и случайные доли"| RBn["Участник Pn (секретный вход xn)"]
        RB1 <-->|"Шифротексты и случайные доли"| RBn
        RB2 --> View["Полное представление View_A(x1,...,xn) атакующего A"]
    end

    Sim <-->|"Неразличимые распределения вероятностей (View_A ≈ Sim)"| View

\[\left\{ \mathcal{S}\left(I, \{x_i\}_{i \in I}, \{y_i\}_{i \in I}\right) \right\} \stackrel{c}{\approx} \left\{ \text{View}_I^\Pi(x_1, \dots, x_n) \right\}\]

При этом различают получестных противников (Semi-Honest / Passive), соблюдающих протокол, но анализирующих трафик, и злонамеренных противников (Malicious / Active), активно искажающих сообщения.

3. Двигатель 1: Пороговое разделение секрета $(t, n)$ Шамира, интерполяция Лагранжа и протоколы BGW / SPDZ

3.1 Полиномы над полем $\mathbb{F}_p$ и формула Лагранжа

\[P(x) = s + a_1 x + a_2 x^2 + \dots + a_{t-1} x^{t-1} \pmod p\]\[s = P(0) = \sum_{i \in T} y_i \prod_{j \in T,\, j \ne i} \frac{-x_j}{x_i - x_j} \pmod p\]

Для любых $t - 1$ долей каждое возможное значение секрета $s' \in \mathbb{F}_p$ равновероятно ($H(S \mid \text{Shares}_{t-1}) = H(S)$ — безусловная теоретико-информационная стойкость).

3.2 Протокол BGW и мультипликативные тройки Бивера

\[[x \cdot y] = [w] + d \cdot [v] + e \cdot [u] + d \cdot e \pmod p\]

4. Двигатель 2: Забывчивая передача ($\text{OT}_1^2$) Рабина и искаженные схемы (Garbled Circuits) Яо

Для побитовых сравнений ($x > y$) булевы схемы позволяют выполнить вычисление за константное число раундов $O(1)$:

  flowchart TD
    subgraph Step1["1. Алиса (Garbler): шифрование булевой схемы"]
        W["Сгенерировать для каждого провода w_i два случайных 128-битных ключа AES (k_i^0, k_i^1)"] --> G["Двойное шифрование всех 4 строк таблицы истинности вентиля: Enc(k_a^α, k_b^β, k_c^g(α,β))"]
        G --> P["Случайная перестановка 4 шифротекстов каждого вентиля (Garbled Table)"]
    end

    subgraph Step2["2. Передача ключей через забывчивую передачу 1-из-2 (OT_1^2)"]
        P -->|"Отправить таблицы Garbled + активный ключ Алисы k_a^x"| Eval["Боб (Evaluator)"]
        BobIn["Секретный входной бит Боба y ∈ {0,1}"] --> OT["Забывчивая передача 1-из-2 (OT_1^2)"]
        W -->|"Пара ключей-кандидатов (k_b^0, k_b^1)"| OT
        OT -->|"Боб получает ТОЛЬКО k_b^y (Алиса ничего не узнает о y)"| Eval
    end

    subgraph Step3["3. Боб (Evaluator): слепое вычисление схемы"]
        Eval --> Dec["Расшифровать ровно 1 из 4 строк вентиля ключами (k_a^x, k_b^y) -> выходной ключ k_c^z"]
        Dec --> Out["Сопоставить ключ финального выходного провода с ответом z = f(x,y)"]
    end

С помощью забывчивой передачи 1-из-2 ($\text{OT}_1^2$) Майкла Рабина Боб получает ключ $k_b^y$ для своего секретного бита $y$, не раскрывая $y$ Алисе. Три современные оптимизации — Point-and-Permute (цветные биты указывают точную строку для расшифровки), Free-XOR ($k_i^1 = k_i^0 \oplus \Delta$ делает все вентили XOR абсолютно бесплатными без шифротекстов и вызовов AES) и Half-Gates (сокращение вентиля AND до 2 шифротекстов) — ускорили искаженные схемы более чем в $1000$ раз.

5. Полная реализация на Python: Разделение секрета Шамира и тройки Бивера над $\mathbb{F}_p$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import secrets
from typing import List, Tuple

PRIME = (1 << 61) - 1  # 61-битное простое число Мерсенна p = 2^61 - 1

def mod_inv(a: int, p: int = PRIME) -> int:
    return pow(a % p, -1, p)

def shamir_share(secret: int, t: int, n: int, p: int = PRIME) -> List[Tuple[int, int]]:
    coeffs = [secret % p] + [secrets.randbelow(p) for _ in range(t - 1)]
    shares = []
    for i in range(1, n + 1):
        y = 0
        for c in reversed(coeffs):
            y = (y * i + c) % p
        shares.append((i, y))
    return shares

def lagrange_reconstruct(shares: List[Tuple[int, int]], p: int = PRIME) -> int:
    secret = 0
    k = len(shares)
    for i in range(k):
        xi, yi = shares[i]
        num, den = 1, 1
        for j in range(k):
            if i != j:
                xj, _ = shares[j]
                num = (num * (-xj)) % p
                den = (den * (xi - xj)) % p
        secret = (secret + yi * num * mod_inv(den, p)) % p
    return secret

def mpc_add(sa, sb, p=PRIME):
    return [(xa, (ya + yb) % p) for (xa, ya), (_, yb) in zip(sa, sb)]

def mpc_sub(sa, sb, p=PRIME):
    return [(xa, (ya - yb) % p) for (xa, ya), (_, yb) in zip(sa, sb)]

def mpc_scalar_mul(c, sa, p=PRIME):
    return [(xa, (c * ya) % p) for xa, ya in sa]

def mpc_add_const(c, sa, p=PRIME):
    return [(xa, (ya + c) % p) for xa, ya in sa]

def generate_beaver_triple(t: int, n: int, p: int = PRIME):
    u, v = secrets.randbelow(p), secrets.randbelow(p)
    return shamir_share(u, t, n, p), shamir_share(v, t, n, p), shamir_share((u * v) % p, t, n, p)

def mpc_beaver_mul(sx, sy, triple, t: int, p: int = PRIME):
    su, sv, sw = triple
    d = lagrange_reconstruct(mpc_sub(sx, su, p)[:t], p)
    e = lagrange_reconstruct(mpc_sub(sy, sv, p)[:t], p)
    res = mpc_add(mpc_add(sw, mpc_scalar_mul(d, sv, p), p), mpc_scalar_mul(e, su, p), p)
    return mpc_add_const((d * e) % p, res, p)

if __name__ == "__main__":
    t, n = 3, 5
    salaries = [85000, 92000, 78000]
    shared = [shamir_share(s, t, n) for s in salaries]
    total_shares = shared[0]
    for s in shared[1:]:
        total_shares = mpc_add(total_shares, s)
    print("Восстановленная сумма зарплат:", lagrange_reconstruct(total_shares[:t]))

6. Сравнение технологий защиты приватности (PETs) и реальные внедрения

Критерий	Многосторонние вычисления (MPC)	Полностью гомоморфное шифрование (FHE)	Доказательства с нулевым разглашением (ZKP)	Доверенная среда исполнения (TEE)
Решаемая задача	Совместное вычисление функции $f(x_1, \dots, x_n)$ над секретами разных сторон	Слепые вычисления на одном сервере над шифротекстами $\text{Enc}(x) \mapsto \text{Enc}(f(x))$	Доказательство истинности $f(x, w)=1$ одним доказывающим, уже знающим $w$	Аппаратно-изолированное выполнение в открытом виде внутри анклава CPU
Узкое место	Очень быстрые операции CPU, но требуется сетевой обмен на каждый слой умножений	Всего 1 раунд связи, но вычисления CPU в $10^3–10^5$ раз медленнее	Мгновенная проверка, тяжелая генерация доказательства (MSM / FFT)	Почти нативная скорость, но ограниченный объем памяти анклава
Модель доверия	Отсутствие сговора (менее $t$ серверов в сговоре)	Трудность задач на решетках (RLWE)	Математическая надежность (не объединяет чужие секреты сам по себе)	Доверие производителю чипа (Intel/AMD); уязвимость к атакам по сторонним каналам

От исторического датского двойного аукциона квот на сахарную свеклу в 2008 году до исследования гендерного разрыва в оплате труда в Бостоне (BWWC), проверки утечек паролей в Google Chrome и Apple iCloud (Private Set Intersection, PSI), межбольничных геномных исследований (Secure GWAS) и институциональных криптокошельков с пороговой подписью MPC (Fireblocks, Coinbase) — MPC заменяет институциональное доверие математической неизбежностью.