On homogeneous matroids and block-schemes.pdf Разграничение доступа на основе схем разделения секрета (СРС) состоит в том, чтобы заранее заданные (разрешённые) коалиции участников могли однозначно восстановить секрет, а неразрешённые не получали никакой дополнительной (к имеющейся априорной) информации о возможном значении секрета. Такие СРС называются совершенными [1, 2]. Идеальными называются СРС, где размер доли секрета, предоставляемый каждому участнику, равен размеру самого секрета. Если разрешёнными коалициями являются любые множества из к или более элементов, то такие СРС называются пороговыми «к из N»» СРС, где N - количество всех участников [1, 3, 4]. Как известно [1, 3, 5], разрешённые коалиции идеальной совершенной схемы разделения секрета определяются циклами некоторого связного матроида, изучение которого и даёт структуру доступа. Общая проблема описания матроидов, соответствующих СРС, пока не решена [1]. Актуальной задачей является описание однородных СРС [6], т. е. таких, где мощность всех разрешённых коалиций равна k, но, возможно, не все k-элементные множества входят в структуру доступа СРС. Под однородностью матроида понимается одинаковость мощностей его циклов, равная n, где, возможно, не все n-элементные множества - циклы. При этом если все n-элементные подмножества - циклы, то такой матроид называется пороговым (равномерным). Матроид называется связным, если для любых двух его элементов существует содержащий их цикл. Для исключения незаменимых участников идеальной СРС имеет смысл рассматривать только разделяющие матроиды. Матроид разделяющий тогда и только тогда, когда для любых x = y существует разделяющий их цикл C, т. е. x Е C, y Е C. Теорема Зингера [7, 8] связывает конечные геометрии с блок-схемами. Это мотивирует к рассмотрению класса однородных матроидов, основанных на блок-схемах. Будем понимать под блок-схемой, согласно [8], такое размещение v различных элементов по b блокам, что каждый блок содержит точно к различных элементов, каждый элемент появляется точно в r различных блоках и каждая пара различных элементов появляется в Л блоках. При этом блок-схема c к = 3 , v = 1, 3 (mod 6) и Л = 1 называется семейством троек Штейнера [8]. Заметим, что семейство троек Штейнера удовлетворяет аксиомам гиперплоскостей [9]. Утверждение 1. Матроид, у которого когиперплоскости - тройки Штейнера, является однородным связным и разделяющим, если его мощность не меньше семи. Утверждение 2. Нетривиальная блок-схема с Л =1 задает когиперплоскости однородного связного разделяющего матроида. Семейства циклов и когиперплоскостей построенного таким образом однородного матроида оказываются дополнительными блок-схемами [8]. Утверждение 3. Блок-схема с Л = 2 не удовлетворяет аксиомам гиперплоскостей. Приведённые утверждения позволяют выдвинуть следующие гипотезы. Гипотеза 1. Однородный матроид определяется некоторой блок-схемой. Гипотеза 2. Каждому однородному матроиду, основанному на блок-схеме, соответствует идеальная схема разделения секрета. Таким образом, однородные матроиды оказываются связанными с блок-схемами и идеальными схемами разделения секрета.

Скачать электронную версию публикации