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

Идеальное разделение секрета и матроиды - часть 2


Матроидом называется конечное множество и семейство его подмножеств, называемых независимыми (остальные множества называются зависимыми), если выполнены следующие свойства:

Пример 4.  

Множество - это множество векторов в некотором линейном векторном пространстве, а независимые подмножества - это линейно независимые подмножества векторов.

Собственно с этого примера и началась теория матроидов, вначале как попытка дать аксиоматическое определение линейной независимости векторов через ``внутренние свойства'', т.е. не апеллируя к понятию вектора. К счастью, попытка не удалась, так как нашлись матроиды, не представимые как линейные (т.е. как системы векторов), а сама теория матроидов разрослась далеко за пределы ``линейной алгебры'' (см. []).

Пример 5. (матроид Вамоса)  

Рассмотрим следующее множество: и положим , , и . Матроид Вамоса определяется как матроид, в котором множества , , , , , а также все подмножества из пяти или более элементов являются зависимыми. Известно, что этот матроид не является линейным.

Матроид также можно определить через так называемую ранговую функцию матроида, определяемую как максимальная мощность независимого подмножества . Очевидно, что независимые множества (и только они) задаются условием . Ранговая функция матроида обладает свойствами

Обратно, пусть некоторая функция обладает свойствами . Назовем независимыми те множества , для которых .

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

Теперь мы можем сформулировать основной результат.

Теорема . ([])   Для любой БД-совершенной идеальной СРС, реализующей структуру доступа , независимые множества, определяемые условием

, задают связный матроид на множестве

. Все циклы этого матроида, содержащие точку , имеют вид , где

.

Главным в доказательстве теоремы является ``проверка'' целочисленности функции . В самом деле, очевидно обладает остальными свойствами  и, следовательно, при условии целочисленности является ранговой функцией и задает матроид. Доказательство этой теоремы и несколько более общих утверждений можно найти в [].




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


[an error occurred while processing this directive]