Введение в криптографию
[an error occurred while processing this directive]

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


Начнем с предложенной А. Шамиром [] элегантной схемы разделения секрета для пороговых структур доступа. Пусть конечное поле из элементов (например, - простое число и ) и n.$" width="47" height="28" > Сопоставим участникам различных ненулевых элементов поля и положим . При распределении секрета дилер СРС генерирует независимых равномерно распределенных на случайных величин ( ) и посылает -му участнику () ``его'' значение многочлена

, где . Поскольку любой многочлен степени однозначно восстанавливается по его значениям в произвольных точках (например, по интерполяционной формуле Лагранжа), то любые участников вместе могут восстановить многочлен и, следовательно, найти значение секрета как . По этой же причине для любых участников, любых полученных ими значений проекций и любого значения секрета существует ровно один ``соответствующий'' им многочлен, т.е. такой, что и . Следовательно, эта схема является совершенной в соответствии с . ``Линейность'' данной схемы становится ясна, если записать ``разделение секрета'' в векторно-матричном виде:

(3)

где , -матрица

и . Заметим, что любые столбцов этой матрицы линейно независимы, а максимально возможное число столбцов матрицы равно , и чтобы добиться обещанного в разделе  значения надо добавить столбец, соответствующий точке ``бесконечность''.

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

Возьмем в в качестве произвольную -матрицу с элементами из поля . Получаемую СРС будем называть одномерной линейной СРС. Она является совершенной комбинаторной СРС со структурой доступа , состоящей из множеств таких, что вектор представим в виде линейной комбинации векторов где это -ый столбец матрицы Строками матрицы , соответствующей данной СРС являются, как видно из , линейные комбинации строк матрицы . Перепишем

в следующем виде

где - скалярное произведение векторов и . Если , т.е. если , то

и, следовательно, значение секрета однозначно находится по его ``проекциям''. Рассмотрим теперь случай, когда вектор не представим в виде линейной комбинации векторов . Нам нужно показать, что в этом случае для любых заданных значений координат из множества число строк матрицы с данным значением нулевой координаты не зависит от этого значения. В этом нетрудно убедиться, рассмотрев как систему линейных уравнений относительно неизвестных и воспользовавшись тем, что система совместна тогда и только тогда, когда ранг матрицы коэффициентов равен рангу расширенной матрицы, а число решений у совместных систем одинаково и равно числу решений однородной системы.




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]