forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsecret-sharing.tex
106 lines (85 loc) · 6.69 KB
/
secret-sharing.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
\chapter{Разделение секрета}
\selectlanguage{russian}
\section{Пороговые схемы}
Идея \emph{пороговой} $(K, N)$-схемы\index{разделение секрета!пороговое} разделения общего секрета среди $N$ пользователей состоит в следующем. Доверенная сторона хочет распределить некий секрет $K_0$ между $N$ пользователями таким образом, что:
\begin{itemize}
\item любые $m_1: K \leq m_1 \leq N$, легальных пользователей могут получить секрет (или доступ к секрету), если предъявят свои секретные ключи;
\item любые $m_2: m_2 < K$, легальных пользователей не могут получить секрет и не могут определить (вычислить) этот секрет, даже решив трудную в вычислительном смысле задачу.
\end{itemize}
Далее рассмотрены три случая: $(K, N)$-схема Блэкли, $(K, N)$-схема Шамира и простая $(N,N)$-схема.
\input{secret-sharing-blackleys}
\input{secret-sharing-shamirs}
\input{secret-sharing-xor}
\section{Распределение секрета по коалициям}
\subsection{Схема для нескольких коалиций}
Предположим, что имеется $N$ легальных пользователей
\[ \{ U_1, U_2, \dots, U_N \}, \]
которым нужно сообщить (открыть, предоставить в доступ) общий секрет $K$.
Секрет может быть доступен только определённым коалициям\index{распределение секрета!по коалициям}, например:
\[ \begin{array}{l}
C_1 = \{ U_1, U_2 \}, \\
C_2 = \{ U_1, U_3, U_4 \}, \\
C_3 = \{ U_2, U_3 \}, \\
\dots
\end{array} \]
При этом ни одна из коалиций $C_i, ~ i = 1, 2, \dots$ не должна быть подмножеством другой коалиции.
\example
Имеется 4 участника:
\[ \{ U_1, U_2, U_3, U_4 \}, \]
которые образуют 3 коалиции:
\[ \begin{array}{l}
C_1 = \{ U_1, U_2 \}, \\
C_2 = \{ U_1, U_3 \}, \\
C_3 = \{ U_2, U_3, U_4 \}. \\
\end{array} \]
Распределение частичных секретов между ними представлено в виде таблицы~\ref{tab:secret-share-coalition-1}, в которой введены следующие обозначения: $a_1, b_1, c_2, c_3$ -- случайные числа из кольца $\Z_M$. В строках таблицы содержатся частичные секреты каждого из пользователей, в столбцах таблицы показаны частичные секреты, соответствующие каждой из коалиций.
\begin{table}[!ht]
\centering
\caption{Распределение секрета по определённым коалициям\label{tab:secret-share-coalition-1}}
\begin{tabular}{|c||c|c|c|}
\hline
& $C_1 = \{ U_1, U_2 \}$ & $C_2 = \{U_1, U_3 \}$ & $C_3 = \{ U_2, U_3, U_4 \}$ \\
\hline \hline
$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$ \\
\hline
\end{tabular}
\end{table}
Как видно из приведённых данных, суммирование по модулю $M$ чисел, записанных в каждом из столбцов таблицы, открывает секрет $K$.
\exampleend
\example
%\section{Схема разделения секрета на монотонных булевых функциях}
%\example
В системе распределения секрета доверенный
%с использованием монотонных булевых функций
центр использует кольцо $\Z_m$ целых чисел по модулю $m$. Требуется разделить секрет $K$ между $5$ пользователями:
\[ \{ U_1, U_2, U_3, U_4, U_5 \} \]
так, чтобы восстановить секрет могли только коалиции:
\[ \begin{array}{lll}
C_1 = \{ U_1, U_2 \}, & & C_2 = \{ U_1, U_3 \}, \\
C_3 = \{ U_2, U_3, U_4 \}, & & C_4 = \{ U_2, U_3, U_5 \}, \\
C_5 = \{ U_3, U_4, U_5 \}, & & C_6 = \{ U_1, U_2, U_3 \}. \\
\end{array} \]
Заданное множество коалиций с доступом не является минимальным, так как одни коалиции входят в другие:
\[ C_1 \subset C_6, ~ C_2 \subset C_6. \]
Исключая $C_6$, получим минимальное множество коалиций с доступом к секрету -- ни одна из оставшихся коалиций не входит в другую $C_i \nsubseteq C_j$ для $i \neq j$. Пользователям выдаются тени по минимальному множеству коалиций с доступом. В строках таблицы~\ref{tab:secret-share-coalition-2} содержатся частичные секреты каждого из пользователей, в столбцах таблицы показаны частичные секреты, соответствующие каждой из коалиций.
\begin{table}[!ht]
\centering
\caption{Распределение секрета по определённым коалициям\label{tab:secret-share-coalition-2}}
\begin{tabular}{|c||c|c|c|c|c|}
\hline
& $C_1$ & $C_2$ & $C_3$ & $C_4$ & $C_5$ \\
\hline \hline
$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$ \\
\hline
\end{tabular}
\end{table}
Тени выбираются случайно из кольца $\mathbb{\Z}_m$. В результате у пользователей будут тени.
\exampleend
\input{secret-sharing-brickells}