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


5.3. Линейное разделение секрета

Начнем с предложенной А. Шамиром [2] элегантной схемы разделения секрета для пороговых структур доступа. Пусть $ K=GF(q)$ конечное поле из $ q$ элементов (например, $ q=p$ - простое число и $ K=Z_p$) и $ q>n.$ Сопоставим участникам $ n$ различных ненулевых элементов поля $ \{a_1,\ldots,a_n\}$ и положим $ a_0=0$. При распределении секрета $ s_0$ дилер СРС генерирует $ k-1$ независимых равномерно распределенных на $ GF(q)$ случайных величин $ f_j$ ( $ j=1,\dots, k-1$) и посылает $ i$-му участнику ($ i=1,\ldots,n$) ``его'' значение $ s_i =f(a_i)$ многочлена $ f(x)=f_0+f_1x+\dots+f_{k-1}x^{k-1}$, где $ f_0=s_0$. Поскольку любой многочлен степени $ k-1$ однозначно восстанавливается по его значениям в произвольных $ k$ точках (например, по интерполяционной формуле Лагранжа), то любые $ k$ участников вместе могут восстановить многочлен $ f(x)$ и, следовательно, найти значение секрета как $ s_0=f(0)$. По этой же причине для любых $ k-1$ участников, любых полученных ими значений проекций $ s_i$ и любого значения секрета $ s_0$ существует ровно один ``соответствующий'' им многочлен, т.е. такой, что $ s_i =f(a_i)$ и $ s_0=f(0)$. Следовательно, эта схема является совершенной в соответствии с определением 2. ``Линейность'' данной схемы становится ясна, если записать ``разделение секрета'' в векторно-матричном виде:
\begin{displaymath} {\mathbf s}={\mathbf f} H, \tag{3} \end{displaymath} (3)

где $ {\mathbf s}=(s_0,\ldots,s_n), {\mathbf f}=(f_0,\ldots,f_{k-1})$, $ k\times(n+1)$-матрица $ H =(h_{ij})\double=(a_i^{j-1})$ и $ h_{00}=1$. Заметим, что любые $ k$ столбцов этой матрицы линейно независимы, а максимально возможное число столбцов матрицы $ H$ равно $ q$, и чтобы добиться обещанного в разделе 1 значения $ q+1$ надо добавить столбец, соответствующий точке ``бесконечность''.

Упражнение. Придумайте сами, как это сделать.

Возьмем в (3) в качестве $ H$ произвольную $ r\times(n+1)$-матрицу с элементами из поля $ K$. Получаемую СРС будем называть одномерной линейной СРС. Она является совершенной комбинаторной СРС со структурой доступа $ \Gamma$, состоящей из множеств $ A$ таких, что вектор $ {\mathbf h}_0$ представим в виде линейной комбинации векторов $ \{{\mathbf h}_j:\;j\in A\},$ где $ {\mathbf h}_j$ это $ j$-ый столбец матрицы $ H.$ Строками матрицы $ V$, соответствующей данной СРС являются, как видно из (3), линейные комбинации строк матрицы $ H$. Перепишем (3) в следующем виде

\begin{displaymath}s_j=({\mathbf f},{\mathbf h}_j) \;{\mbox {для}}\; j=0,1,\ldots,n,\end{displaymath}

где $ ({\mathbf f},{\mathbf h}_j)$ - скалярное произведение векторов $ \mathbf f$ и $ {\mathbf h}_j$. Если $ A\in \Gamma$, т.е. если $ {\mathbf h}_0=\sum \lambda_j {\mathbf h}_j$, то

\begin{displaymath}s_0=({\mathbf f},{\mathbf h}_0)=({\mathbf f}, \sum \lambda_j ... ...sum \lambda_j ({\mathbf f},{\mathbf h}_j)= \sum \lambda_j s_j \end{displaymath}

и, следовательно, значение секрета однозначно находится по его ``проекциям''. Рассмотрим теперь случай, когда вектор $ {\mathbf h}_0$ не представим в виде линейной комбинации векторов $ \{{\mathbf h}_j:\;j\in A\}$. Нам нужно показать, что в этом случае для любых заданных значений координат из множества $ A$ число строк матрицы $ V$ с данным значением нулевой координаты не зависит от этого значения. В этом нетрудно убедиться, рассмотрев (3) как систему линейных уравнений относительно неизвестных $ f_i$ и воспользовавшись тем, что система совместна тогда и только тогда, когда ранг матрицы коэффициентов равен рангу расширенной матрицы, а число решений у совместных систем одинаково и равно числу решений однородной системы.

Указание. Рассмотрите две системы: без ``нулевого'' уравнения (т.е. со свободным членом) и с ним. Так как вектор $ {\mathbf h}_0$ не представим в виде линейной комбинации векторов $ \{{\mathbf h}_j: j\in A\}$, то ранг матрицы коэффициентов второй системы на 1 больше ранга матрицы коэффициентов первой системы. Отсюда немедленно следует, что если первая система совместна, то совместна и вторая при любом $ s_0$.

Эта конструкция подводит нас к определению общей линейной СРС. Пусть секрет и его ``проекции'' представляются как конечномерные векторы $ {\mathbf s}_i=(s_i^1,\ldots,s_i^{m_i})$ и генерируются по формуле $ {\mathbf s}_i={\mathbf f} H_i,$ где $ H_i$ - некоторые $ r\times m_i$-матрицы. Сопоставим каждой матрице $ H_i$ линейное пространство $ L_i$ ее столбцов (т.е. состоящее из всех линейных комбинаций вектор-столбцов матрицы $ H_i$). Несложные рассуждения, аналогичные приведенным выше для одномерного случая (все $ m_i=1$), показывают, что данная конструкция дает совершенную СРС тогда и только тогда, когда семейство линейных подпространств $ \{L_0,\dots,L_n\}$ конечномерного векторного пространства $ K^r$ удовлетворяет упомянутому во введении свойству ``все или ничего''. При этом множество $ A$ является разрешенным ($ A\in \Gamma$), если и только если линейная оболочка подпространств $ \{L_a:a\in A\}$ содержит подпространство $ L_0$ целиком. С другой стороны, множество $ A$ является неразрешенным ( $ A\notin \Gamma$), если и только если линейная оболочка подпространств $ \{L_a:a\in A\}$ пересекается с подпространством $ L_0$ только по вектору $ \mathbf 0$. Отметим, что если бы для некоторого $ A$ пересечение $ L_0$ и линейной оболочки $ \{L_a:a\in A\}$ было нетривиальным, то участники $ A$ не могли бы восстановить секрет однозначно, но получали бы некоторую информацию о нем, т.е. схема не была бы совершенной.

Пример 3.   Рассмотрим следующую структуру доступа для случая четырех участников, задаваемую $ \Gamma_{\min}=\{\{1,2\},\{2,3\},\{3,4\}\}.$ Она известна как первый построенный пример структуры доступа, для которой не существует идеальной реализации. Более того, было доказано, что для любой ее совершенной реализации $ R(\Gamma)\geq 3/2 $. С другой стороны, непосредственная проверка показывает, что выбор матриц $ H_0,H_1,\ldots,H_4$, приведенных в табл. 1, дает совершенную линейную СРС с $ R=3/2$, реализующую эту структуру, которая, следовательно, является и оптимальной (наиболее экономной) СРС.


Таблица 1.
\begin{table}%%{Таблица═1.} {\par\begin{displaymath} \arraycolsep=2pt H_0=\lef... ...0\!\\ \!0\!&\!1\!\ \end{array}\right]. \end{displaymath} \par } \end{table}


Next: 5.4. Идеальное разделение секрета Up: 5. Математика разделения секрета Previous: 5.2. Разделение секрета для Contents: Содержание

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