secret-sharing-brickells.tex

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

Рассмотрим схему Брикелла (\langen{Ernest Francis Brickell},~\cite{Brickell:1990}) распределения секрета по коалициям.

По-прежнему
    \[ \{ 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$ случайно. Затем вычисляются скалярные произведения:
\[\begin{array}{l}
	\left( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \varphi(U_1) \right) ~=~ a_1, \\
	\left( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \varphi(U_2) \right) ~=~ a_2, \\
	\dots \\
	\left( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \varphi(U_N) \right) ~=~ a_N. \\
\end{array}\]

Пользователям $U_i, ~ i = 1, 2, \dots, N$ выдаются их частичные секреты:
    \[ U_i \colon \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). \]

После этого вычисляется выражение
\[\begin{array}{l}
    \lambda_1 a_1 + \lambda_2 a_2 + \lambda_3 a_3 = \\
    = \left( \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) \right) = \\
    = \left( \left( K_0, K_1, \dots, K_{d-1} \right), ~ \left( 1, 0, \dots, 0 \right) \right) =  K_0, \\
\end{array}\]
которое и является общим секретом.

%\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

\index{схема распределение секрета!Бриккела|)}