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

Линейное разделение секрета - часть 2


Указание. Рассмотрите две системы: без ``нулевого'' уравнения (т.е. со свободным членом) и с ним. Так как вектор не представим в виде линейной комбинации векторов , то ранг матрицы коэффициентов второй системы на 1 больше ранга матрицы коэффициентов первой системы. Отсюда немедленно следует, что если первая система совместна, то совместна и вторая при любом .

Эта конструкция подводит нас к определению общей линейной СРС. Пусть секрет и его ``проекции'' представляются как конечномерные векторы

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

Пример 3.  

Рассмотрим следующую структуру доступа для случая четырех участников, задаваемую

Она известна как первый построенный пример структуры доступа, для которой не существует идеальной реализации. Более того, было доказано, что для любой ее совершенной реализации

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

Таблица 1.

Next: 5.4. Идеальное разделение секрета

Up: 5. Математика разделения секрета

Previous: 5.2. Разделение секрета для

Contents:




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


[an error occurred while processing this directive]