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

Каждая доля секрета — это плоскость, а секрет представляет собой точку пересечения трех плоскостей. Две доли секрета позволяют получить линию, на которой лежит секретная точка.

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

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

В отличии от процедуры разбиения секрета, в процедуре разделения секрета количество долей, которые нужны для восстановления секрета, может отличаться от того, на сколько долей мы разделили секрет. Такая схема носит названия пороговой схемы $\left$ , где n — количество долей, на которые был разделён секрет, а t - количество долей, которые нужны для восстановления секрета.

В тривиальном случае t = n мы получаем схему разбиения секрета.

Идеи схем $t \neq n$ были независимо предложены в 1979 году Ади Шамиром и Джорджем Блэкли Blakley Jr.). Кроме этого подобные процедуры исследовались Гусом Симмонсом.

Схема Шамира

Через две точки можно провести неограниченное число полиномов степени 2. Чтобы выбрать из них единственный - нужна третья точка

Идея схемы заключается в том, что двух точек достаточно для задания прямой, трех точек — для задания параболы, четырех точек — для кубической параболы, и так далее. Чтобы задать многочлен степени k требуется k + 1 точек.

Если мы хотим разделить секрет таким образом, чтобы восстановить его могли только k человек, мы «прячем» его в формулу -мерного многочлена. Восстановить этот многочлен можно по k точкам. Количество же различных точек многочлена не ограничено.

Схема Блэкли

Две непараллельные прямые на плоскости пересекаются в одной точке. Любые две некомпланарные плоскости пересекаются по одной прямой, а три некомпланарные плоскости в пространстве пересекаются тоже в одной точке. Вообще n n-мерных гиперплоскостей всегда пересекаются в одной точке. Одна из координат этой точки будет секретом. Если закодировать секрет как несколько координат точки, то уже по одной доле секрета можно будет получить какую-то информацию о секрете, то есть о взаимозависимости координат точки пересечения.


Схема Блэкли в трех измерениях: каждая доля секрета — это плоскость, а секрет — это одна из координат точки пересечения плоскостей. Двух плоскостей недостаточно для определения точки пересечения.

С помощью схемы Блэкли можно создать-схему разделения секрета для любых t u n: для этого надо положить размерность пространства равную t, и каждому из n игроков дать одну гиперплоскость, проходящую через секретную точку. Тогда любые t из n гиперплоскостей будут однозначно пересекаться в секретной точке. Схема Блэкли менее эффективна чем схема Шамира: в схеме Шамира каждая доля такого же размера как и секрет, а в схеме Блэкли каждая доля в t раз больше. Существуют улучшения схемы Блэкли, позволяющие повысить ее эффективность.

Схемы, основанные на китайской теореме об остатках

В 1983 году Миньотт, Морис, Асмут и Блум предложили две схемы разделения секрета, основанные на китайской теореме об остатках. Для некоторого числа вычисляются остатки от деления на последовательность чисел, которые раздаются сторонам. Благодаря ограничениям на последовательность чисел, восстановить секрет может только определённое число сторон.

Схемы, основанные на решении систем уравнений

В 1983 году Карнин, Грини и Хеллман предложили свою схему разделения секрета, которая основывалась на невозможности решить систему с m неизвестными имея менее m уравнений.

Способы обмана пороговой схемы

Существуют несколько способов нарушить протокол работы пороговой схемы:

Также существуют другие возможности нарушения работы, несвязанные с особенностями реализации схемы: