15-05-2023
В криптографии под разделением секрета (англ. 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] свою схему разделения секрета, которая основывалась на невозможности решить систему с неизвестными, имея менее уравнений.
Существуют несколько способов нарушить протокол работы пороговой схемы:
Также существуют другие возможности нарушения работы, несвязанные с особенностями реализации схемы:
Пороговая схема.