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

Начнем с определения идеальных СРС. Для этого вернемся к комбинаторному определению совершенной СРС. Следующее определение совершенной СРС является даже более общим, чем вероятностное определение 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) и, следовательно, при условии целочисленности является ранговой функцией и задает матроид.

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

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

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

Секретность и имитостойкость

Криптографические преобразования обеспечивают решение двух главных проблем ЗИ: проблемы секретности (лишение противника возможности извлечь информацию из канала связи) и проблемы имитостойкости (лишение противника возможности ввести ложную информацию в канал связи или изменить сообщение так, чтобы изменился его смысл).

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