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

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

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

Для того, чтобы после разделения секрет могли восстановить только ${\displaystyle k}$ участников, его «прячут» в формулу многочлена степени ${\displaystyle (k-1)}$ над конечным полем ${\displaystyle G}$. Для однозначного восстановления этого многочлена необходимо знать его значения в ${\displaystyle k}$ точках, причем, используя меньшее число точек, однозначно восстановить исходный многочлен не получится. Количество же различных точек многочлена не ограничено (на практике оно ограничивается размером числового поля ${\displaystyle G}$, в котором ведутся расчёты).

Кратко данный алгоритм можно описать следующим образом. Пусть дано конечное поле ${\displaystyle G}$. Зафиксируем ${\displaystyle n}$ различных ненулевых несекретных элементов данного поля. Каждый из этих элементов приписывается определённому члену группы. Далее выбирается произвольный набор из ${\displaystyle t}$ элементов поля ${\displaystyle G}$, из которых составляется многочлен ${\displaystyle f(x)}$ над полем ${\displaystyle G}$ степени ${\displaystyle t-1,1<t\leq n}$. После получения многочлена вычисляем его значение в несекретных точках и сообщаем полученные результаты соответствующим членам группы[1].

Чтобы восстановить секрет, можно воспользоваться интерполяционной формулой, например формулой Лагранжа.

Важным достоинством схемы Шамира является то, что она легко масштабируема[5]. Чтобы увеличить число пользователей в группе, необходимо лишь добавить соответствующее число несекретных элементов к уже существующим, при этом должно выполняться условие ${\displaystyle r_{i}\neq r_{j}}$ при ${\displaystyle i\neq j}$. В то же время, компрометация одной части секрета переводит схему из ${\displaystyle (n,t)}$-пороговой в ${\displaystyle (n-1,t-1)}$-пороговую.

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

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

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

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

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

Пусть количество пользователей в группе равно ${\displaystyle n}$. В схеме Миньотта выбирается некоторое множество попарно взаимно простых чисел ${\displaystyle \{m_{1},m_{2},...,m_{n}\}}$ таких, что произведение ${\displaystyle k-1}$ наибольших чисел меньше, чем произведение ${\displaystyle k}$ наименьших из этих чисел. Пусть эти произведения равны ${\displaystyle M}$ и ${\displaystyle N}$, соответственно. Число ${\displaystyle k}$ называется порогом для конструируемой схемы по множеству ${\displaystyle \{m_{1},m_{2},...,m_{n}\}}$. В качестве секрета выбирается число ${\displaystyle S}$ такое, для которого выполняется соотношение ${\displaystyle M<S<N}$. Части секрета распределяются между участниками группы следующим образом: каждому участнику выдается пара чисел ${\displaystyle (r_{i},m_{i})}$, где ${\displaystyle r_{i}\equiv S{\pmod {m_{i}}}}$.

Чтобы восстановить секрет, необходимо объединить ${\displaystyle t\geq k}$ фрагментов. В этом случае получим систему сравнений вида ${\displaystyle x\equiv r_{i}{\pmod {m_{i}}}}$, множество решений которой можно найти, используя китайскую теорему об остатках. Секретное число ${\displaystyle S}$ принадлежит этому множеству и удовлетворяет условию ${\displaystyle S<m_{1}\cdot m_{2}\cdot ...\cdot m_{t}}$. Также несложно показать, что если число фрагментов меньше ${\displaystyle k}$, то, чтобы найти секрет ${\displaystyle S}$, необходимо перебрать порядка ${\displaystyle {\frac {N}{M}}}$ целых чисел. При правильном выборе чисел ${\displaystyle m_{i}}$ такой перебор практически невозможно реализовать. К примеру, если разрядность ${\displaystyle m_{i}}$ будет от 129 до 130 бит, а ${\displaystyle k<15}$, то соотношение ${\displaystyle {\frac {N}{M}}}$ будет иметь порядок ${\displaystyle 2^{100}}$[9].

Схема Асмута — Блума является доработанной схемой Миньотта. В отличие от схемы Миньотта, её можно построить в таком виде, чтобы она была совершенной[10].

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

В рамках данной схемы выбираются ${\displaystyle n+1}$ ${\displaystyle m}$-мерных векторов ${\displaystyle V_{0},V_{1},...,V_{n}}$ так, чтобы любая матрица размером ${\displaystyle m\times m}$, составленная из этих векторов, имела ранг ${\displaystyle m}$. Пусть вектор ${\displaystyle U}$ имеет размерность ${\displaystyle m}$.

Секретом в схеме является матричное произведение ${\displaystyle U^{T}V_{0}}$. Долями секрета являются произведения ${\displaystyle U^{T}V_{i},1\leq i\leq n}$.

Имея любые ${\displaystyle m}$ долей, можно составить систему линейных уравнений размерности ${\displaystyle m\times m}$, неизвестными в которой являются коэффициенты ${\displaystyle U}$. Решив данную систему, можно найти ${\displaystyle U}$, а имея ${\displaystyle U}$, можно найти секрет. При этом система уравнений не имеет решения в случае, если долей меньше, чем ${\displaystyle m}$[12].

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

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

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

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