Линейное разделение секрета
Начнем с предложенной Шамиром элегантной схемы разделения секрета для пороговых структур доступа. Пусть К = GF(q) — конечное поле из q элементов (например, q = p — простое число и К = Zp) и q > n. Сопоставим участникам n различных ненулевых элементов поля {a1, …, an} и положим a0 = 0. При распределении секрета s0
дилер СРС генерирует k–1 независимых равномерно распределенных на GF(q) случайных величин fj (j = 1, …, k–1) и посылает і-му учаснику (і = 1, ..., n) “его” значение si = f(ai) многочлена f(x) = f0
+ f1x + … + fk-1xk-1, где f0 = s0. Поскольку любой многочлен степени k-1 однозначно восстанавливается по его значениям в произвольных k точках (например, по интерполяционной формуле Лагранжа), то любые k участников вместе могут восстановить многочлен f(x) и, следовательно, найти значение секрета как s0 = f(0). По этой же причине для любых k–1 участников, любых полученных ими значений проекций si и любого значения секрета s0 существует ровно один “соответствующий” им многочлен, т.е. такой, что si = f(ai) и s0 = f(0). Следовательно, эта схема является совершенной в соответствии с определением 2. “Линейность” данной схемы становится ясна, если записать “разделение секрета” в векторно-матричном виде:
s = fH, (18.3)
где s = (s0, …, sn), f = (f0, …, fk–1), k× (n+1) — матрица H = (hij) = (aij-1) и h00 = 1. Заметим, что любые k столбцов этой матрицы линейно независимы, а максимально возможное число столбцов матрицы H равно q, чтобы добиться обещанного значения q+1 надо добавить столбец, соответствующий точке “бесконечность”.
Возьмем в (18.3) в качестве H произвольную r × (n + 1)-матрицу с элементами из поля K. Получаемую СРС, будем называть одномерной линейной СРС. Она является совершенной комбинаторной СРС со структурой доступа Г, состоящей из множеств А таких, что вектор h0
представим в виде линейной комбинации векторов {hj: j Î A}, где hj — это j-ый столбец матрицы H.
Строками матрицы V, соответствующей данной СРС, являются, как видно из (18.3), линейные комбинации строк матрицы H. Перепишем (18.3) в следующем виде
sj = (f, hj) для j = 0, 1, …, n,
где (f, hj) — скалярное произведение векторов f и hj. Если А Î Г, т.е. если h0 = ??jhj, то
s0 = (f, h0) = = ??j(f, hj) = ??jsj
и, следовательно, значение секрета однозначно находится по его “проекциям”. Рассмотрим теперь случай, когда вектор h0 не представим в виде линейной комбинации векторов {hj: j Î A}. Нам нужно показать, что в этом случае для любых заданных значений координат из множества А число строк матрицы V с данным значением любой координаты не зависит от этого значения. В этом не трудно убедится, рассмотрев (18.3) как систему линейных уравнений относительно неизвестных fi
и воспользовавшись тем, что система совместна тогда и только тогда, когда ранг матрицы коэффициентов равен рангу расширенной матрицы, а число решений у совместных систем одинаково и равно числу решений однородной системы.
Указание. Рассмотрите две системы: c “нулевым” уравнением и без него (т.е. со свободным членом). Так как вектор h0
не представим в виде линейной комбинации векторов {hj: j Î A}, то ранг матрицы коэффициентов второй системы на 1 больше ранга матрицы коэффициентов первой системы. Отсюда немедленно следует, что если первая система совместна, то совместна и вторая при любом s0.
Эта конструкция подводит нас к определению общей линейной СРС. Пусть секрет и его “проекции” представляются как конечномерные векторы si = (s, …, s) и генерируются по формуле si = fHi, где Hi
— некоторые r × mi-матрицы. Сопоставим каждой матрице Hi
линейное пространство Li
ее столбцов (т.е. состоящее из всех линейных комбинаций вектор-столбцов матрицы Hi). Несложные рассуждения, аналогичные приведенным выше для одномерного случая (все mi = 1), показывают, что данная конструкция дает совершенную СРС тогда и только тогда, когда семейство линейных подпространств {L0, …, Ln} конечномерного векторного пространства K удовлетворяет упомянутому выше свойству “все или ничего”.
При этом множество А является разрешенным {La: a Î A} содержит подпространство L0 целиком. С другой стороны, множество А является неразрешенным (А Ï Г), если и только если линейная оболочка подпространств {La: a Î A} пересекается с подпространством L0
только по вектору 0. Отметим, что если бы для некоторого А пересечение L0 и линейной оболочки {La: a Î A} было нетривиальным, то участники А не могли бы восстановить секрет однозначно, но получали бы некоторую информацию о нем, т.е. схема не была бы совершенной.
Пример 18.3. Рассмотрим следующую структуру доступа для случая четырех участников, задаваемую Гmin = {{1,2}, {2,3}, {3,4}}. Она известна как первый построенный пример структуры доступа, для которой не существует идеальной реализации. Более того, было доказано, что для любой ее совершенной реализации R(Г) ? 3/2. С другой стороны, непосредственная проверка показывает, что выбор матриц H0, H1, ..., H4, приведенных на рис. 18.2, дает совершенную линейную СРС с R = 3/2, реализующую эту структуру, которая, следовательно, является и оптимальной (наиболее экономной) СРС.
Рис. 18.2. Матрицы, реализующие совершенную линейную СРС
