Схема разделения секрета

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

История

Концепция разделения секрета была впервые формально описана независимо двумя группами исследователей в 1979 году. Ади Шамир (Израиль) предложил схему, основанную на интерполяции многочленов (схема Шамира), а Джордж Блэкли (США) — схему, основанную на геометрии многомерных пространств (схема Блэкли). Оба подхода решали одну задачу: как защитить ключ шифрования от утери или компрометации, не доверяя его одному хранителю. Первоначально схемы применялись в военных и дипломатических системах связи, а затем — в коммерческих системах управления ключами и цифровых подписях.

Основные понятия

Любая схема разделения секрета характеризуется двумя ключевыми параметрами: n (общее количество участников, получающих доли) и k (пороговое значение — минимальное количество долей, необходимое для восстановления секрета). Такая схема называется (k, n)-пороговой.

Требования к схеме

• Пороговое восстановление: любые k участников, объединив свои доли, могут однозначно восстановить секрет.
• Секретность: любые (k-1) участников, даже объединив свои доли, не могут получить никакой информации о секрете (в идеальной схеме — никакой, в вычислительной — с пренебрежимо малой вероятностью).
• Надёжность: потеря или компрометация до (n-k) долей не препятствует восстановлению секрета.
• Корректность: схема должна гарантировать, что восстановленный секрет совпадает с исходным.

Классификация схем разделения секрета

По типу используемой математики

1. Схема Шамира (полиномиальная). Основана на интерполяции многочлена степени (k-1). Секрет кодируется как свободный член многочлена, а доли — как значения многочлена в различных ненулевых точках. Для восстановления секрета по k точкам используется интерполяция Лагранжа. Схема является идеальной (размер доли равен размеру секрета) и совершенной (любая коалиция из менее k участников не получает информации). На практике часто используется в системах управления ключами и блокчейн-кошельках.

1. Схема Блэкли (геометрическая). Секрет представляется как точка в k-мерном пространстве. Каждая доля — это уравнение гиперплоскости, проходящей через эту точку. Для восстановления секрета необходимо найти точку пересечения k гиперплоскостей. Недостаток — доли могут быть больше секрета, что делает схему менее эффективной по памяти.

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

По структуре доступа

• Пороговые схемы: для восстановления достаточно любых k долей из n (самый распространённый тип).
• Схемы с общей структурой доступа: доступ к секрету имеют только строго определённые подмножества участников (например, «директор и два из трёх заместителей»). Реализуются с использованием монотонных булевых схем или схемы Бен-Ора — Голдвассера — Вигдерсона.
• Иерархические схемы: участники разделены по уровням доступа, и восстановление возможно только при наличии определённого количества долей с разных уровней.

По типу используемого поля

• Над конечным полем (GF(p)): секрет и доли — числа по модулю простого числа p. Обеспечивает точные вычисления без ошибок округления.
• Над целыми числами: возможны приближённые вычисления, что используется в некоторых приложениях машинного обучения.

Применение

Управление криптографическими ключами

Наиболее распространённое применение. Разделение мастер-ключа системы шифрования между несколькими администраторами позволяет избежать единой точки отказа. Если один администратор потеряет свою долю или будет скомпрометирован, секрет останется в безопасности, пока не соберётся пороговая группа.

Системы цифровых подписей

В пороговых схемах подписи (например, на основе ECDSA или BLS) секретный ключ разделяется между несколькими участниками. Для создания подписи требуется участие k из n сторон, при этом ни одна из сторон не узнаёт полный ключ. Применяется в мультиподписях криптовалют и децентрализованных автономных организациях (DAO).

Хранение паролей и seed-фраз

Криптовалютные кошельки (например, Ledger, Trezor) предлагают разделение seed-фразы (мнемонической фразы восстановления) по схеме Шамира. Владелец может передать доли фразы разным доверенным лицам, и для восстановления доступа к кошельку потребуется, например, 3 из 5 долей.

Облачное хранение данных

Схемы разделения секрета используются для обеспечения конфиденциальности при хранении данных в распределённых облачных хранилищах. Файл разделяется на доли, которые хранятся у разных провайдеров. Даже если один провайдер будет скомпрометирован, он не получит доступа к исходным данным.

Многосторонние вычисления (MPC)

Разделение секрета является базовым строительным блоком для протоколов безопасных многосторонних вычислений, позволяющих нескольким сторонам совместно вычислить функцию от своих приватных входов, не раскрывая эти входы друг другу.

Пример работы схемы Шамира (k=3, n=5)

Пусть секрет S = 1234. Выбирается простое число p = 1613. Строится многочлен степени 2 (k-1=2) с коэффициентами a₁=166, a₂=94: f(x) = 1234 + 166x + 94x² mod 1613.

Вычисляются доли для 5 участников:

• f(1) = 1234 + 166 + 94 = 1494 mod 1613 = 1494
• f(2) = 1234 + 332 + 376 = 1942 mod 1613 = 329
• f(3) = 1234 + 498 + 846 = 2578 mod 1613 = 965
• f(4) = 1234 + 664 + 1504 = 3402 mod 1613 = 176
• f(5) = 1234 + 830 + 2350 = 4414 mod 1613 = 1188

Теперь для восстановления секрета любые 3 участника, например, с долями (1, 1494), (2, 329) и (3, 965), могут построить интерполяционный многочлен Лагранжа и вычислить f(0) = 1234. Любые 2 участника не смогут этого сделать — для многочлена второй степени по двум точкам существует бесконечно много решений.

Критика и ограничения

• Проблема честности: классические схемы не защищены от нечестного дилера (того, кто создаёт доли) или нечестных участников, которые могут предоставить ложные доли при восстановлении. Для решения используются верифицируемые схемы разделения секрета (VSS).
• Уязвимость к атакам по времени: реализация схем, особенно на эллиптических кривых, может быть подвержена атакам по побочным каналам, если не используются константные алгоритмы.
• Сложность распределения: в крупных системах с большим n и k распределение долей может быть вычислительно затратным, особенно для схем с общей структурой доступа.
• Необходимость безопасного канала: доли должны передаваться участникам по защищённым каналам, иначе перехват одной доли не даёт информации, но перехват k долей — даёт.

Интересные факты

• Схема Шамира используется в некоторых реализациях протокола консенсуса Proof-of-Stake (например, в сети Cosmos) для разделения валидаторских ключей.
• В 2020 году группа исследователей из Массачусетского технологического института (MIT) предложила квантово-устойчивую схему разделения секрета на основе решёток.
• Схема Блэкли менее популярна из-за того, что размер каждой доли в ней может быть в несколько раз больше размера самого секрета, что снижает эффективность хранения.

Источники

• Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613.
• Blakley, G. R. (1979). Safeguarding cryptographic keys. Proceedings of the National Computer Conference, 48, 313–317.
• Mignotte, M. (1983). How to share a secret? Lecture Notes in Computer Science, 149, 371–375.
• Beimel, A. (2011). Secret-sharing schemes: A survey. Lecture Notes in Computer Science, 6639, 11–46.
• Stinson, D. R. (1995). Cryptography: Theory and Practice. CRC Press.