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

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

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

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

Идеи схем были независимо предложены в 1979 году Ади Шамиром^[1] и Джорджем Блэкли (англ. George Robert (Bob) Blakley Jr.)^[2]. Кроме этого подобные процедуры исследовались Гусом Симмонсом.^[3]

Схема Шамира

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

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

Схема Блэкли

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

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

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

В 1983 году Миньотт, Морис (англ. Maurice Mignotte)^[4], Асмут и Блум^[5] предложили две схемы разделения секрета, основанные на китайской теореме об остатках. Для некоторого числа (в схеме Миньотта это сам секрет, в схеме Асмута—Блума — некоторое производное число) вычисляются остатки от деления на последовательность чисел, которые раздаются сторонам. Благодаря ограничениям на последовательность чисел, восстановить секрет может только определённое число сторон.

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

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

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

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

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

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

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

Примечания