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

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

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

Начнем с предложенной А. Шамиром [2] элегантной схемы разделения секрета для пороговых структур доступа. Пусть конечное поле из элементов (например, - простое число и ) и Сопоставим участникам различных ненулевых элементов поля $\{a_1,\ldots,a_n\}$ и положим . При распределении секрета дилер СРС генерирует независимых равномерно распределенных на случайных величин ( $j=1,\dots, k-1$ ) и посылает -му участнику ( $i=1,\ldots,n$ ) ``его'' значение многочлена $f(x)=f_0+f_1x+\dots+f_{k-1}x^{k-1}$ , где . Поскольку любой многочлен степени однозначно восстанавливается по его значениям в произвольных точках (например, по интерполяционной формуле Лагранжа), то любые участников вместе могут восстановить многочлен и, следовательно, найти значение секрета как . По этой же причине для любых участников, любых полученных ими значений проекций и любого значения секрета существует ровно один ``соответствующий'' им многочлен, т.е. такой, что и . Следовательно, эта схема является совершенной в соответствии с определением 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$ . Заметим, что любые

столбцов этой матрицы линейно независимы, а максимально возможное число столбцов матрицы

равно

, и чтобы добиться обещанного в разделе 1 значения

надо добавить столбец, соответствующий точке ``бесконечность''.

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

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

число строк матрицы

с данным значением нулевой координаты не зависит от этого значения. В этом нетрудно убедиться, рассмотрев (3) как систему линейных уравнений относительно неизвестных

и воспользовавшись тем, что система совместна тогда и только тогда, когда ранг матрицы коэффициентов равен рангу расширенной матрицы, а число решений у совместных систем одинаково и равно числу решений однородной системы.

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

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

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

Таблица 1.

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