brickells_scheme.tex

\subsection{Схема Брикелла для нескольких коалиций}
\selectlanguage{russian}

Рассмотрим \textbf{схему Брикелла}\index{распределение секрета!Бриккела} (Brickell) распределения секрета по коалициям.

По-прежнему,
    \[ \{ U_1, U_2, \dots, U_N \} \]
легальные пользователи. Пусть $\Z_p$ -- кольцо целых чисел  по модулю $p$. Рассмотрим векторы
    \[ \mathcal{U} = \left\{ (u_1, u_2, \dots, u_d) \right\}, ~~ u_i \in \Z_p \]
длины $d$. Каждому пользователю $U_i, ~ i = 1, \dots, N$ ставится в соответствие вектор
    \[ \varphi(U_i) \in \mathcal{U}, ~~ i = 1, \dots, N. \]

Тогда каждой из коалиций, например
    \[ C_1 = \{ U_1, U_2, U_3 \}, \]
соответствует набор векторов
    \[ \varphi(U_1), \varphi(U_2), \varphi(U_3). \]
Эти векторы должны быть выбраны так, чтобы их линейная оболочка \emph{содержала} вектор
    \[ (1, 0, 0, \dots, 0) \]
длины $d$. Линейная оболочка  любого набора векторов, не образующих коалицию, \emph{не должна} содержать вектор $(1, 0, 0, \dots, 0)$ длины $d$.

Пусть $K_0 \in \Z_p$ -- общий секрет. Распределение секрета производится следующим образом. Сначала вычисляется вектор $(K_0, K_1, \dots, K_{d-1})$, где первая координата -- это общий секрет, а остальные координаты выбираются из $\Z_p$ случайно. Затем вычисляются скалярные произведения
\[
    \Big( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \varphi(U_1) \Big) ~=~ a_1,
\] \[
    \Big( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \varphi(U_2) \Big) ~=~ a_2,
\] \[
    \dots
\] \[
    \Big( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \varphi(U_N) \Big) ~=~ a_N,
\]
Пользователю $U_i, ~ i = 1, 2, \dots, N$, выдаются их частичные секреты
    \[ U_i: ~~ \left\{ \varphi(U_i), ~ a_i \right\}. \]

Пусть коалиция $C$ -- допустимая, например
    \[ C = C_1 = \{ U_1, U_2, U_3 \}. \]
Тогда члены коалиции совместно находят  такие коэффициенты $\lambda_1, \lambda_2, \lambda_3$, что
    \[ \lambda_1\varphi(U_1)+\lambda_2\varphi(U_2)+\lambda_3\varphi(U_3) ~=~ (1,0, \dots, 0). \]
После этого вычисляется выражение
\[
    \lambda_1 a_1 + \lambda_2 a_2 + \lambda_3 a_3 =
\] \[
    = \Big( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \lambda_1 \varphi(U_1) + \lambda_2 \varphi(U_2) + \lambda_3 \varphi(U_3) \Big) =
\] \[
    = \Big( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \left( 1, 0, \dots, 0 \right) \Big) =  K_0,
\]
которое и является общим секретом.

%\section{Схема разделения секрета в векторном пространстве Бриккела}
%
%В схеме Бриккела для $n$ пользователей $\{ U_1, U_2, \ldots, U_n \}$ Центр выбирает $k$-мерные векторы $\varphi(U_i)$ над полем $\mathbb{\Z}_p$ так, чтобы их линейная нетривиальная комбинация над полем $\mathbb{\Z}_p$ могла равняться единичному вектору
%    \[ (1,0,0, \ldots, 0) = \sum\limits_{i=1}^{n} c_i \ \varphi(U_i), ~ c_i \in  \mathbb{\Z}_p. \]
%Центр пользователю $i$ присваивает \emph{открытый, публично доступный} вектор $\varphi(U_i)$.
%
%Для разделения секрета $K$ Центр выбирает случайные числа $a_2, a_3, \ldots, a_n$, составляет вектор $\bar{a} = (K, a_2, a_3, \ldots, a_n)$ и выдает каждому пользователю \emph{секретную} тень $s_i = \bar{a} \cdot \varphi(U_i)$.
%
%Восстановление секрета производится
%    \[ K = \bar{a} \cdot (1,0,\ldots,0) = \bar{a} \cdot \sum\limits_{i=1}^{n} c_i \varphi(U_i) = \sum\limits_{i=1}^{n} c_i s_i, \]
%так как из открытых векторов $\varphi(U_i)$ пользователи могут найти $c_i$.
%
%Восстановить секрет могут только те коалиции пользователей, для которых нетривиальная комбинация векторов $\varphi(U_i)$ дает единичный вектор.

\example
Для сети из $n=4$ участников
    \[ \{ U_1, U_2, U_3, U_4 \} \]
выбраны следующие векторы длины $k=3$ над полем $\Z_{23}$:
\[ \begin{array}{l}
    \varphi(U_1) = (0,2,0), \\
    \varphi(U_2) = (2,0,7), \\
    \varphi(U_3) = (0,5,7), \\
    \varphi(U_4) = (0,2,9). \\
\end{array} \]
Найдем все коалиции, которые могут раскрыть секрет.

Запишем
    \[ (1,0,0) = c_1 (0,2,0) + c_2 (2,0,7) + c_3 (0,5,7) + c_4 (0,2,9). \]
Ясно, что $c_2 \neq 0$, и коалициями пользователей, которые дают единичный вектор и, следовательно, могут восстановить секрет, являются:
\[ \begin{array}{l}
    C_1 = \{ U_1, U_2, U_3 \}, \\
    C_2 = \{ U_1, U_2, U_4 \}, \\
    C_3 = \{ U_2, U_3, U_4 \}. \\
\end{array} \]

Пусть доверенный Центр для секрета $K=4$ выбрал вектор $\bar{a} = (4, 2, 9)$. Тогда участники получают тени:
    \[ s_1 = (4,2,9) \cdot (0,2,0) = 4 \mod 23, \]
    \[ s_2 = (4,2,9) \cdot (2,0,7) = 2 \mod 23, \]
    \[ s_3 = (4,2,9) \cdot (0,5,7) = 4 \mod 23, \]
    \[ s_4 = (4,2,9) \cdot (0,2,9) = 16 \mod 23. \]

Возьмем коалицию $C_1 = \{ U_1, U_2, U_3 \}$ и вычислим коэффициенты $c_i$:
    \[ (1,0,0) = c_1 (0,2,0) + c_2 (2,0,7) + c_3 (0,5,7), \]
\[ \begin{array}{l}
    c_1 = 7 \mod 23, \\
    c_2 = 12 \mod 23, \\
    c_3 = 11 \mod 23. \\
\end{array} \]

Найдем секрет:
    \[ K = 7 \cdot 4 + 12 \cdot 2 + 11 \cdot 4 = 4 \mod 23.\]
\exampleend