Многосторонние вычисления и пороговая криптография

Как нескольким сторонам вместе посчитать ответ, не показав друг другу свои данные.

Многосторонние вычисления (secure multi-party computation, MPC) — протоколы, где несколько участников совместно вычисляют функцию от своих приватных входов так, что каждый узнаёт только результат, но не чужие входные данные.

Зачем это знать

Иногда нужный результат требует данных, которыми никто не готов делиться. Кто богаче из двух людей, не называя сумм? Какова средняя зарплата в отделе без раскрытия чьего-либо оклада? Кто выиграл закрытый аукцион без публикации ставок? MPC даёт ответ, не создавая «доверенного посредника», который видел бы всё и стал бы единой точкой утечки.

Идея: считаем вслепую

Простейший пример — приватное суммирование. Трое хотят узнать сумму зарплат, не раскрывая оклады. Каждый разбивает свою зарплату на случайные доли, раздаёт по одной каждому участнику, затем все складывают полученные доли. Сумма долей равна сумме зарплат, но ни одна отдельная доля ничего не выдаёт. Это и есть дух MPC: входы «размазаны» так, что промежуточные значения бессмысленны, а итог — корректен.

Разделение секрета Шамира

Фундаментальный кирпич MPC и пороговой криптографии — схема разделения секрета Шамира. Секрет делят на n долей так, что любые t из них восстанавливают секрет, а любые t−1 не дают о нём ровно никакой информации. Схема (t, n)-пороговая.

Идея гениально проста и опирается на школьную геометрию: через любые две точки проходит ровно одна прямая, через любые три — одна парабола, и так далее. Чтобы спрятать секрет с порогом t, берут случайный многочлен степени t−1, у которого свободный член равен секрету, и раздают участникам значения этого многочлена в разных точках. Имея t точек, многочлен восстанавливают однозначно (интерполяция) и читают свободный член. С t−1 точками подходящих многочленов бесконечно много — секрет неопределён.

# Учебная демонстрация разделения секрета Шамира (схема (t, n)).
# Считаем по модулю простого числа p — так делают в реальной криптографии.
import random

p = 2087  # простое число, больше секрета и больше n

def make_shares(secret, t, n):
    # многочлен степени t-1: f(x) = secret + a1*x + a2*x^2 + ...
    coeffs = [secret] + [random.randrange(1, p) for _ in range(t - 1)]
    def f(x):
        return sum(c * pow(x, i, p) for i, c in enumerate(coeffs)) % p
    return [(x, f(x)) for x in range(1, n + 1)]

def recover(shares):
    # интерполяция Лагранжа в точке x=0 по модулю p
    secret = 0
    for i, (xi, yi) in enumerate(shares):
        num, den = 1, 1
        for j, (xj, _) in enumerate(shares):
            if i != j:
                num = (num * (-xj)) % p
                den = (den * (xi - xj)) % p
        lagr = (num * pow(den, -1, p)) % p  # обратный по модулю
        secret = (secret + yi * lagr) % p
    return secret % p

random.seed(42)
SECRET = 1234
shares = make_shares(SECRET, t=3, n=5)
print("Доли (x, y):", shares)
print("Восстановили по 3 долям:", recover(shares[:3]))
print("По другим 3 долям:", recover([shares[0], shares[2], shares[4]]))
print("Двух долей не хватает для порога t=3 (любой результат возможен).")

Вывод:

Доли (x, y): [(1, 1794), (2, 473), (3, 1445), (4, 536), (5, 1920)]
Восстановили по 3 долям: 1234
По другим 3 долям: 1234
Двух долей не хватает для порога t=3 (любой результат возможен).

Любые три доли дают исходный секрет 1234, а две — нет. Именно так данные «размазывают» по участникам без доверенного хранителя.

Пороговые подписи

Та же идея применима к ключам подписи. В пороговой подписи приватный ключ не существует целиком ни у кого: он разделён на доли между n участниками, и для создания валидной подписи нужны любые t из них. Преимущества для защиты:

Нет единой точки компрометации: украв одну (и даже t−1) долю, злоумышленник не подделает подпись.
Отказоустойчивость: подписать можно, даже если часть держателей недоступна.
В отличие от мультиподписи, на выходе — одна обычная подпись, и внешнему наблюдателю не видно, сколько сторон участвовало.

Это основа корпоративных и крипто-кошельков: ключ делят между несколькими сотрудниками/устройствами (схема, например, 3 из 5), и перевод требует кворума.

Как это работает под капотом

Полноценный MPC комбинирует разделение секрета с протоколами, позволяющими складывать и умножать «секретные доли» так, что результат остаётся разделённым до самого конца. Различают модели угроз: honest-but-curious (участники следуют правилам, но пытаются подсмотреть) и злонамеренные (могут отклоняться от протокола) — для вторых нужны дополнительные проверки целостности. Безопасность держится, пока сговорившихся участников меньше порога.

Где это применяется

Защита ключей: пороговые кошельки и MPC-подпись вместо хранения цельного приватного ключа.
Совместная аналитика: банки считают общий антифрод-скоринг, не раскрывая клиентов; больницы — статистику, не объединяя карты пациентов.
Аукционы и голосования: подвести итог, не раскрывая отдельные ставки/голоса.

Как защититься и применять грамотно

Выбирайте порог осознанно: слишком низкий t — легко собрать кворум злоумышленнику, слишком высокий — система встанет при потере нескольких долей. Доли распределяйте по независимым носителям и людям, чтобы исключить общий канал компрометации. Для враждебной среды берите схемы с проверкой целостности (verifiable secret sharing), иначе участник может тихо подсунуть неверную долю и испортить результат.

Итоги

MPC вычисляет функцию от приватных входов, раскрывая только результат, без доверенного посредника.
Схема Шамира делит секрет на n долей с порогом t: любые t восстанавливают секрет, t−1 не дают о нём ничего.
Пороговые подписи разделяют приватный ключ, убирая единую точку компрометации и сохраняя одну обычную подпись на выходе.
Применения — защита ключей и кошельков, совместная приватная аналитика, тайные аукционы и голосования.