Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ПРИК Л АДНАЯ Д ИСКРЕТНА Я МАТЕМ АТ И К А
2008 Математические методы криптографии № 2(2)
УДК 519.7
СОВЕРШЕННЫЕ СХЕМЫ РАЗДЕЛЕНИЯ СЕКРЕТА
Н.Г. Парватов
Томский государственный университет
E-mail: parvatov@mail.tsu.ru
В статье излагаются некоторые известные результаты теории разделения секрета.
Ключевые слова: совершенная схема разделения секрета, структура доступа, идеальное разделение сек-
рета, полиматроид, матроид.
В теории разделения секрета рассматривается задача, которую неформально можно поставить следую-
щим образом. Требуется разделить значение секрета из некоторого множества секретов между участниками
из некоторого множества участников, выдав каждому участнику его долю секрета так, чтобы заранее опре-
делённые, авторизованные, множества участников могли, соединив свои доли, вычислить истинное значе-
ние секрета, а участники остальных, неавторизованных, множеств не могли бы этого сделать. Иногда требу-
ется, чтобы участники неавторизованных множеств, пытаясь восстановить истинное значение секрета, не
могли бы исключить ни одного значения из множества секретов, или даже не получили бы никакой допол-
нительной информации о секрете. Данная задача может возникнуть при разделении доступа между группой
лиц, не доверяющих друг другу, а также при хранении конфиденциальной информации, разделённой на час-
ти. Несмотря на то, что в настоящее время имеется довольно обширный перечень публикаций по разделе-
нию секрета, некоторые ключевые статьи достать довольно трудно. Столкнувшись с этой трудностью, автор
вынужден был самостоятельно восстанавливать систему первоначальных понятий теории разделения секре-
та и получать некоторые основные результаты этой теории. О некоторых из этих результатов и пойдёт речь
далее.
Структура доступа
Структурой доступа (сд) на множестве Q станем называть всякое подмножество G системы B(Q) всех
подмножеств множества Q, обладающее свойством монотонности:
.если часть множества A⊆ Q принадлежит G, то и само A принадлежит G..
Множества, принадлежащие сд, станем называть авторизованными в ней. Система всех минимальныx по
включению авторизованных множеств сд G называется её базисом и обозначается G0. Элементы множества
Q называются участниками сд G. Участники, принадлежащие базисным множествам из G0, называются су-
щественными. Пользуясь случаем, введём несколько важных операций над сд. Во-первых, заметим, что для
любого множества U из B(Q) множество B(Q\U)∩G является сд на множестве участников Q\U; эту сд станем
обозначать через GQ\U. Множество всех подмножеств V из B(Q), таких, что U∪V авторизованно в G, образу-
ет сд на Q. Эту сд обозначим через G(U). Наконец, через GQ\U станем обозначать сд G(U)
Q\U, полученную по-
вторным применением первых двух операций. Из данных трёх операций первая и последняя имеют особое
значение и называются операциями взятия миноров. Сд, возникающие из данной сд G в результате (воз-
можно, неоднократного) применения подобных операций, называются минорами G. Отметим, что много-
кратное взятие миноров можно всегда заменить равносильным не более, чем двукратным применением по-
добных операций. Если все участники, принадлежащие множеству U, несущественны в сд G, то миноры
GQ\U и GQ\U совпадают. В этой ситуации будем говорить, что сд G получена из сд GQ\U (равносильно из GQ\U)
путём введения несущественных участников, а сд GQ\U (равносильно сд GQ\U) получена из сд G путём удале-
ния несущественных участников. Классы сд, замкнутые операциями взятия миноров, а также операциями
введения и удаления несущественных участников, станем называть инвариантными. Далее, для сд G на
множестве Q через G* принято обозначать определённую на том же множестве Q сд, в которой авторизован-
ными являются всевозможные дополнениянеавторизованных в G множеств. Ясно, что G**=G. Сд G и G* по
отношению друг к другу принято называть двойственными.
В дальнейшем полезно иметь в виду, что существует взаимно однозначное соответствие
x_U(x)
между булевыми векторами x = (x1, ..., xn) длины n и всевозможными подмножествами U(x) n-элементного
множества Q = {p1, ..., pn}, при котором U(x) = {pi | xi = 1}. Данный факт влечёт существование (обратных по
отношению друг к другу) взаимно однозначных соответствий
f_G( f ), G_f (G)
Совершенные схемы разделения секрета 51
между булевыми функциями f, зависящими от n аргументов x1, ..., xn, и всевозможными системами G под-
множеств множества Q. При этом система G( f ) состоит из всевозможных таких подмножеств U(x), для ко-
торых f (x) = 1, а булева функция f (G) принимает значение 1 на наборе x, если U(x) принадлежит G. Данные
соответствия, в свою очередь, индуцируют взаимно однозначное соответствие между монотонными буле-
выми функциями от n аргументов и структурами доступа на n-элементном множестве. Отметим, что суще-
ственность участника pi из Q в структуре доступа G равносильна тому, что функция f (G) зависит от пере-
менной xi существенно. Отметим также, что функции f (GQ\U) и f(GQ\U) могут быть получены из функции f(G)
подстановкой константы 0 и 1 соответственнона места переменных xi, pi∈U. В свете сказанного легко по-
нятна связь между инвариантными классами структур доступа и инвариантными классами булевых функций
(замкнутыми операциями перестановки переменных, операциями введения и удаления фиктивных перемен-
ных, а также операциями подстановки 0 и 1 на места переменных [1]).
Схема разделения секрета
Договоримся обозначать через AQ множество всевозможных функций s:Q→A. Всякую такую функцию
будем называть также набором, а её значение s(q) будем также обозначать через sq и называть значением
q-координаты набора s. Для любого множества U из B(Q) через sU станем обозначать ограничение sU:U→A,
такое, что sU(q) = s(q) для всех q из U. В дальнейшем нас будут интересовать подмножества множества AQ.
Для всякого такого подмножества S станем обозначать через Sq множество всех q-координат sq и через SU
множество всех ограничений sU для всевозможных наборов s из S. Для набора y из SU через Sy обозначим
множество всех таких наборов s из S, что sU = y. Пусть Q =P ∪{D} и элемент D не принадлежит множеству P.
Набор (S, P, D), где S – непустое подмножество множества AQ, называется схемой разделения секрета (срс).
При этом множество Q называется множеством участников данной срс. Участник D называется дилером.
Множество SD называется множеством секретов, число |SD| его элементов называется порядком срс. Мно-
жество Sq называется множеством долей участника q из P. Наборы из S называются правилами разделения
секрета. Так, s из S − это правило разделения секрета sD, а sq – принадлежащая участнику q доля секрета sD,
разделённого по правилу s. Несложно понять, что всевозможные множества U из B(P), для которых выпол-
няется равенство
|SU∪{D}| = |SU|,
образуют сд, обозначим её через G(S, P), на множестве P. Это − сд, реализуемая срс S. В соответствии с оп-
ределением для любого авторизованного в G(S, P) множества U и любого правила s из S значение sD одно-
значно определяется ограничением sU. Это свойство позволяет использовать срс для решения описанной во
введении задачи разделения секрета. Именно для того, чтобы разделить значение секрета из множества SD
между участниками из множества P так, чтобы авторизованные в G(S, P) множества участников могли вос-
становить секрет, нужно прибегнуть к помощи ещё одного участника, пользующегося всеобщим доверием.
Этот участник выбирает наугад (или в соответствии с некоторым распределением) правило s из S и каждому
участнику q из P в тайне от остальных передаёт долю sq. Отметим, что в описанной ситуации доли участни-
ков из неавторизованного множества могут содержать некоторую (возможно, значительную или даже пол-
ную) информацию о секрете. Чтобы избавить срс от этого нежелательного свойства, понадобятся более
сложные определения, которые будут сделаны далее.
Энтропийная функция
Для непустого подмножества S множества AQ функцию h:B(Q)→[0,+∞) будем называть энтропийной, ес-
ли выполнены условия:
1) h(∅ ) = 0;
2) h(U) ≤ h(V), если U ⊆ V ⊆ Q;
3) h(U ∪ V) + h(U ∩ V) ≤ h(U) + h(V) для любых подмножеств U и V множества Q;
4) если h(U) = h(V) и U ⊆ V ⊆ Q, то |SU| = |SV|.
В частности, равенства h(U) = 0 и |SU| = 1 равносильны. Если говорить неформально, то величина h(U)
(энтропия множества U) призвана задавать степень неопределённости, возникающую при попытках угадать
зафиксированный элемент из SU. Примером энтропийной функции на S может служить комбинаторная эн-
тропия, определённая для всех U из B(Q) как
h(U) = log|SU|,
(логарифмы берутся по фиксированному основанию k > 1), а также энтропия Шеннона (см. [2]), определён-
ная для всех U из B(Q) как
h(U) = −ΣPU(xU)log PU(xU).
Во втором случае предполагается, что на множестве S определено распределение P(x) (ненулевых) веро-
ятностей случайной величины X, которое индуцирует распределение PU(xU) случайной величины XU на
множестве SU, а суммирование ведётся по всем xU из SU; при этом величину h(U) принято называть вероят-
52 Н.Г. Парватов
ностной энтропией, или энтропией Шеннона, случайной величины XU. В обоих случаях все четыре свойст-
ва очевидны, известны или легко проверяются. В первом свойстве предполагается, что множество SU при
пустом U само не пусто, а состоит из единственного пустого набора (см. [2]). Вполне возможно, что имеют
смысл и другие способы определения энтропийной функции, но перечисленные два являются основными.
Имеет смысл при U ⊆ V разность h(V) − h(U) обозначать через h(V|U) и называть условной энтропией мно-
жества V при известном U. Эта величина задаёт остаточную неопределённость вектора sV при известном ог-
раничении sU (и известном S) и может принимать значения от 0 (когда sV однозначно восстанавливается по
известному sU и S) до h(V\U). Отметим, что как комбинаторная, так и вероятностная энтропия h обладает
ещё одним свойством:
5) если h(U ∪ V) + h(U∩V) = h(U) + h(V), то |SU∪V||SU∩V| = |SU||SV|,
из которого следует, что при пустом пересечении U∩V равенство h(U ∪ V) = h(U) + h(V) влечёт
|SU∪V|=|SU||SV|. Последнее означает, что компоненты sU и sV в наборе sU∪V принимают все возможные значения
из множеств SU и SV.
Совершенная срс
Пусть теперь Q = P ∪ {D}, D∉P и h − энтропийная функция на непустоммножестве S ⊆ AQ . Набор
(S, P, D, h) будем называть совершенной срс, если для каждого подмножества U ⊆ P выполняется
h(U, D) = h(U) или h(U, D) = h(U) + h(D).
(Здесь и далее из соображений краткости под знаком функции h опускаются знаки объединения и фигурные
скобки; вместо них используются запятые.) В случае комбинаторной или вероятностной энтропии h будем
говорить соответственно о комбинаторной или вероятностной срс. Те подмножества U, для которых вы-
полняется первое условие, составляют сд G(S, P), реализуемую данной срс. Как уже отмечалось, для таких
подмножеств U имеется возможность для любого правила s из S определить значение sD по проекции sU.
В это же время для неавторизованных в G(S, P) подмножеств U выполняется второе условие, означающее,
что участники этого множества при любом s из S, пытаясь угадать sD по sU, сталкиваются с максимально
возможной неопределённостью. В случае комбинаторной срс это означает, что для любого набора y из SU
найдётся правило s в S такое, что sU = y, обладающее любым наперёд заданным значением sD из SD. А в слу-
чае вероятностной срс это означает, что для любого правила s из S проекция sU не несёт никакой информа-
ции о значении секрета sD.
Скорость срс
В силу вышесказанного об энтропийной функции h возможность эффективного использования срс в зна-
чительной степени определяется величинами h(p) для p из P. Чем они больше, тем больше требуется затрат
для передачи, хранения и обработки долей. Вместе с тем без ущерба для разделения и восстановления сек-
рета несущественным участникам можно не передавать их долей. В связи с этим эффективность совершен-
ной срс (S, P, D, h), реализующей сд G, можно охарактеризовать величиной
r(S, P, D, h) = min(h(p)/h(D)),
где min вычисляется по всевозможным существенным участникам p из ∪G0. Эта величина называется ско-
ростью срс (S, P, D, h). Имеет место
Теорема 1. Пусть совершенная срс (S, P, D, h) реализует сд G. Тогда для любого существенного в G уча-
стника p из P имеет место неравенство h(p) ≤ h(D).
Доказательство. Так как участник p существенный в G, то для некоторого неавторизованного в G
множества U множество U ∪ {p} авторизованно в G. Тогда h(U) + h(p) ≥ h(U, p) = h(U, p, D) ≥ h(U, D) =
= h(U) + h(D). Отсюда h(p) ≥ h(D). Теорема доказана.
Из доказанной теоремы следует, что скорость определена корректно и принимает значения из отрезка
[0, 1], если имеется хотя бы один существенный участник (то есть когда сд G не тривиальна − не пуста и от-
личается от B(P)). Если существенных участников нет, то скорость срс будем считать бесконечной и будем
обозначать её знаком +∞. Срс, имеющие скорость, равную 1 или +∞, называются идеальными.
Одной из основных задач теории разделения секрета является задача создания (синтеза) срс для заданной
сд. При этом требуется в некотором классе найти срс, реализующую заданную сд и имеющую по возможно-
сти максимальную скорость. Этим оправдывается введение для заданного класса C схем разделения секрета
и заданной сд G на множестве P величины
r(C, G) = sup r(S, P, D, h),
где sup берётся по всевозможным срс (S, P, D, h) из класса C, реализующим сд G. Данная величина носит на-
звание скорости сд G в классе C. Отметим, что скорость r(C, G) данной сд G в классе C не обязана дости-
гаться на некоторой срс из C, но может достигаться на некоторой последовательности срс. В частности, ав-
тор не исключает возможности существования сд, имеющей в некотором классе скорость, равную 1, но не
имеющей в этом классе идеальной реализации.
Совершенные схемы разделения секрета 53
Вычислительная эффективность срс
Введённая выше скорость схем разделения секрета в большей степени характеризует их коммуникаци-
онную (связанную с затратами при передаче и хранении долей секрета), нежели вычислительную эффектив-
ность. Последняя определяется вычислительными затратами, необходимыми для разделения и восстановле-
ния секрета. Эти затраты могут быть значительными вне зависимости от энтропии долей. Более прямо вы-
числительную эффективность срс (S, P, D, h) характеризует максимальная схемная сложность l(S, P, D, h)
функции
SU→SD,
определённой для каждого авторизованного множества U следующим образом:
x_y, если x = sU и y = sD для некоторого s из S.
Естественно назвать эту величину сложностью срс (S, P, D, h). В связи с этим представляет интерес задача
нахождения для заданной сд реализующей её срс, принадлежащей заданному классу и имеющей по воз-
можности минимальную сложность. К сожалению, в известных автору работах данная задача не рассмат-
ривалась.
Срс, связанные с группами
Пусть S ⊆ AQ, и для любого элемента q из Q пусть Sq – аддитивная (но не обязательно абелева) группа с
множеством операторов K, действующих левым умножением [3, 4]. Через ΠQSq обозначается прямое произ-
ведение этих групп, состоящее из всевозможных таких наборов s из AQ, что sq∈Sq для любого q из Q, и яв-
ляющееся группой с множеством операторов K, в которой
(s + w)q = sq + wq, (cs)q = csq
для любых s и w из ΠQSq и любого c из K. Пусть также множество S является подгруппой группы ΠQSq (и то-
гда подпрямым произведением групп Sq). В этой ситуации полезно иметь в виду, что для любого подмноже-
ства U ⊆ Q и для нулевого набора 0 из SQ\U каждое из множеств SU и S0 является (K-операторной) подгруп-
пой группы ΠUSq, а для любого набора y из SQ\U множество Sy является смежным классом группы SQ\U по
подгруппе S0. Пусть, наконец, Q = P ∪ {D} и для любого подмножества U ⊆ P верно
|SU∪{D}| = |SU| или |SU∪{D}| = |SU||S{D}|. (1)
Тогда можно определить совершенную комбинаторную срс (S, P, D, h) с ранговой функцией h, такой, что
h(U) = log|S(D)| S(U). Эта срс является одновременно и вероятностной для равномерного распределения веро-
ятностей на S. В некоторых случаях условие (1) выполняется автоматически. Так происходит, например, ко-
гда группа SD простая относительно множества операторов K, то есть имеет ровно две допустимые относи-
тельно K подгруппы (именно тривиальные подгруппы). В частности, именно этот случай имеет место, когда
все Sq являются одномерными векторными пространствами над конечным полем K; в данном случае срс на-
зывается векторной, или линейной одномерной, или срс Брикелла. Если все Sq являются векторными про-
странствами над конечным полем K, но не обязательно одномерными, то срс называется линейной. Срс Бри-
келла представляют особый интерес в связи с их высокой эффективностью (они идеальны и обладают про-
стыми алгоритмами разделения и восстановления секрета). В меньшей степени это относится к линейным
срс (которые могут быть неидеальными). В ещё меньшей степени это относится к срс, связанным с группа-
ми. Последние не обязаны быть идеальными и для них не известны хорошие алгоритмы разделения и вос-
становления секрета.
Инвариантные классы сд
Введённые ранее операции взятия миноров над сд связаны с некоторыми операциями над срс. С этой
целью рассмотрим энтропийную функцию h непустого подмножества S ⊆ AQ и для подмножества U ⊆ Q
определим функции
hQ\U:B(Q\U)→[0,+∞), h(U):B(Q)→[0,+∞) и hQ\U:B(Q\U)→[0,+∞),
положив hQ\U(V) = h(V) для V ⊆ Q\U, h(U)(V) = h(U ∪ V) для V ⊆ Q и hQ\U = h(U)
Q\U. Несложно понять, что дан-
ные функции являются энтропийными для соответствующих множеств SQ\U, Sy и Sy
Q\U, где набор y выбран
произвольно из множества SU. В действительности, имеет место
Теорема 2. Пусть (S, P, D, h) − совершенная срс, реализующая сд G, и Q = P ∪ {D}. Тогда для любого
подмножества U ⊆ P и любого набора y из SU верно:
1) набор (SQ\U, P\U, D, hQ\U) является срс, реализующей сд GP\U;
2) набор (Sy, P\U, D, h(U)) является срс, реализующей сд G(U);
3) набор (Sy
Q\U, P\U, D, hQ\U) является срс, реализующейсд GP\U.
Следствие 1. Для любого r из [0, 1] ∪ {+∞} класс Cr всех сд, чья скорость в классе всех срс не меньше r,
инвариантен. В частности, инвариантен класс всех идеальных срс.
54 Н.Г. Парватов
Отметим, что инвариантность того или иного класса сд позволяет охарактеризовать этот класс посредст-
вом запрещающего множества миноров, подобно тому, как это делается для наследственных классов графов
[5]. Помимо класса Cr имеются и другие важные для приложений инвариантные классы сд, такие, как клас-
сы сд, имеющих векторную (или линейную) реализацию над заданным (или произвольным) конечным по-
лем, класс групповых сд, класс совершенных вероятностных (или комбинаторных) сд, класс сд, имеющих
реализацию порядка, равного заданной величине k или 1. Очевидно, при помощи операций пересечения и
объединения из перечисленных классов снова получаются инвариантные классы. Отметим ещё одно
Следствие 2. Если существует реализующая сд G срс с энтропийной функцией h, то существует реали-
зующая G срс с энтропийной функцией H, такой, что H(p) ≤ h(p) для любого участника p сд G и H(p) = 0 для
любого несущественного в G участника p.
Идеальный матроид
Для заданного класса C совершенных срс, представляющих практическийинтерес, имеет смысл задача
конструктивного описания всех сд, имеющих реализацию в классе C. В частности, данная задача имеет
смысл для класса всех идеальных совершенных срс. В настоящее время данная задача не решена, а наилуч-
шие из известных условий связаны с понятием матроида. Напомним, что полиматроидом на множестве Q
называется пара (Q, h), где h: B(Q)→[0, +∞) − функция, обладающая свойствами (1) − (3) из определения эн-
тропийной функции. В частности, энтропийная функция непустого подмножества S ⊆ AQ определяет поли-
матроид на множестве Q. Полиматроид (Q, h) называется матроидом, если дополнительно выполнено свой-
ство
1) h(U) ∈{0, ..., |U|} для любого U из B(Q).
При этом элементы множества Q называются точками матроида. Функция h называется ранговой функцией
матроида. Её значение h(U) называется рангом множества U∈B(Q). Множества, чья мощность совпадает с
рангом, называются независимыми, в отличие от остальных, зависимых множеств матроида. Минимальные
по включению зависимые множества матроида называются его циклами. Матроид называется связным, если
любые две его точки попадают в некоторый цикл. Известно, что матроид однозначно определяется всеми
своими циклами, проходящими через любую его заданную точку. Имеет место следующая теорема
Теорема 3 (Брикелл, Дэвенпорт). Пусть (S, P, Q, H) − идеальная совершенная срс, реализующая сд G,
не имеющую несущественных участников. Пусть также H(D) = 1. Тогда (Q, H) − матроид, циклами которо-
го, проходящими через точку D, являются всевозможные множества U ∪ {D}, U∈G0.
Замечание. Требование H(D) = 1 не умаляет общности теоремы. Энтропийную функцию H совершенной
срс с этим свойством всегда можно найти, разделив все значения произвольной энтропийной функции h на
h(D), то есть положив H = h/(h(D)).
Вариант доказательства данной теоремы можно найти в [6]. Без доказательства данная теорема приво-
дится в [7]. В [6, 7] можно найти ссылки на оригинальную работу Дэвенпорта и Брикелла, содержащую до-
казательства данной теоремы. Ещё один вариант доказательства будет приведён далее. Для доказательства
понадобятся вспомогательные леммы 1 и 2.
Лемма 1. Пусть в условиях теоремы 3 V∈B(P)\G и множество U∈B(P) минимальное по включению, для
которого выполняется условие V ∪ U∈G. Тогда H(U, V) = H(V) + |U|. В частности, для базисного множества
U∈G0 верно H(U) = |U|.
Доказательство леммы 1. Пусть множество U n-элементное, состоит из элементов p1, ..., pn. Тогда для
любого m, 1 ≤ m ≤ n, верно: H(V, U, D) = H(V, U) ≤ H(V, U \{pm}) + H(pm) = H(V, U \{pm}) + H(D) =
= H(V, U \{pm}, D) ≤ H(V, U, D). Очевидно, что здесьвезде равенства. Учитывая это и используя свойства (2)
и (3) из определения энтропийной функции, получаем H(pm) = H(V, U) − H(V, U \{pm}) ≤ H(V, p1, ..., pm) −
– H(V, p1, ..., pm–1) ≤ H(pm) = H(D) = 1. Очевидно, что и здесь равенства. Используя их при m = 1, ..., n, полу-
чаем, что H(V, p1) = H(V) + H(D) = H(V) + 1 и H(V, p1, p2) = H(V, p1) + H(p2) = H(V, p1) + 1 = H(V) + 2, ...,
h(V, U) = h(V) + |U|. Что и требовалось доказать.
Лемма 2. Пусть в условиях теоремы 3 p∈U и U∈G0. Тогда для любого V∈B(P), такого, что U ⊆ V, верно:
H(V \{p}, D) = H(V, D) = H(V).
Доказательство леммы 2. Легко понять, что H(D) + H(U \{p}) = H(p) + H(U \{p}) ≥ H(U) = H(U, D) ≥
H(U \{p}, D) = H(U \{p}) + H(D). Отсюда следует, что H(U \{p}, D) = H(U, D) = H(U). В силу третьего свой-
ства в определении энтропийной функции H данные равенства будут выполняться и после замены U на V.
Лемма доказана.
Доказательство теоремы 3. Прежде всего докажем, что (Q, H) − матроид. Для этого достаточно прове-
рить целочисленность функции H. Более того, достаточно проверить целочисленность значений H(U) лишь
для авторизованных в G множеств U. Это следует из того, что не авторизованное множество V можно до-
полнить до авторизованного множества U = V ∪ W минимальным по включению множеством W, тогда по
лемме 1 H(U) = H(V, W) = H(V) + |W| и из целочисленности H(U) следует целочисленность H(V). Итак, будем
Совершенные схемы разделения секрета 55
доказывать для авторизованного в G множества U, что значение H(U) − целое. Назовём множество U
m-множеством, если U = U1 ∪ U2 для некоторого m-элементного множества U1 и для некоторого не пересе-
кающегося с ним базисного множества U2. Ясно, что всякое авторизованное множество является m-множе-
ством для некоторого натурального m. Индукцией по m покажем, что H(U) − целое для m-множества U.
Данное утверждение является следствием леммы 1 при m = 0, так как 0-множествами являются базисные
множества. Пусть M > 0, и утверждение имеет место при всех m < M. Докажем его при m = M. Рассмотрим
m-множество U = U1 ∪ U2, где |U1| = m и U2 из G0. Предположим сначала, что U2 − единственное базисное
множество, включённое в U. Тогда по лемме 1 H(U) = H(U1) + |U2| и нужно убедиться, что H(U1) − целое.
Поскольку элементы множества U1 существенны в P, найдётся базисное множество, имеющее непустое пе-
ресечение с U1. Выберем некоторое такое базисное множество U3 с минимальной по включению разностью
U3\U1. Тогда множество U1 ∪ U3 является m'-множеством для некоторого m' < m (именно для m' = |U1\U3|)
и по предположению H(U1, U3) − целое. Так как в силу минимальности U3 по лемме 1
H(U1, U3) = H(U1) + |U3\U1|, то и значение H(U1) − целое. Возвращаясь назад, заключаем, что в рассмотрен-
ном случае H(U) − целое. Осталось рассмотреть случай, когда U включает отличное от U2 базисное множе-
ство, содержащее некоторый элемент p из U1. Так как множество U \{p} авторизовано (ибо оно включает
U2), то H(U \{p}, D) = H(U). По лемме 2 заключаем, что H(U \{p}) = H(U). Поскольку U \{p} = (U1\{p}) ∪ U2,
множество U \{p} является (m−1)-множеством. По предположению индукции значение H(U) = H(U \{p}) −
целое. Итак, доказано, что пара (Q, H) является матроидом. Обратим своё внимание на циклы данного мат-
роида. Прежде всего отметим, что циклами матроида являются такие множества точек, чей ранг на 1 меньше
мощности и чьё любое собственное подмножество имеет ранг, совпадающий с мощностью. В силу этого для
любого цикла U ∪ {D}, где D∉U, верно, что |U| = H(U, D) = H(U) = H(U \{p}, D) = H(U \{p}) + 1 для любого
p из U. Это означает, что U − минимальное авторизованное в G, то есть принадлежит G0. Обратно, если U из
G0, то, учитывая леммы 1 и 2, имеем |U| = H(U) = H(U, D) = H(U \{p},D) для всех p из U. Следовательно,
U ∪ {D} − цикл. Теорема доказана.
Итак, теорема 3 показывает, что энтропийная функция совершенной идеальной срс является ранговой
функцией матроида. Матроиды, получающиеся таким путём, называются идеальными. В настоящее время
известны неидеальные матроиды [7]. В [7] указывается, что матроид, отвечающий совершенной комбина-
торной срс, связный.
Срс и сд Брикелла
Рассмотрим срс Брикелла над конечным полем K и реализуемые ими сд. Такие сд называются сд Брикел-
ла над полем K. Установим необходимые и достаточные условия того, что заданная сд является сд Брикелла
над заданным конечным полем. Итак, пусть (S, P, Q, h) − срс Брикелла над конечным полем K, реализующая
сд G. Выберем в векторном пространстве S порождающий его набор R векторов r1, ..., rm, линейная оболочка
<r1, ..., rm> которых совпадает с S. Для любого q из Q через R(q) обозначим набор (r1q, ..., rmq) и для любого U
из B(Q) через R(U) обозначим множество наборов R(q) для всевозможных q из U. Возникшее таким образом
отображение
R: Q→Km, R: q_R(q)
называется реализацией Брикелла срс (S, P, Q, h) и сд G. Отметим пару свойств реализации R, имеющих ме-
сто для любого подмножества U из B(P).
Свойство 1. Множество U тогда и только тогда авторизовано в G, когда вектор R(D) принадлежит ли-
нейной оболочке <R(U)>. Это следует из того, что rank SV = rank <R(V)> для любого V из B(Q), что в свою
очередь, является простой переформулировкой следующего известного свойства из [3]: строчный ранг мат-
рицы над полем совпадает с её столбцовым рангом.
Свойство 2. Множество U тогда и только тогда не авторизовано в G, когда существует вектор v(U) в Km,
такой, что v(U)•R(D) = 1 (здесь и далее точкой обозначаем скалярное произведение) и v(U)•B(p) = 0 для лю-
бого p из U. Действительно, в силу предыдущего свойства U∈G ⇔ <R(D)> ⊆ <R(U)> ⇔ <R(U)> ⊥ ⊆
<R(D)> ⊥ (в последнем выражении речь идёт об ортогональном дополнении). Следовательно, условие U∈G
равносильно существованию вектора v(U) в <R(U)> ⊥ \<R(D)> ⊥ . Иными словами, вектор v(U) ортогонален
всем векторам R(p), таким, что p∈U, и не ортогонален вектору B(D). Очевидно, вектор v(U) можно выбрать
так, что v(U)• R(D) = 1. Тем самым свойство 2 доказано. Имеет место
Теорема 4. Пусть G − сд с множеством участников P. Если G − сд Брикелла над конечным полем K, то
существует пара функций
d: G0Ч P→K и d*: G*
0Ч P→K,
обладающих следующими свойствами:
1) d(U, p) ≠ 0 и d*(V, q) ≠ 0, если p∈U∈G0 и q∈V∈G*
0;
2) d(U, p) = 0 и d*(V, q) = 0, если p∉U∈G0 и q∉V∈G*
0;
3) Σd(U, p)d*(V, p) = 1 для любых U∈G0 и V∈G*
0, где суммирование ведётся в K по всевозможным p из P.
56 Н.Г. Парватов
Обратно, если существуют функции d и d*, обладающие свойствами 2) и 3), то сд G является сд Брикелла
над K.
Доказательство. Необходимость. Пусть G − сд Брикелла над конечным полем K с реализацией R:
Q→Km. Пусть V − множество из G*
0. Тогда P \V − максимальное неавторизованное в G. В силу второго свой-
ства существует вектор v = v(P \V) в Km, такой, что v•R(D) = 1 и v•R(p) = 0 для любого p∈P \V. Отметим, что в
силу максимальности множества P \V скалярные произведения v•R(p) при p∈V не равны нулю. Пусть также
U − минимальное авторизованное в G множество из G0. Тогда в силу первого свойства вектор R(D) выража-
ется линейно через вектора B(p), где p из U, с ненулевыми (в силу минимальности U) коэффициентами. Обо-
значим эти коэффициенты через d(U, p) так, что B(D) = Σd(U, p)R(p), и положим d(U, p) = 0 для всех p из
P\U. Тогда 1 = v•R(D) = v•Σd(U, p)R(p) = Σd(U, p)(v•R(p)). Остаётся положить d*(V, p) = v•R(p). Докажем дос-
таточность. С этой целью будем считать заданными величины d(U, p) и d*(V, p), обладающие вторым и
третьим свойствами. Пусть множество G*
0 состоит из множеств V1, ..., Vm. Зададим функцию R: Q→Km так,
что R(D) = (1, ..., 1) и R(p) = (d*(V1, p), ..., d*(Vm, p)) для всех p из P. Легко понять, что для любого U из G0
вектор R(D) выражается линейно через вектора R(p), p из U с коэффициентами d(U, p); это следует из второ-
го и третьего свойств. Если же U – максимальное не авторизованное в G множество, то разность P \U совпа-
дает с некоторым множеством Vi. Тогда всякий вектор R(p), где p из U, имеет 0 в i-й координате, а значит,
вектор R(D) = (1, ..., 1) нельзя выразить линейной комбинацией этих векторов. Отмеченные свойства функ-
ции R говорят о том, что она является реализацией Брикелла сд G. Теорема доказана. Непосредственно из
теоремы получаем
Следствие 3. Сд G на множестве P тогда и только тогда является сд Брикелла над конечным полем K,
когда над этим полем относительно переменных d(U, p) и d*(V, q), где p∈U∈G0 и q∈V∈G*
0, разрешима сис-
тема уравнений Σd(U, p)d*(V, p) = 1 (сумма по всем p из U∩V) для всевозможных значений U∈G0 и V∈G*
0.
В случае двухэлементного поля K = Z2 получаем
Следствие 4 [10]. Сд G тогда и только тогда является сд Брикелла над полем Z2, когда для любого мно-
жества U из G и любого множества V из G*
0 пересечение U∩V содержит нечётное число элементов.
Данное следствие было опубликовано с доказательством в [6]. Теорема 4 является непосредственным
обобщением этого результата.
Замечание. Следствие 3 сводит вопрос о существовании реализации Брикелла над полем K для заданной
сд G к разрешимости над K некоторой системы уравнений. Причём, как видно из доказательства теоремы 4,
решение данной системы даёт реализацию Брикелла данной сд, впрочем, возможно неэффективную (с
большим m). В [9] описывается алгоритм, распознающий совместность системы полиномиальных уравнений
над алгебраически замкнутым полем. В соответствии с этим алгоритмом нужно найти редуцированный ба-
зис Грёбнера идеала, порождённого системой многочленов (определяющих систему уравнений). Тогда сис-
тема оказывается совместной, если редуцированный базис не состоит из одного единичного многочлена.
При нахождении редуцированного базиса методом Бухбергера из [9] все вычисления происходят в кольце
многочленов над фиксированным полем. В частности, если коэффициенты системы целочисленные (как в
нашем случае), то все вычисления будут происходить в простом поле заданной характеристики. Это приво-
дит ещё к одному интересному следствию.
Следствие 5. Для любого простого p существует алгоритм, распознающий для произвольной заданной
сд свойство иметь реализацию Брикелла над конечным полем характеристики p.
Замечание. Отметим ещё одно свойство системы из следствия 3. Оказывается, переменные d(U, p) мож-
но выразить через переменные d*(V, q), поскольку для любого U из G0 и p из U в G*
0 найдётся такое V, что в
системе имеется уравнение d(U, p)d*(V, p) = 1. Аналогично, переменные d*(V, q) выражаются через перемен-
ные d(U, q). Указанные возможности следуют из леммы 3.
Лемма 3. Для любой сд G, любого множества U из G0 и любого p из U найдётся такое множество V в G*
0,
что U∩V = {p}.
Доказательство. Обязательно найдётся максимальное по включению неавторизованное в G множество
W, такое, что U \{p} ⊆ W ⊆ P \{p}. Так как дополнение V = P \W принадлежит G*
0 и U∩V = {p}, лемма
доказана.
Нижние оценки порядка реализации
Предположим, что сд G является сд Брикелла над некоторым конечным полем K, содержащим q элемен-
тов. Представляется интересной задача нахождения наименьшего такого значения q для заданной сд G.
Также имеет смысл задача нахождения нижней оценки для q. При решении данных задач может оказаться
полезной следующая лемма. Далее будет показано, как этой леммой следует пользоваться.
Лемма 4. Пусть G – сд Брикелла над полем порядка q на множестве участников P = A ∪ {a1, ..., ar}, где
элементы a1, ..., ar все различные из P\A и для любого i из {1, ..., r} существует множество Ai в G0, такое, что
ai∈Ai и Ai ⊆ A ∪ {a1, ..., ai}. Тогда для любого элемента a0 из A число таких множеств B в G*
0, что пересече-
ние B∩(A\{a0}) пусто, не превосходит q.
Совершенные схемы разделения секрета 57
Доказательство. В системе уравнений из теоремы 4 в этом случае для всякого множества B из G*
0 будут
присутствовать уравнения:
d(A1, a0)d*(B, a0) + d(A1, a1)d*(B, a1) = 1, d(A2, a0)d*(B, a0) + d(A2, a1)d*(B, a1) + d(A2, a2)d*(B, a2) = 1, ...
Отсюда видно, что значение d*(B, a0) однозначно определяет все значения d*(B, a) для всевозможных a из P
и таким образом однозначно определяет само множество B. Следовательно, имеется не более q возможно-
стей для выбора B. Лемма доказана.
Пороговая сд
Рассмотрим пример использования леммы 4.
Структура доступа G на n-элементном множестве P называется (n, k)-пороговой, если её базис, множест-
во G0, состоит из всевозможных k-элементных подмножеств множества P. Хорошо известно, что для любых
целых k и n, таких, что 1 ≤ k ≤ n, (n, k)-пороговая сд является сд Брикелла над некоторым конечным полем.
Об этом можно прочитать, например, в [7, 10]. Несложно понять, что для заданных целого положительного
k и целого положительного q, являющегося степенью простого числа, существует наибольшее n, при кото-
ром существует сд Брикелла над q-элементным полем, реализующая (n, k)-пороговую сд. Для такого наи-
большего n положим m(k, q) = n + 1. Несложно понять, что m(k, q) – это наибольшее число векторов в век-
торном пространстве над q-элементным полем, из которых любые k линейно независимы и любые k + 1 ли-
нейно зависимы. В некоторых случаях значение m(k, q) найти несложно. Так, величина m(1, q) совпадает с
длиной кода Хэмминга над q-элементным полем и, следовательно, равняется q + 1. Определение точного
вида функции m(k, q) в общем случае является давней комбинаторной задачей, не решённой и по сей день
[7, 11]. Предполагается, что m(k, q) = q + 1 за исключением случая m(3, q) = (q – 1, q) = q + 2 при чётном q.
Следующая теорема даёт нижнюю оценку порядка реализации Брикелла для (n, k)-пороговой сд и одновре-
менно даёт верхнюю оценку m(k, q) ≤ q + k – 1 для величины m(k, q), лишь на 1 худшую, чем оценка теоре-
мы 11 из [11].
Теорема 5. Если над q-элементным полем существует реализация Брикелла (n, k)-пороговой сд и k ≥ 2, то
n ≤ q + k – 2.
Доказательство данной теоремы опирается на лемму 4. Пусть G – (n, k)-пороговая сд на n-элементном
множестве P. Тогда G0 состоит из всевозможных k-элементных подмножеств множества P и G*
0 состоит из
всевозможных (n – k + 1)-элементных подмножеств. Это позволяет в условиях леммы 4 выбрать (k–1)-
элементное множество A. Тогда, с одной стороны, число подмножеств B, о которых идёт речь в лемме, рав-
но n − k + 2. С другой стороны, это число по лемме 4 не превосходит q. Таким образом получаем неравенст-
во n − k + 2 ≤ q. Теорема доказана.
ЛИТЕРАТУРА
1. Яблонский С.В. О классах функций алгебры логики, допускающих простую схемную реализацию // УМН. 1957.
Т. XII. Вып. 6 (78). С. 189 – 196.
2. Алон Н., Спенсер Д.Ж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007. 320 с.
3. Ван дер Варден Б.Л. Алгебра. Определения, теоремы, формулы. 3-е изд., стер. – СПб.: Лань, 2004. 624 с.
4. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. М.: Наука, 1972. 240 с.
5. Дистель Р. Теория графов. Новосибирск: Изд-во Ин-та математики, 2002. 336 с.
6. Marti-Ferre J., Padro C. On secret sharing schemes, matroids and polymatroids // Cryptology ePrint Archive, Report
2006/077, http://eprint.iacr.org/2006/077.
7. Введение в криптографию / Под общ. ред. В.В. Ященко. 3-е изд., доп. М.: МЦНМО «ЧеРо», 2000. 288 с.
8. Marti-Ferre J., Padro C. Secret sharing schemes on sparse homogeneous access structures with rank three // The electronic
journal of combinatorics 11 (2004), Research papper 72, 16 p. (electronic).
9. Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраиче-
ской геометрии и коммутативной алгебры. М.: Мир, 2000. 687 с.
10. Агибалов Г.П. Избранные теоремы начального курса криптографии. Томск: Изд-во НТЛ, 2005. 116 с.
11. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. 744 с.
__