Схема (n,t)-звезды

Пусть OKi-граф – это неориентированный граф с вершинами [n], где ребро (j,k) существует тогда и только тогда, когда процессор Pi

завершил распространение двух сообщений (OK,j,k), инициированное Pj и (OK,k,j), инициированное Pk.

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

Пусть G - граф с вершинами [n]. Тогда пара множеств (C,D) такая, что CÍDÍ[n] является (n,t)-звездой в G, если выполняются следующие условия:

· ½C½³n-2t и ½D½³n-t;

· для каждого jÎC и для каждого kÎD в G существует ребро (j,k).

Процессор Pi получает доступ к разделенному секрету, когда находит звезду по OKi-графу. Лемма 3.5 (см. далее) реализует, что если n³4t+1, доли несбоящих процессоров в звезде OKi- графа, определяют единственным образом полином степени t от двух переменных. Лемма 3.6. говорит о том, что полиномы, определенные звездами для каждой из двух сторон равны. Таким образом, только несбоящие процессоры могут найти звезду, определяющую уникальный секрет.

В принципе, можно было бы допустить процессор, ждущий клику размера n-t взамен звезды. Если дилер честен, то OKi

- граф будет иметь такую клику. Однако задача нахождения клики максимального размера является NP-полной задачей. Поэтому стороны будут пытаться найти (n,t)-звезду.

Кроме того, необходимо удостовериться, что если несбоящий процессор находит звезду по OK-графу, то все несбоящие процессоры найдут звезду, даже если дилер нечестен и OK-граф не содержит клики. После получения сообщения (OK,·,·) процессор, который не нашел звезду проверяет какая из предложенных звезд является звездой для OK-графа. Отметим, что ребро в OK-графе для несбоящего процессора будет, в конечном счете, ребром в OK-графе для каждого несбоящего процессора (так как все сообщения (OK,·,·) распространяются посредством Br-субпротокола. Таким образом, звезда в OK-графе некоторого несбоящего процессора будет в конечном счете звездой в OK-графе любого другого несбоящего процессора.

Далее описывается процедура нахождения (n,t)-звезды в графе с n вершинами (см. определение 3.3), где граф содержит клику размера n-t. А именно, нижеописываемая процедура ЗВЗ, в качестве выхода выдает либо звезду в графе, либо выдает сообщение «звезда не найдена». Как только граф содержит клику размера n-t, процедура выдает звезду в графе. Аналогичная процедура описана в [ГДж].

Алгоритм работает следующим образом. Сначала находится максимальное паросочетание в комплиментарном графе и выдается множество несравнимых вершин. (Паросочетание в графе – это произвольное подмножество попарно несмежных ребер. Паросочетание является максимальным, если оно не содержится в паросочетании с большим числом ребер [Ле]. Комплиментарный граф – это граф, в котором ребро существует тогда и только тогда, когда оно не существует в оригинальном графе).

Выход алгоритма является независимым множеством в комплиментарном графе и, таким образом, формируется клика в оригинальном графе. Кроме того, если граф содержит клику размера n-k, тогда максимальное паросочетание в комплиментарном графе включает не более k ребер и 2k вершин. Далее описание алгоритма ведется в терминах комплиментарного графа. Если входной граф имеет независимое множество мощностью n-t, находится множества CÍD

вершин, такие, что ½C½³n-2t ½D½³n-t и не существует ребер между вершинами из C и вершинами из CÈD. Эта пара множеств будет называться

-звездой. Далее находится максимальное паросочетание в графе (см., например, [Ал, стр.18]).

На основе этого паросочетания вычисляются множества C и D вершин, и проверяется, формирует ли пара (C,D)

-звезду в графе. Если входной граф содержит независимое множество мощностью n-t, тогда полученные множества C и D формируют

-звезду в входном графе.

Далее показывается, как вычисляются множества C и D. Вершина называется трехглавой, если она не входит в паросочетание и две ее соседние вершины являются парой паросочетаний (а именно, ребро между этими двумя соседними вершинами являются паросочетанием).

Пусть C - множество вершин, которые не являются трехглавыми и B - множество вершин, которые имеют соседние вершины из C

и пусть D=[n]-B.

Алгоритм ЗВЗ

Вход:

неориентированный граф G с вершинами [n] и параметром t.

Выход:

-звезда в графе G, или сообщение «звезда не найдена».

1. Найти максимальное паросочетание M

в G. Пусть N - множество согласованных вершин (а именно, концевые точки ребер в M) и пусть

=[n]-N.

2. Проверить, что паросочетание M

имеет свойство L:

2.1. Пусть Т

– множество трехглавых вершин, а именно T={iÎ

½$ j,k такие, что (i,j),(i,k)ÎG}. Пусть

C=

-T.

2.2. Пусть B – множество вершин, имеющих соседние вершины в C, а именно B:={jÎN½$ iÎC такие, что (i,j)ÎG}. Пусть D:=[n]-B.

2.3. Если ½C½³n-2t и ½D½³n-t выдать (C,D), в противном случае выдать «звезда не найдена».

Предложение 3.3.

Предположим, что процедура ЗВЗ

выдает (C,D) на входном графе G. Тогда, (C,D) формирует

-звезду в G.

Доказательство.

Ясно, если алгоритм ЗВЗ выдает (C,D), тогда затем ½C½³n-2t ½D½³n-t и CÍD. Мы показываем, что для каждого iÎC и для каждого jÎD вершины i и j не являются соседними в G.

Предположим, что iÎC и jÎD и что (i,j) – ребро в G. Так как jÎD, мы имеем jÏB. По определению множества B, мы имеем jÏN (если iÎC и jÎN, тогда jÎB). Кроме того, iÎCÍ

. Таким образом, и i, и j не входят в паросочетание. Следовательно, ребро (i,j) может быть добавлено к паросочетанию для создания наибольшего паросочетания, и, следовательно, паросочетание не является максимальным. <

Предложение 3.4. Пусть G

- граф с n вершинами, содержащий независимое множество мощностью n-t.

Тогда процедура ЗВЗ выдает

-звезду в G.

Доказательство.

Сначала покажем, что если входной граф G

содержит независимое множество мощности n-t, тогда множества C и D, определенные на шагах 2.а и 2.b. алгоритма ЗВЗ являются достаточно большими. Следовательно, алгоритм выдает (C,D). В предложении 3.3 утверждается, что (C,D) формирует звезду в G. Далее покажем, что ½C½³n-2t. Пусть IÍ[n] – независимое множество мощности n-t в G и пусть

=[n]-I. Далее необходимо конкретизировать значения N, T и C в алгоритме ЗВЗ.

Пусть

F=I-C. Далее покажем, что ½F½£½

½. В то же время ½

½£t. Следовательно, ½C½³½I½-½F½³n-2t.

Так как ½F½£½

½, покажем взаимно однозначное соответствие f:F®

. Пусть iÎF и так как iÏC, мы имеет либо iÎN, либо iÎT.

Случай 1: iÎN. Тогда, пусть f(i) - вершина, сочетаемая с i в множестве М. Ясно, что f(i)Î

, в противном случае мы имели бы ребро (i,f(i)), где и i и f(i) принадлежит независимому множеству.

Случай 2: iÎT. По определению множества T, вершина i имеет две соседние вершины j и k

такие, что (j,k)ÎM. Произвольно множество f(i)=j. Понятно, что и j, и k принадлежат

.

Покажем, что f - взаимно однозначная функция. Рассматривая две различные вершины l,mÎF, мы различаем три случая.

Случай 1: l,mÎN. В этом случае, f(l)¹f(m), так как М - паросочетание.

Случай 2: lÎN и mÎT. Так как mÎT, то существует ребро между m и вершиной, сочетаемой с f(m). Так как lÎN вершина, сочетаемая с f(l) – это вершина l. Далее, предположим, что f(l)=f(m). Таким образом, (l,m) – ребро в G. Однако и l, и m принадлежат множеству I.

Что противоречит условию.

Случай 3: l,mÎT. Предположим, что f(l)=f(m). Пусть a - вершина, сочетаемая с f(m) из М. Тогда и l, и m – соседние вершины для f(m) и a. Однако, в этом случае паросочетание М

- не является максимальным, например, M-{(f(m),a)}È{(f(m),l),(a,m)} – является наибольшим паросочетанием.

В заключение покажем, что D³n-t. Напомним, что D=[n]-B. Далее покажем, что ½B½£½M½. Так как G содержит независимое множество мощности n-t, мы имеем ½M½£t. Таким образом, ½D½=n-½B½³n-½M½³n-t.

Для того, чтобы понять, что ½B½£½M½, мы покажем, что не более одной концевой точки каждого ребра (a,b)ÎM находится в B. От обратного предположим, что и a, и b имеют соседние вершины в C и пусть c,dÎC – соседние вершины a и b, соответственно. Конечно, c¹d (в противном случае, вершина c была бы трехглавой, и мы имели бы cÏC). Однако в этом случае паросочетание M не является максимальным. Например,

M-{(a,b)}È{(a,c),(b,d)} является наибольшим паросочетанием. <

Содержание раздела