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

Разделение секрета делит секрет s на n долей так, что любые t из них позволяют восстановить s, а любая группа размером меньше t не даёт никакой информации. Две самые известные схемы - схема Шамира (на базе полиномов, t-of-n) и аддитивная (каждая доля представляет собой s_i, где Σ s_i = s, и требуются все участники).

В схеме Шамира дилер выбирает случайный полином p(x) = s + r₁x + ... + r_{t-1}x^{t-1} и передаёт значение p(i) доле i. Интерполяция Лагранжа по любым t долям восстанавливает p(0) = s. Именно случайность коэффициентов старших степеней скрывает s от любого подмножества размером меньше t.

Свойство, которое делает это полезным для secure-multiparty-computation, - линейность:

• [x] + [y] = [x + y] - покомпонентное сложение долей выполняется бесплатно
• [x] + a = [x + a] для известной константы a
• a · [x] = [a·x] для известной константы a

Таким образом, линейные комбинации разделённых значений вычисляются без какого-либо взаимодействия. Сложность возникает при умножении двух разделённых значений, где наивное почленное умножение удваивает степень результирующего полинома - порог восстановления возрастает с t до 2t-1. Стандартным решением в модели с предварительными вычислениями и онлайн-фазой служат beaver-triples.

Этот паттерн уходит глубоко: схемы HE - по сути то же разделение секрета, где "долями" выступают шифротексты; бутстраппинг в FHE концептуально представляет собой рерандомизацию полинома долей; в сообществе Bitcoin схемы по типу Шамира используются для холодного хранения (хотя Pedersen-VSS и Feldman-VSS добавляют коммитменты для защиты от нечестных дилеров).

Перекрёстные ссылки: mpc-beaver-triples, beaver-triples, secure-multiparty-computation.