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

Начнем с предложенной Шамиром элегантной схемы разделения секрета для пороговых структур доступа. Пусть К = GF(q)— конечное поле изqэлементов (например,q = p— простое число иК = Z_p) иq > n. Сопоставим участникамn различных ненулевых элементов поля{a₁, …, a_n}и положимa₀ = 0. При распределении секретаs₀дилер СРС генерируетk–1независимых равномерно распределенных наGF(q)случайных величинf_j (j = 1, …, k–1)и посылает і-му учаснику (і = 1, ..., n) “его” значение s_i = f(a_i) многочлена f(x) = f₀ + f₁x + … + f_k-1x_k-1, гдеf₀ = s₀.Поскольку любой многочлен степениk-1однозначно восстанавливается по его значениям в произвольныхkточках (например, по интерполяционной формуле Лагранжа), то любыеkучастников вместе могут восстановить многочленf(x)и, следовательно, найти значение секрета какs₀ = f(0). По этой же причине для любыхk–1участников,любых полученных ими значений проекций s_i и любого значения секрета s₀ существует ровно один “соответствующий” им многочлен, т.е. такой, чтоs_i = f(a_i)иs₀ = f(0). Следовательно, эта схема является совершенной в соответствии с определением 2. “Линейность” данной схемы становится ясна, если записать “разделение секрета” в векторно-матричном виде:

s = fH, (18.3)

где s = (s₀, …, s_n), f = (f₀, …, f_k–1), k × (n+1)— матрицаH = (h_ij) = (a_i^j-1)иh₀₀ = 1. Заметим, что любыеkстолбцов этой матрицы линейно независимы, а максимально возможное число столбцов матрицыHравноq, чтобы добиться обещанного значенияq+1надо добавить столбец, соответствующий точке “бесконечность”.

Возьмем в (18.3) в качестве Hпроизвольнуюr × (n + 1)-матрицу с элементами из поляK. Получаемую СРС, будем называтьодномерной линейной СРС. Она является совершенной комбинаторной СРС со структурой доступаГ, состоящей из множествАтаких, что векторh₀представим в виде линейной комбинации векторов{h_j: j  A}, гдеh_j— этоj-ый столбец матрицыH. Строками матрицыV, соответствующей данной СРС, являются, как видно из (18.3), линейные комбинации строк матрицыH. Перепишем (18.3) в следующем виде

s_j = (f, h_j)дляj = 0, 1, …, n,

где (f, h_j) — скалярное произведение векторов f и h_j. Если А  Г, т.е. если h₀ = Σλ_jh_j, то

s₀ = (f, h₀) = = Σλ_j(f, h_j) = Σλ_js_j

и, следовательно, значение секрета однозначно находится по его “проекциям”. Рассмотрим теперь случай, когда вектор h₀не представим в виде линейной комбинации векторов{h_j: j  A}. Нам нужно показать, что в этом случае для любых заданных значений координат из множестваАчисло строк матрицыVс данным значением любой координаты не зависит от этого значения. В этом не трудно убедится, рассмотрев (18.3) как систему линейных уравнений относительно неизвестныхf_iи воспользовавшись тем, что система совместна тогда и только тогда, когда ранг матрицы коэффициентов равен рангу расширенной матрицы, а число решений у совместных систем одинаково и равно числу решений однородной системы.

Указание. Рассмотрите две системы:c“нулевым” уравнением и без него (т.е. со свободным членом). Так как векторh₀не представим в виде линейной комбинации векторов{h_j: j  A}, то ранг матрицы коэффициентов второй системы на 1 больше ранга матрицы коэффициентов первой системы. Отсюда немедленно следует, что если первая система совместна, то совместна и вторая при любомs₀.

Эта конструкция подводит нас к определению общей линейной СРС. Пусть секрет и его “проекции” представляются как конечномерные векторы s_i = (s, …, s)и генерируются по формулеs_i = fH_i, гдеH_i— некоторыеr × m_i-матрицы. Сопоставим каждой матрицеH_iлинейное пространствоL_iее столбцов (т.е. состоящее из всех линейных комбинаций вектор-столбцов матрицыH_i). Несложные рассуждения, аналогичные приведенным выше для одномерного случая (всеm_i = 1), показывают, что данная конструкция дает совершенную СРС тогда и только тогда, когда семейство линейных подпространств{L₀, …, L_n}конечномерного векторного пространстваKудовлетворяет упомянутому выше свойству “все или ничего”. При этом множествоАявляется разрешенным{L_a: a  A}содержит подпространствоL₀целиком. С другой стороны, множествоАявляется неразрешенным (А  Г), если и только если линейная оболочка подпространств{La: a  A}пересекается с подпространствомL₀только по вектору0. Отметим, что если бы для некоторогоАпересечениеL₀и линейной оболочки{L_a: a  A}было нетривиальным, то участникиАне могли бы восстановить секрет однозначно, но получали бы некоторую информацию о нем, т.е. схема не была бы совершенной.

Пример 18.3. Рассмотрим следующую структуру доступа для случая четырех участников, задаваемуюГ_min = {{1,2}, {2,3}, {3,4}}. Она известна как первый построенный пример структуры доступа, для которой не существует идеальной реализации. Более того, было доказано, что для любой ее совершенной реализацииR(Г) ≥ 3/2. С другой стороны, непосредственная проверка показывает, что выбор матрицH₀,H₁, ...,H₄, приведенных на рис. 18.2, дает совершенную линейную СРС сR = 3/2, реализующую эту структуру, которая, следовательно, является и оптимальной (наиболее экономной) СРС.

Рис. 18.2.Матрицы, реализующие совершенную линейную СРС