Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: 5.3. Линейное разделение секрета Up: 5. Математика разделения секрета Previous: 5.1. Введение Contents: Содержание


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

Начнем с формальной математической модели. Имеется $ n+1$ множество $ {\cal S}_0, {\cal S}_1,\dots,{\cal S}_n$ и (совместное) распределение вероятностей $ P$ на их декартовом произведении $ {\cal S}={\cal S}_0\times \dots \times{\cal S}_n$. Соответствующие случайные величины обозначаются через $ S_i$. Имеется также некоторое множество $ \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_0$ выбирается с вероятностью $ p(s_0)$, и имеется СРС, которая ``распределяет'' секрет $ s_0$ между $ n$ участниками, посылая ``проекции'' $ s_1,\dots,s_n$ секрета с вероятностью $ P_{s_0}(s_1,\dots,s_n)$. Отметим, что $ i$-й участник получает свою ``проекцию'' $ s_i\in {\cal S}_i$ и не имеет информации о значениях других ``проекций'', однако знает все множества $ {\cal S}_i$, а также оба распределения вероятностей $ p(s_0)$ и $ 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$ (т.е. $ A\in \Gamma$) вместе могли бы однозначно восстановить значение секрета - это отражено в свойстве (1);
б) участники, образующие неразрешенное множество $ A$ ( $ A\notin \Gamma$), не могли бы получить дополнительную информацию об $ s_0$, т.е., чтобы вероятность того, что значение секрета $ S_0=c_0$, не зависела от значений ``проекций'' $ S_i$ при $ i \in A$ - это свойство (2).

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

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

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

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

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

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

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

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

Удивительно, но простой схемы примера 2 оказывается достаточно, чтобы из нее, как из кирпичиков, построить совершенную СРС для произвольной структуры доступа. А именно, для всех разрешенных множеств, т.е. для $ A\in \Gamma$, независимо реализуем описанную только что пороговую $ (\vert A\vert,\vert A\vert)$-СРС, послав тем самым $ i$-му участнику столько ``проекций''  $ s_{i}^{A}$, скольким разрешенным множествам он принадлежит. Это словесное описание несложно перевести на комбинаторный язык свойств матрицы $ V$ и убедиться, что эта СРС совершенна. Как это часто бывает, ``совершенная'' не значит ``экономная'', и у данной СРС размер ``проекции'' оказывается, как правило, во много раз больше, чем размер секрета. Эту схему можно сделать более экономной, так как достаточно реализовать пороговые $ (\vert A\vert,\vert A\vert)$-СРС только для минимальных разрешенных множеств $ A$, т.е. для $ A\in \Gamma_{\min}$, где $ \Gamma_{\min}$ - совокупность минимальных (относительно включения) множеств из $ \Gamma$. Тем не менее, для пороговой $ (n,n/2)$-СРС размер ``проекции'' (измеренный, например, в битах) будет в $ C_n^{n/2}\sim 2^n/\sqrt{2\pi n}$ раз больше размера секрета (это наихудший случай для рассматриваемой конструкции). С другой стороны, как мы убедимся чуть позже, любая пороговая структура доступа может быть реализована идеально, т.е. при совпадающих размерах ``проекции'' и секрета. Поэтому естественно возникает вопрос о том, каково максимально возможное превышение размера ``проекции'' над размером секрета для наихудшей структуры доступа при наилучшей реализации. Формально, $ R(n)=\max R(\Gamma) $, где $ \max$ берется по всем структурам доступа $ \Gamma$ на $ n$ участниках, а $ 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$. Такая огромная ``щель'' между верхней и нижней оценкой дает, по нашему мнению, достаточный простор для исследований (автор предполагает, что $ R(n)$ растет экспоненциально от $ n$).

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

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100