5.2. Разделение секрета для произвольных структур доступа

Next: 5.3. Линейное разделение секрета Up: 5. Математика разделения секрета Previous: 5.1. Введение Contents: Содержание

5.2. Разделение секрета для произвольных структур доступа

Начнем с формальной математической модели. Имеется множество ${\cal S}_0, {\cal S}_1,\dots,{\cal S}_n$ и (совместное) распределение вероятностей на их декартовом произведении ${\cal S}={\cal S}_0\times \dots \times{\cal S}_n$ . Соответствующие случайные величины обозначаются через . Имеется также некоторое множество $\Gamma$ подмножеств множества $\{ 1,\dots ,n\}$ , называемое структурой доступа.

Определение 1. Пара $(P,{\cal S})$ называется совершенной вероятностной СРС, реализующей структуру доступа $\Gamma$ , если

$\begin{displaymath} P(S_0=c_0 \mid S_i=c_i, i \in A)\in \{0,1\}\; {\mbox {для}}\; A\in \Gamma , \tag{1} \end{displaymath}$ (1)

$\begin{displaymath} P(S_0=c_0 \mid S_i=c_i, i \in A)=P(S_0=c_0)\; {\mbox {для}}\; A\notin \Gamma .\tag{2} \end{displaymath}$

(2)

Это определение можно истолковать следующим образом. Имеется множество ${\cal S}_0$ всех возможных секретов, из которого секрет выбирается с вероятностью , и имеется СРС, которая ``распределяет'' секрет между участниками, посылая ``проекции'' $s_1,\dots,s_n$ секрета с вероятностью $P_{s_0}(s_1,\dots,s_n)$ . Отметим, что -й участник получает свою ``проекцию'' $s_i\in {\cal S}_i$ и не имеет информации о значениях других ``проекций'', однако знает все множества ${\cal S}_i$ , а также оба распределения вероятностей и $P_{s_0}(s_1,\dots,s_n).$ Эти два распределения могут быть эквивалентно заменены на одно: $P(s_0,s_1,\dots,s_n)=p(s_0)P_{s_0}(s_1,\dots,s_n)$ , что и было сделано выше. Цель СРС, как указывалось во введении, состоит в том, чтобы:
а) участники из разрешенного множества (т.е. $A\in \Gamma$ ) вместе могли бы однозначно восстановить значение секрета - это отражено в свойстве (1);
б) участники, образующие неразрешенное множество ( $A\notin \Gamma$ ), не могли бы получить дополнительную информацию об , т.е., чтобы вероятность того, что значение секрета , не зависела от значений ``проекций'' при $i \in A$ - это свойство (2).

Замечание о терминологии. В англоязычной литературе для обозначения ``порции'' информации, посылаемой участнику СРС, были введены термины ``share'' (А. Шамир) и ``shadow'' (Г. Блейкли). Первый термин оказался наиболее популярным и автор долго боролся с соблазном привлечь массового читателя, постоянно используя в качестве его перевода слово ``акция''. Неадекватная (во всех смыслах) замена ``акции'' на ``проекцию'' может быть несколько оправдана следующим примером.

Пример 1. Множество ${\cal S}_0$ всех возможных секретов состоит из , и , ``представленных'' соответственно: шаром; кубом, ребра которого параллельны осям координат; цилиндром, образующие которого параллельны оси . При этом диаметры шара и основания цилиндра, и длины ребра куба и образующей цилиндра, равны. Первый участник получает в качестве своей ``доли'' секрета его проекцию на плоскость , а второй - на плоскость . Ясно, что вместе они однозначно восстановят секрет, а порознь - не могут. Однако, эта СРС не является совершенной, так как любой из участников получает информацию о секрете, оставляя только два значения секрета как возможные при данной проекции (например, если проекция - квадрат, то шар невозможен).

Еще одно замечание. Элемент (участник) $x\in \{1,\dots,n\}$ называется несущественным (относительно $\Gamma$ ), если для любого неразрешенного множества множество $A\cup x$ также неразрешенное. Очевидно, что несущественные участники настолько несущественны для разделения секрета, что им просто не нужно посылать никакой информации. Поэтому далее, без ограничения общности, рассматриваются только такие структуры доступа $\Gamma$ , для которых все элементы являются существенными. Кроме того, естественно предполагать, что $\Gamma$ является монотонной структурой, т.е. из $A\subset B, A\in \Gamma$ следует $B\in \Gamma.$

Пример 2. Рассмотрим простейшую структуру доступа - -пороговую схему, т.е. все участники вместе могут восстановить секрет, а любое подмножество участников не может получить дополнительной информации о секрете. Будем строить идеальную СРС, выбирая и секрет, и его проекции из группы вычетов по модулю , т.е. ${\cal S}_0 = {\cal S}_1\double=\ldots={\cal S}_n= Z_q.$ Дилер генерирует независимых равномерно распределенных на случайных величин и посылает -му участнику ( $i=1,\ldots,n-1$ ) его ``проекцию'' , а -му участнику посылает $s_n=s_0 - (s_1+\dots+s_{n-1})$ . Кажущееся ``неравноправие'' -ого участника тут же исчезает, если мы выпишем распределение $P_{s_0}(s_1,\dots,s_n)$ , которое очевидно равно $1/q^{n-1}$ , если $s_0 = s_1+\dots+s_{n}$ , и равно - в остальных случаях. Теперь легко проверяется и свойство (2), означающее в данном случае независимость случайной величины от случайных величин $\{S_i : i \in A\}$ при любом собственном подмножестве .

Данное выше определение СРС, оперирующее словами ``распределение вероятностей'', ниже переведено, почти без потери общности, на комбинаторный язык, который представляется автору более простым для понимания. Произвольная $M\times (n+1)$ -матрица , строки которой имеют вид ${\mathbf v} =(v_0,v_1,\ldots,v_n)$ , где $v_i \in {\cal S}_i$ , называется матрицей комбинаторной СРС, а ее строки - ``правилами'' распределения секрета. Для заданного значения секрета дилер СРС случайно и равновероятно выбирает строку $\mathbf v$ из тех строк матрицы , для которых значение нулевой координаты равно .

Определение 2. Матрица задает совершенную комбинаторную СРС, реализующую структуру доступа $\Gamma$ , если, во-первых, для любого множества $A\in \Gamma$ нулевая координата любой строки матрицы однозначно определяется значениями ее координат из множества , и, во-вторых, для любого множества $A\notin \Gamma$ и любых заданных значений координат из множества число строк матрицы с данным значением $\alpha$ нулевой координаты не зависит от $\alpha$ .

Сопоставим совершенной вероятностной СРС, задаваемой парой $(P,{\cal S})$ , матрицу состоящую из строк $s\in{\cal S}$ , таких что . Заметим, что если в определении 1 положить все ненулевые значения одинаковыми, а условия (1) и (2) переформулировать на комбинаторном языке, то получится определение 2. Это комбинаторное определение несколько обобщается, если допустить в матрице повторяющиеся строки, что эквивалентно вероятностному определению 1, когда значения вероятностей - рациональные числа.

Пример 2. (продолжение) Переформулируем данную выше конструкцию -пороговой СРС на комбинаторном языке. Строками матрицы являются все векторы $\mathbf s$ такие, что $-s_0 +s_1+\dots+s_{n}=0$ . Очевидно, что матрица задает совершенную комбинаторную СРС для $\Gamma =\{1,\ldots,n\}$ , так как для любого собственного подмножества $A\subset\{1,\dots,n\}$ и любых заданных значений координат из множества число строк матрицы с данным значением нулевой координаты равно $q^{n-1-\vert A\vert}$ .

Удивительно, но простой схемы примера 2 оказывается достаточно, чтобы из нее, как из кирпичиков, построить совершенную СРС для произвольной структуры доступа. А именно, для всех разрешенных множеств, т.е. для $A\in \Gamma$ , независимо реализуем описанную только что пороговую $(\vert A\vert,\vert A\vert)$ -СРС, послав тем самым -му участнику столько ``проекций'' $s_{i}^{A}$ , скольким разрешенным множествам он принадлежит. Это словесное описание несложно перевести на комбинаторный язык свойств матрицы и убедиться, что эта СРС совершенна. Как это часто бывает, ``совершенная'' не значит ``экономная'', и у данной СРС размер ``проекции'' оказывается, как правило, во много раз больше, чем размер секрета. Эту схему можно сделать более экономной, так как достаточно реализовать пороговые $(\vert A\vert,\vert A\vert)$ -СРС только для минимальных разрешенных множеств , т.е. для $A\in \Gamma_{\min}$ , где $\Gamma_{\min}$ - совокупность минимальных (относительно включения) множеств из $\Gamma$ . Тем не менее, для пороговой -СРС размер ``проекции'' (измеренный, например, в битах) будет в $C_n^{n/2}\sim 2^n/\sqrt{2\pi n}$ раз больше размера секрета (это наихудший случай для рассматриваемой конструкции). С другой стороны, как мы убедимся чуть позже, любая пороговая структура доступа может быть реализована идеально, т.е. при совпадающих размерах ``проекции'' и секрета. Поэтому естественно возникает вопрос о том, каково максимально возможное превышение размера ``проекции'' над размером секрета для наихудшей структуры доступа при наилучшей реализации. Формально, $R(n)=\max R(\Gamma)$ , где $\max$ берется по всем структурам доступа $\Gamma$ на участниках, а $R(\Gamma) = \min \max \frac{\log \vert S_i\vert}{\log \vert S_0\vert}$ , где $\min$ берется по всем СРС, реализующим данную структуру доступа $\Gamma$ , а $\max$ - по $i=1,\ldots,n$ . Приведенная конструкция показывает, что $R(n)\leq C_n^{n/2}$ . С другой стороны, как было доказано лишь недавно [5], $R(n)\geq n/\log n$ . Такая огромная ``щель'' между верхней и нижней оценкой дает, по нашему мнению, достаточный простор для исследований (автор предполагает, что растет экспоненциально от ).