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

Next: Литература к главе 5 Up: 5. Математика разделения секрета Previous: 5.3. Линейное разделение секрета Contents: Содержание

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

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

Для произвольного множества $B\subseteq \{0,1,\dots,n\}$ обозначим через $M\times \vert B\vert$ -матрицу, полученную из матрицы удалением столбцов, номера которых не принадлежат множеству . Пусть $\vert\vert W\vert\vert$ обозначает число различных строк в матрице .

Определение 3. Матрица задает БД-совершенную СРС, реализующую структуру доступа $\Gamma$ , если labeli4

$\begin{displaymath} \vert\vert V_{A \cup 0}\vert\vert=\vert\vert V_A\vert\vert \times \vert\vert V_0\vert\vert^{\delta_{\Gamma}(A)}, \tag{4} \end{displaymath}$ (4)

где $\delta_{\Gamma}(A)=0$ , если $A\in \Gamma$ , и $\delta_{\Gamma}(A)=1$ в противном случае.

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

Для произвольной комбинаторной СРС, задаваемой матрицей , определим на множествах $A\subseteq \{0,1,\ldots,n\}$ функцию $h(A)= \log_q\vert\vert V_A\vert\vert,$ где $q=\vert{\cal S}_0\vert.$ Легко проверить, что $\max \{h(A),h(B)\}\leq h(A\cup B)\leq \leq h(A)+h(B)$ для любых множеств и , а условие (4) может быть переписано в виде

$\begin{displaymath}h_q(V_{A \cup 0})=h_q(V_A) + \delta_{\Gamma}(A) h_q(V_0), \end{displaymath}$

Лемма . Для любой БД-совершенной СРС если $A\notin \Gamma$ и $\{A\cup i\} \in \Gamma$ , то $h(i) \geq h(0)$ .

Доказательство. По условиям леммы $h(A\cup 0)=h(A)+h(0)$ и $h(A\cup i\cup 0)=h(A\cup i)$ . Следовательно,

$\begin{displaymath}h(A)+h(i)\geq h(A\cup i)=h(A\cup i\cup 0)\geq h(A\cup 0)=h(A)+h(0). \qquad\qquad{}_\blacksquare \end{displaymath}$

Так как мы предполагаем, что все точки $i\in \{1,\ldots,n\}$ существенные, т.е. для любого найдется подмножество такое, что $A\notin \Gamma$ и $\{A\cup i\} \in \Gamma$ , то из леммы вытекает

Следствие . Для любой БД-совершенной СРС $\vert{\cal S}_i\vert\geq \vert{\cal S}_0\vert$ для всех $i\double=1,\dots,n$ .

Следствие означает, как мы и предупреждали в начале статьи, что для совершенных СРС ``размер'' проекции не может быть меньше ``размера'' секрета. Поэтому БД-совершенная СРС называется идеальной, если $\vert{\cal S}_i\vert\double= \vert{\cal S}_0\vert$ для всех $i=1,\dots,n$ .

Замечание . Неравенство $\vert{\cal S}_i\vert\geq \vert{\cal S}_0\vert$ справедливо и для совершенных вероятностных СРС, поскольку их матрицы задают БД-совершенные СРС.

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

Матроидом называется конечное множество и семейство его подмножеств, называемых независимыми (остальные множества называются зависимыми), если выполнены следующие свойства:
$\begin{gather} \emptyset \in I ; \tag{5.1}\\ {\mbox {Если}} \; A\in I \;{\mbox... ...n A\backslash B \;{\mbox {такое, что}} \;a\cup B \in I. \tag{5.3} \end{gather}$

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

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

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

Матроид также можно определить через так называемую ранговую функцию матроида, определяемую как максимальная мощность независимого подмножества $B\subseteq A$ . Очевидно, что независимые множества (и только они) задаются условием $r(A)=\vert A\vert$ . Ранговая функция матроида обладает свойствами
$\begin{gather} r(A)\in Z, \; r(\emptyset)=0 ;\tag{6.1} \\ r(A)\leq r(A\cup b)\l... ...(A\cup c)=r(A),\; {\mbox {то}} \; r(A\cup b\cup c)=r(A). \tag{6.3} \end{gather}$

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

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

Теорема . ([3]) Для любой БД-совершенной идеальной СРС, реализующей структуру доступа $\Gamma$ , независимые множества, определяемые условием $\log_{\vert{\cal S}_0\vert}\vert\vert V_A\vert\vert=\vert A\vert$ , задают связный матроид на множестве $\{0,1,\dots,n\}$ . Все циклы этого матроида, содержащие точку , имеют вид $0\cup A$ , где $A\in \Gamma_{\min}$ .

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

Отметим, что из второй части утверждения теоремы следует, что разным идеальным СРС, реализующим данную структуру доступа $\Gamma$ , всегда соответствует один и тот же матроид, поскольку матроид однозначно определяется всеми циклами, проходящими через фиксированную точку (см. [6]). Тем самым, каждой идеально реализуемой структуре доступа соответствует однозначно определенный матроид.

В связи с теоремой возникает несколько естественных вопросов. Прежде всего, не порождают ли идеальные СРС все матроиды? Нет, например, матроид Вамоса не может быть получен как матроид идеальной СРС [8]. С другой стороны, линейные матроиды есть ни что иное как рассмотренные в разделе 3 идеальные одномерные линейные СРС. В связи с этим возникает вопрос о существовании структуры доступа $\Gamma$ , которую невозможно реализовать в виде идеальной одномерной линейной СРС, но можно в виде идеальной многомерной линейной СРС. Недавно такой пример был построен [9], и, значит, мы можем говорить о многомерных линейных матроидах как классе матроидов более общем, чем линейные.

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