Предположим, что имеется $N$ легальных пользователей
которым нужно сообщить (открыть, предоставить в доступ) общий секрет $K$.
Секрет может быть доступен только определённым коалициям, например:
При этом ни одна из коалиций $C_i, ~ i = 1, 2, \dots$ не должна быть подмножеством другой коалиции.
Пример. Имеется 4 участника:
которые образуют 3 коалиции:
Распределение частичных секретов между ними представлено в виде таблицы [tab:secret-share-coalition-1], в которой введены следующие обозначения: $a_1, b_1, c_2, c_3$ – случайные числа из кольца ${{\mathbb{Z}}}_M$. В строках таблицы содержатся частичные секреты каждого из пользователей, в столбцах таблицы показаны частичные секреты, соответствующие каждой из коалиций.
| $C_1 = \{ U_1, U_2 \}$ | $C_2 = \{U_1, U_3 \}$ | $C_3 = \{ U_2, U_3, U_4 \}$ | |
| $U_1$ | $a_1$ | $b_1$ | – |
| $U_2$ | $K - a_1$ | – | $c_2$ |
| $U_3$ | – | $K - b_1$ | $c_3$ |
| $U_4$ | – | – | $K - c_2 - c_3$ |
Как видно из приведённых данных, суммирование по модулю $M$ чисел, записанных в каждом из столбцов таблицы, открывает секрет $K$.
Пример.
В системе распределения секрета доверенный
центр использует кольцо ${{\mathbb{Z}}}_m$ целых чисел по модулю $m$. Требуется разделить секрет $K$ между $5$ пользователями:
так, чтобы восстановить секрет могли только коалиции:
Заданное множество коалиций с доступом не является минимальным, так как одни коалиции входят в другие:
Исключая $C_6$, получим минимальное множество коалиций с доступом к секрету: ни одна из оставшихся коалиций не входит в другую $C_i \nsubseteq C_j$ для $i \neq j$. Пользователям выдаются тени по минимальному множеству коалиций с доступом. В строках таблицы [tab:secret-share-coalition-2] содержатся частичные секреты каждого из пользователей, в столбцах таблицы показаны частичные секреты, соответствующие каждой из коалиций.
| $C_1$ | $C_2$ | $C_3$ | $C_4$ | $C_5$ | |
| $U_1$ | $a_1$ | $b_1$ | – | – | – |
| $U_2$ | $K - a_1$ | – | $c_2$ | $d_2$ | – |
| $U_3$ | – | $K - b_1$ | $c_3$ | $d_3$ | $e_3$ |
| $U_4$ | – | – | $K - c_2 - c_3$ | – | $e_4$ |
| $U_5$ | – | – | – | $K - d_2 - d_3$ | $K - e_3 - e_4$ |
Тени выбираются случайно из кольца $\mathbb{{{\mathbb{Z}}}}_m$. В результате у пользователей будут тени.
Рассмотрим схему Брикелла (англ. Ernest Francis Brickell, [19]) разделения секрета по коалициям. По-прежнему
– легальные пользователи. Пусть ${{\mathbb{Z}}}_p$ – кольцо целых чисел по модулю $p$. Рассмотрим векторы
длины $d$. Каждому пользователю $U_i, ~ i = 1, \dots, N$ ставится в соответствие вектор
Тогда каждой из коалиций, например
соответствует набор векторов
Эти векторы должны быть выбраны так, чтобы их линейная оболочка содержала вектор
длины $d$. Линейная оболочка любого набора векторов, не образующих коалицию, не должна содержать вектор $(1, 0, 0, \dots, 0)$ длины $d$.
Пусть $K_0 \in {{\mathbb{Z}}}_p$ – общий секрет. Случайным образом из ${{\mathbb{Z}}}_p$ выбираются координаты $K_1$, $K_2$, $\dots$, $K_{d-1}$. Далее вместе с $K_0$ они объединяются в вектор $(K_0, K_1, \dots, K_{d-1})$ и вычисляются $N$ скалярных произведений:
Пользователям $U_i, ~ i = 1, 2, \dots, N$ выдаются следы – их частичные секреты:
Пусть коалиция $C$ – допустимая, например:
Тогда члены коалиции совместно находят такие коэффициенты $\lambda_1, \lambda_2, \lambda_3$, что
После этого вычисляется выражение
которое и является общим секретом.
Пример. Для сети из $n = 4$ участников
выбраны следующие векторы длины $k = 3$ над полем ${{\mathbb{Z}}}_{23}$:
Найдём все коалиции, которые могут раскрыть секрет.
Запишем
Ясно, что $c_2 \neq 0$ и коалициями пользователей, которые дают единичный вектор и, следовательно, могут восстановить секрет, являются:
Пусть доверенный центр для секрета $K = 4$ выбрал вектор $\bar{a} = (4, 2, 9)$. Тогда участники получают тени:
Возьмём коалицию $C_1 = \{ U_1, U_2, U_3 \}$ и вычислим коэффициенты $c_i$:
Найдём секрет: