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

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

Для произвольного множества В  {0, 1, …, n}обозначим черезV_B M × |B|-матрицу, полученную из матрицыVудалением столбцов, номера которых не принадлежат множествуВ. Пусть||W||обозначает число различных строк в матрицеW.

Определение 18.3

Матрица Vзадает БД-совершенную СРС, реализующую структуру доступаГ, если

||V_A0|| = ||V_A|| × ||V₀||^{δГ (А)}, (18.4)

где δ_Г (А) = 0, еслиА  Г, иδ_Г (А) = 1 в противном случае.

Это определение отличается от определений 1 и 2 тем, что на неразрешенные множества Анакладываются довольно слабое условие, а именно, если множество строкVс данными значениями координат из множестваАнепусто, то все возможные значения секрета встречаются в нулевой координате этих строк (без требований “одинаково часто” как в комбинаторном определении 2 или же “с априорной вероятностью” как в вероятностном определении 1). Легко видеть, что матрица любой совершенной вероятностной СРС задает БД-совершенную СРС, но обратное неверно.

Для произвольной комбинаторной СРС, задаваемой матрицей V, определим на множествахА  {0, 1, …, n}функциюh(A) = log_q ||V_A||, где q = |S₀|. Легко проверить, чтоmax{h(A), h(B)}  h(A  B)  h(A) + h(B)для любых множествАиВ, а условие (184) может быть переписано в виде

h_q(V_A0) = h_q(V_A) + δ_Г (А) h_q(V₀)

Лемма. Для любой БД-совершенной СРС если А  Г и {A  i}  Г, то h(i)  h(0).

Доказательство. По условиям леммы

h(A  0) = h(A) + h(0) и h(A  i  0) = h(A  і). Следовательно,

h(A) + h(i)  h (A  і) = h (A  і  0)  h(A  0) = h(A) + h(0)

Так мы предполагаем, что все точки і  {1, …, n}существенные, т.е. для любогоінайдется подмножествоАтакое, чтоА  Ги{A  і}  Г, то из леммы вытекает

Следствие. Для любой БД-совершенной СРС|S_i|  |S₀|для всехі = 1, ..., n.

Следствие означает, как отмечалось выше, что для совершенных СРС “размер” проекции не может быть меньше “размера” секрета. Поэтому БД-совершенная СРС называется идеальной, если |S_i| = |S₀|для всехі = 1, ..., n.

Замечание. Неравенство|S_i|  |S₀| справедливо и для совершенных вероятностных СРС, поскольку их матрицы задают БД-совершенные СРС.

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

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

  I; (18.5.1)

Если A  I и B  A, то B  I; (18.5.2)

Если A, B  I и |A| = |B| + 1,

то существует a A\Bтакое, чтоa  B  I. (18.5.3)

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

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

Пример 18.5. (матроид Вамоса). Рассмотрим следующее множество:Х = {1, 2, 3, 4, 5, 6, 7, 8}и положимa = {1, 2}, b = {3, 4}, c = {5, 6}иd = {7, 8}. Матроид Вамоса определяется как матроид, в котором множестваa  c, a  d, b  c, b  d, c  d, а также все подмножества из пяти или более элементов являются зависимыми. Известно, что этот матроид не является линейным.

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

r(A) Z; r() = 0; (18.6.1)

r(A)  r(A  b)  r(A) + 1; (18.6.2)

Если r(A  b) = r (A  c) = r(A), тоr (A  b  c) = r(A). (18.6.3)

Обратно, пусть некоторая функция r(A)обладает свойствами (18.6). Назовем независимыми те множестваА, для которыхr(A) = |A|. Тогда эти множества задают матроид, а функцияrявляется его ранговой функцией. Возможно также определить матроид через минимальные зависимые множества, называемые циклами. Матроид называетсясвязным, если для любых двух его точек существует содержащий их цикл.

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

Теорема. Для любой БД-совершенной идеальной СРС, реализующей структуру доступаГ, независимые множества, определяемые условиемlog|_S0| ||VA|| = |A|, задают связный матроид на множестве{0, 1,…, n}. Все циклы этого матроида, содержащие точку0, имеют вид0  А, гдеА  Г_min.

Доказательство теоремы приведено в соответствующей литературе и выходит за рамки данной книги. Главным в доказательстве теоремы является “проверка” целочисленности функции h(A). В самом деле,h(A)очевидно обладает остальными свойствами (6) и, следовательно, при условии целочисленности является ранговой функцией и задает матроид.

Отметим, что из второй части утверждения теоремы следует, что разным идеальным СРС, реализующим данную структуру доступа Г, всегда соответствует один и тот же матроид, поскольку матроид однозначно определяется всеми циклами, проходящими через фиксированную точку. Тем самым, каждой идеальной реализуемой структуре доступа соответствует однозначно определенный матроид.

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

Итак, идеальных СРС больше, чем линейных матроидов, но меньше, чем всех матроидов. Уточнить, насколько больше, представляется довольно сложной задачей. В частности, существует ли идеально реализуемая структура доступа Г, которую невозможно реализовать как идеальную линейную многомерную СРС?