Проблема разделения секрета

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

Разделить 128-битный ключ на две 64-битные половины и выдать каждую половину одному из двух людей кажется разумным, но это небезопасно: каждая половина снижает стоимость перебора с 2^128 до 2^64. Злоумышленник, скомпрометировавший одного человека, получает преимущество в 64 бита.

Правильная схема разделения секрета должна обеспечивать: (1) Пороговое восстановление: любые k долей из n позволяют восстановить секрет. (2) Безопасность: любые k-1 долей не раскрывают никакой информации о секрете. (3) Идеальную защиту: вычислительные предположения не требуются.

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

Чтобы разделить секрет S между двумя сторонами: сгенерируйте случайное значение R. Передайте share1=R стороне 1, а share2=S XOR R — стороне 2. Для восстановления: share1 XOR share2 = R XOR (S XOR R) = S. Каждая отдельная доля полностью случайна и ничего не раскрывает о S.

Разделение на основе XOR идеально подходит для схемы 2 из 2, но не обобщается на пороговые схемы k из n. Нельзя создать схему 3 из 5, в которой любые 3 доли восстанавливают секрет, а любые 2 не раскрывают ничего. Эту задачу решает полиномиальная интерполяция.

Идеальная секретность означает, что при наличии менее k долей доли содержат нулевую взаимную информацию о секрете. Это сильнее вычислительной безопасности: даже противник с неограниченными вычислительными возможностями не узнает ничего из k-1 долей.

AWS CloudHSM использует пороговую аутентификацию кворума M из N. PGP разделяет мастер-ключи для передачи на хранение. Провайдеры хранения криптовалют (Fireblocks, BitGo) используют MPC или разделение Шамира для ключей горячих кошельков. Для офлайн-ключей центров сертификации применяются процедуры 5 из 7.

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

Разделение секрета восстанавливает полный секрет (риск: единственная точка отказа во время восстановления). Мультиподпись распределяет подписание: каждая сторона подписывает независимо, а подписи объединяются. Пороговые подписи (TSS) применяют разделение секрета непосредственно к операции подписания.

Безопасные многосторонние вычисления (MPC) полностью устраняют этап восстановления: стороны совместно выполняют вычисления с использованием своих долей, не раскрывая секрет. Пороговые ECDSA и BLS применяются в рабочих системах хранения криптоактивов.

В схеме разделения секрета 2 из 2 на основе XOR сколько долей нужно злоумышленнику, чтобы узнать секрет?

Наивное разделение ключа небезопасно. Правильное разделение секрета требует порогового доступа и идеальной секретности. XOR работает для схемы 2 из 2, а полиномиальная интерполяция — для схем k из n. Далее: математика схемы разделения секрета Шамира.