Пороговая схема

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

Основные понятия и определения

Пороговая схема формально описывается парой чисел (k, n), где n — общее количество участников, а k — пороговое значение (k ≤ n). Схема с параметрами (k, n) означает, что секрет S делится на n частей (долей, теней), раздаваемых участникам, причём:

• Любые k или более долей позволяют однозначно восстановить секрет S.
• Любые k-1 или менее долей не дают никакой информации о секрете S (в информационно-теоретическом смысле).

Такое свойство называется совершенной секретностью. Оно означает, что даже при наличии полной вычислительной мощности противник, владеющий менее чем k долями, не сможет получить никаких сведений о секрете, кроме его длины.

История возникновения

Концепция пороговых схем была впервые предложена независимо двумя исследователями в 1979 году:

• Ади Шамиром (Израиль), который разработал схему на основе интерполяции многочленов (схема Шамира).
• Джорджем Блэкли (США), который предложил подход, основанный на пересечении гиперплоскостей (схема Блэкли).

Оба метода были опубликованы в 1979 году в трудах конференций и стали основой для дальнейшего развития криптографии с разделением секрета. Схема Шамира получила наибольшее распространение благодаря своей простоте, эффективности и возможности работы с любым порогом k.

Математические основы

Схема Шамира

Схема Шамира основана на свойстве многочленов степени k-1: для однозначного определения такого многочлена необходимо знать k различных точек на нём. Процесс выглядит следующим образом:

1. Выбирается простое число p, большее максимального возможного значения секрета S и числа участников n.
2. Строится многочлен f(x) степени k-1 над полем GF(p) (конечное поле из p элементов):

f(x) = a₀ + a₁·x + a₂·x² + ... + a_{k-1}·x^{k-1} где a₀ = S (секрет), а коэффициенты a₁, a₂, ..., a_{k-1} выбираются случайным образом из GF(p).

1. Для каждого участника i (i = 1, 2, ..., n) вычисляется доля: y_i = f(i) mod p.
2. Каждому участнику передаётся пара (i, y_i).

Для восстановления секрета необходимо собрать k любых долей (i, y_i). По ним строится интерполяционный многочлен Лагранжа, и секрет S находится как значение f(0) = a₀.

Схема Блэкли

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

Классификация пороговых схем

По типу секретности

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

По способу восстановления

• Схемы с восстановлением по Лагранжу — классический метод, использующий интерполяцию.
• Схемы с использованием китайской теоремы об остатках — секрет делится на части, каждая из которых является остатком от деления на различные модули.
• Схемы на основе кодов, исправляющих ошибки — например, с использованием кодов Рида-Соломона.

По динамическим свойствам

• Пороговые схемы с возможностью обновления долей — позволяют периодически менять доли участников без изменения самого секрета, что повышает безопасность.
• Пороговые схемы с возможностью исключения участников — позволяют перераспределить доли так, чтобы исключённый участник потерял доступ к секрету.

Применение

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

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

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

В протоколах безопасных многосторонних вычислений (MPC) пороговые схемы используются для распределения секретных данных между участниками, позволяя выполнять вычисления без раскрытия самих данных.

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

В пороговых схемах подписи секретный ключ распределяется между несколькими участниками. Подпись может быть создана только при участии порогового числа участников, что повышает безопасность и предотвращает злоупотребления.

Блокчейн и криптовалюты

В некоторых блокчейн-проектах пороговые схемы применяются для управления кошельками с мультиподписью, где для совершения транзакции требуется подпись нескольких держателей ключей.

Системы резервного копирования

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

Преимущества и недостатки

Преимущества

• Устойчивость к компрометации — даже если часть долей будет украдена или утеряна, секрет остаётся защищённым, если количество скомпрометированных долей меньше порога.
• Отказоустойчивость — потеря некоторых долей не препятствует восстановлению секрета, если доступно пороговое количество.
• Гибкость — можно выбирать произвольное соотношение k и n в зависимости от требований безопасности.
• Информационно-теоретическая стойкость (в совершенных схемах) — не зависит от вычислительных мощностей противника.

Недостатки

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

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

Основная критика пороговых схем связана с практическими аспектами их применения. Во-первых, в реальных системах часто требуется не только разделение секрета, но и его последующее использование (например, для расшифровки данных), что может потребовать дополнительных протоколов. Во-вторых, при большом количестве участников и высоком пороге вычислительные затраты на восстановление могут быть значительными. В-третьих, схема Шамира требует, чтобы все операции выполнялись в конечном поле, что накладывает ограничения на размер секрета.

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

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

• В 1989 году Густавус Симмонс обобщил концепцию пороговых схем, введя понятие «честных схем» (verifiable secret sharing), где участники могут проверить корректность полученных долей без раскрытия секрета.
• Пороговые схемы лежат в основе некоторых протоколов квантового распределения ключей, где секрет делится между несколькими квантовыми каналами.
• В 2019 году группа исследователей из России предложила модификацию схемы Шамира, устойчивую к атакам с использованием квантовых компьютеров (постквантовая криптография).

Источники

1. Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612-613.
2. Blakley, G. R. (1979). Safeguarding cryptographic keys. Proceedings of the National Computer Conference, 48, 313-317.
3. Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
4. Stinson, D. R. (1995). Cryptography: Theory and Practice. CRC Press.
5. Beimel, A. (2011). Secret-sharing schemes: A survey. Lecture Notes in Computer Science, 6634, 11-46.