Введение в криптографию




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


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

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

Определение 3.  

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

(4)


где , если , и

в противном случае.

Это определение отличается от

и  тем, что на неразрешенные множества накладывается довольно слабое условие, а именно, если множество строк с данными значениями координат из множества непусто, то все возможные значения секрета встречаются в нулевой координате этих строк (без требований ``одинаково часто'' как в комбинаторном

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

Для произвольной комбинаторной СРС, задаваемой матрицей , определим на множествах функцию

где Легко проверить, что

для любых множеств и , а условие (4) может быть переписано в виде

Лемма .   Для любой БД-совершенной СРС если и , то .

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

. Следовательно,

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

Следствие .   Для любой БД-совершенной СРС

для всех .

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

Замечание .  

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

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




Содержание  Назад  Вперед