Векторная схема разделения секрета

Векторная схема разделения секрета, или схема Блэкли (англ. Blakley's scheme), — схема разделения секрета между сторонами, основанная на использовании точек многомерного пространства. Предложена Джорджем Блэкли в 1979 году. Схема Блэкли позволяет создать (t, n)-пороговое разделение секрета для любых t, n.

Идея

Разделяемым секретом в схеме Блэкли является одна из координат точки в $m$-мерном пространстве. Долями секрета, раздаваемые сторонам, являются уравнения $(m-1)$-мерных гиперплоскостей. Для восстановления точки необходимо знать $m$ уравнений гиперплоскостей. Менее, чем $m$ сторон не смогут восстановить секрет, так как множеством пересечения $m-1$ плоскостей является прямая, и секрет не может быть восстановлен.

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

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

Описание

Генерация точки

Пусть нужно реализовать $(k,n)$-пороговую схему, то есть секрет $M$ разделить между $n$ сторонами так, чтобы любые $k$ из них могли восстановить секрет. Для этого выбирается большое простое число $p>M$, по модулю которого будет строиться поле $GF(p)$. Случайным образом дилер^[кто?] выбирает числа $b_{2},\dots ,b_{k}\in GF(p)$. Тем самым задается точка $(M,b_{2},\dots ,b_{k})$ в $k$-мерном пространстве, первая координата которой является секретом.

Раздача секрета

Для каждой стороны $P_{i},i=(1,\dots ,n)$ случайным образом выбираются коэффициенты $a_{1i},a_{2i},\dots ,a_{ki}$, равномерно распределённые в поле $GF(p)$. Так как уравнение плоскости имеет вид $a_{1i}\cdot x_{1}+a_{2i}\cdot x_{2}+\dots +a_{ki}\cdot x_{k}+d_{i}=0$, для каждой стороны необходимо вычислить коэффициенты $d_{i}$:

${\begin{aligned}d_{1}&=-(a_{11}\cdot M+a_{21}\cdot b_{2}+\dots +a_{k1}\cdot b_{k}){\bmod {p}},\\d_{2}&=-(a_{12}\cdot M+a_{22}\cdot b_{2}+\dots +a_{k2}\cdot b_{k}){\bmod {p}},\\&~\vdots \\d_{i}&=-(a_{1i}\cdot M+a_{2i}\cdot b_{2}+\dots +a_{ki}\cdot b_{k}){\bmod {p}},\\&~\vdots \\d_{n}&=-(a_{1n}\cdot M+a_{2n}\cdot b_{2}+\dots +a_{kn}\cdot b_{k}){\bmod {p}}.\\\end{aligned}}$

При этом необходимо следить, чтобы любые $k$ уравнений были линейно независимы. В качестве долей секрета сторонам раздают набор коэффициентов, задающих уравнение гиперплоскости.

Восстановление секрета

Для восстановления секрета любым $k$ сторонам необходимо собраться вместе и из имеющихся долей секрета составить уравнения для отыскания точки пересечения гиперплоскостей:

$\left\{{\begin{aligned}(a_{11}\cdot x_{1}+a_{21}\cdot x_{2}+\dots +a_{k1}\cdot x_{k}+d_{1}){\bmod {p}}&=0,\\(a_{12}\cdot x_{1}+a_{22}\cdot x_{2}+\dots +a_{k2}\cdot x_{k}+d_{2}){\bmod {p}}&=0,\\&\vdots \\(a_{1k}\cdot x_{1}+a_{2k}\cdot x_{2}+\dots +a_{kk}\cdot x_{k}+d_{k}){\bmod {p}}&=0.\\\end{aligned}}\right.$

Решение системы даёт точку в $k$-мерном пространстве, первая координата которой и есть разделяемый секрет. Систему можно решать любым известным способом, например, методом Гаусса, но при этом необходимо проводить вычисления в поле $GF(p)$.

Если число участников встречи будет меньше, чем $k$, например, $k-1$, то результатом решения системы уравнений, составленной из имеющегося набора коэффициентов, будет прямая в $k$-мерном пространстве. Тем самым множество допустимых значений секрета, удовлетворяющих полученной системе, в точности совпадает с полным числом элементов поля $GF(p)$, и секрет равновероятно может принимать любое значение из этого поля. Таким образом, участники, собравшись вместе, не получат никакой новой информации о разделённом секрете.

Свойства

Несовершенная схема: Количество участника увеличит, номер возможностей для секретной точкой снизит. Например, для t − 1 участников знают линии, в которой лежит секретная точка.

Отсек схемы: Участники  делятся на подгруппы называемых отсеков. Чтобы получить секрет, кворум отсеков требуется, но для отсек участвовать в кворуме, другой кворум акций требуется.

Многоуровневые схемы: Участники делятся на две упорядоченных уровнях. Для восстановления секрет меньше кворума требуется более высокий уровень. Кроме того, каждый высший уровнь участники может заменить на нижнего уровня участники.

Некоторые участники не могут получить секрет.

Пример

Пусть нужно разделить секрет «6» между 4 сторонами, при этом любые 3 должны иметь возможность восстановить его. Иными словами, необходимо реализовать $(3,4)$-пороговое разделение секрета.

Для этого зададим точку в 3-мерном пространстве, например, $(6,4,2)$. Первая координата точки и есть разделяемый секрет, 4 и 2 — некоторые случайные числа. При этом будем работать в поле $GF(11)$, то есть все числа будут вычисляться, как остатки от деления на $p=11$.

Каждой стороне необходимо дать уравнение плоскости, проходящей через заданную точку. В 3-мерном пространстве уравнение плоскости задается с помощью 4 параметров: $a_{1}\cdot x_{1}+a_{2}\cdot x_{2}+a_{3}\cdot x_{3}+d=0$, где $x_{1},x_{2},x_{3}$ — координаты, а $(a_{1},a_{2},a_{3},d)$ — параметры, раздаваемые сторонам. Для выбора параметров можно поступить следующим образом: величины $(a_{1},a_{2},a_{3})$ выбрать случайным образом (при этом необходимо, чтобы полученные плоскости не оказались компланарными), а свободный коэффициент для каждой стороны вычислять по заданной точке и выбранным коэффициентам.

Например, выберем параметры следующим образом:

1-я сторона: $(4,8,2,d_{1})$,

2-я сторона: $(2,6,8,d_{2})$,

3-я сторона: $(6,8,4,d_{3})$,

4-я сторона: $(3,10,1,d_{4})$.

Для вычисления неизвестных параметров $d$ воспользуемся значениями координат выбранной точки:

${\begin{aligned}d_{1}&=-(4\cdot 6+8\cdot 4+2\cdot 2){\bmod {1}}1=6,\\d_{2}&=-(2\cdot 6+6\cdot 4+8\cdot 2){\bmod {1}}1=3,\\d_{3}&=-(6\cdot 6+8\cdot 4+4\cdot 2){\bmod {1}}1=1,\\d_{4}&=-(3\cdot 6+10\cdot 4+1\cdot 2){\bmod {1}}1=6.\\\end{aligned}}$

После этого доли секрета вместе с числом $p=11$ раздаются сторонам.

Для восстановления секрета любым трём участникам необходимо найти точку пересечения плоскостей, уравнения которых им были заданы. Например, первым трём сторонам для восстановления секрета необходимо будет решить систему уравнений

$\left\{{\begin{aligned}(4\cdot x_{1}+8\cdot x_{2}+2\cdot x_{3}+6){\bmod {1}}1=0,\\(2\cdot x_{1}+6\cdot x_{2}+8\cdot x_{3}+3){\bmod {1}}1=0,\\(6\cdot x_{1}+8\cdot x_{2}+4\cdot x_{3}+1){\bmod {1}}1=0.\\\end{aligned}}\right.$

Систему можно решать любым способом, не забывая при этом, что вычисления ведутся в поле $GF(11)$. Несложно убедиться, что точка $(6,4,2)$ является решением системы, её первая координата «6» и есть разделяемый секрет.

Литература

• Шнайер Б. 23.2 Алгоритмы разделения секрета. Векторная схема // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 589. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Blakley G. R. Safeguarding cryptographic keys (англ.) // Proceedings of the 1979 AFIPS National Computer Conference — Montvale: AFIPS Press, 1979. — P. 313—317. — doi:10.1109/AFIPS.1979.98