Линейное разделение секрета
Начнем с предложенной А. Шамиром [] элегантной схемы разделения секрета для пороговых структур доступа. Пусть конечное поле из элементов (например, - простое число и ) и n.$" width="47" height="28" > Сопоставим участникам различных ненулевых элементов поля и положим . При распределении секрета дилер СРС генерирует независимых равномерно распределенных на случайных величин ( ) и посылает -му участнику () ``его'' значение многочлена
, где . Поскольку любой многочлен степени однозначно восстанавливается по его значениям в произвольных точках (например, по интерполяционной формуле Лагранжа), то любые участников вместе могут восстановить многочлен и, следовательно, найти значение секрета как . По этой же причине для любых участников, любых полученных ими значений проекций и любого значения секрета существует ровно один ``соответствующий'' им многочлен, т.е. такой, что и . Следовательно, эта схема является совершенной в соответствии с . ``Линейность'' данной схемы становится ясна, если записать ``разделение секрета'' в векторно-матричном виде:
|
(3) |
где , -матрица
и . Заметим, что любые столбцов этой матрицы линейно независимы, а максимально возможное число столбцов матрицы равно , и чтобы добиться обещанного в разделе значения надо добавить столбец, соответствующий точке ``бесконечность''.
Упражнение. Придумайте сами, как это сделать.
Возьмем в в качестве произвольную -матрицу с элементами из поля . Получаемую СРС будем называть одномерной линейной СРС. Она является совершенной комбинаторной СРС со структурой доступа , состоящей из множеств таких, что вектор представим в виде линейной комбинации векторов где это -ый столбец матрицы Строками матрицы , соответствующей данной СРС являются, как видно из , линейные комбинации строк матрицы . Перепишем
в следующем виде
где - скалярное произведение векторов и . Если , т.е. если , то
и, следовательно, значение секрета однозначно находится по его ``проекциям''. Рассмотрим теперь случай, когда вектор не представим в виде линейной комбинации векторов . Нам нужно показать, что в этом случае для любых заданных значений координат из множества число строк матрицы с данным значением нулевой координаты не зависит от этого значения. В этом нетрудно убедиться, рассмотрев как систему линейных уравнений относительно неизвестных и воспользовавшись тем, что система совместна тогда и только тогда, когда ранг матрицы коэффициентов равен рангу расширенной матрицы, а число решений у совместных систем одинаково и равно числу решений однородной системы.
Указание. Рассмотрите две системы: без ``нулевого'' уравнения (т.е. со свободным членом) и с ним. Так как вектор не представим в виде линейной комбинации векторов , то ранг матрицы коэффициентов второй системы на 1 больше ранга матрицы коэффициентов первой системы. Отсюда немедленно следует, что если первая система совместна, то совместна и вторая при любом .
Эта конструкция подводит нас к определению общей линейной СРС. Пусть секрет и его ``проекции'' представляются как конечномерные векторы
и генерируются по формуле где - некоторые -матрицы. Сопоставим каждой матрице линейное пространство ее столбцов (т.е. состоящее из всех линейных комбинаций вектор-столбцов матрицы ). Несложные рассуждения, аналогичные приведенным выше для одномерного случая (все ), показывают, что данная конструкция дает совершенную СРС тогда и только тогда, когда семейство линейных подпространств конечномерного векторного пространства удовлетворяет упомянутому во введении свойству ``все или ничего''. При этом множество является разрешенным (), если и только если линейная оболочка подпространств содержит подпространство целиком. С другой стороны, множество является неразрешенным ( ), если и только если линейная оболочка подпространств пересекается с подпространством только по вектору . Отметим, что если бы для некоторого пересечение и линейной оболочки было нетривиальным, то участники не могли бы восстановить секрет однозначно, но получали бы некоторую информацию о нем, т.е. схема не была бы совершенной.
Пример 3.
Рассмотрим следующую структуру доступа для случая четырех участников, задаваемую
Она известна как первый построенный пример структуры доступа, для которой не существует идеальной реализации. Более того, было доказано, что для любой ее совершенной реализации
. С другой стороны, непосредственная проверка показывает, что выбор матриц , приведенных в табл. 1, дает совершенную линейную СРС с , реализующую эту структуру, которая, следовательно, является и оптимальной (наиболее экономной) СРС.
Up: 5. Математика разделения секрета
Previous: 5.2. Разделение секрета для
Contents: