Протокол проверяемого разделения секрета

В обычных схемах разделения секрета рассматривается пассивный противник, а именно, противником являются не более чем (m -1) процессоров, которые, объединив свои доли, пытаются получить какую-либо информацию о значении секрета.

Если же на фазе восстановления секрета действует активный противник, возможны следующие ситуации:

Ø дилер пытается раздать процессорам неправильные тени,

Ø процессоры А _i преследуют цель сорвать восстановление секрета S, посылая честным участникам вместо долей секрета любую другую информацию.

Подобное дей­ствие приведет к тому, что секрет не будет правильно восстановлен. При этом невозмож­но определить, кто из участников коалиции виноват в этом. В худшем случае участники просто не обна­ружат, что восстановленный секрет не соответствует исходному разде­ленному секрету.

Для защиты в подобной ситуации используется протокол проверяе­мого разделения секрета или верифицируемая схема разделения секрета.

Возможное решение заключается в применении доказательства с нулевым раскрытием, позволяющего одному участнику доказать коррект­ность выполненных им вычислений и знание тени, полученной в результа­те разделения секрета, другому участнику схемы, не раскрывая при этом самой тени. Данный протокол позволяет решать следу­ющую практическую задачу: каждый из участников может убедиться в том, что полученная им тень, объединенная с тенями других участников, позволяет гаранти­рован­но восстановить разде­ленный секрет.

32.7. Протокол проверяемого разделения се­крета по схеме Шамира

Для примера рассмотрим схему Шамира и ситуацию, в которой коалиция из m участников пытается восстановить секрет S при условии, что один из участников — обманщик и предоста­вляет «ложную» тень (не ту, что была получена в результате разделения секрета).

Фаза разделения секрета начинается с того, что дилер публикует секрет S в «зашифро­ванном» виде (точнее было бы сказать — выполняет привязку к строке S, по аналогии с привязкой к биту).

Дилер выбирает случайный по­лином степени m-1

Q(x) = а₀ + а₁ х + … + a_m-1х^m-1, где а_о = S,

вычисля­ет r_i = g ^ai mod р (i = 1,..., n) и публикует r ₁,..., r _n.

С помощью этой информации каждый процессор A _j может прове­рить, что значение s_j, полученное им от дилера, действительно является долей секрета S. Для этого он должен проверить равенство

g^sj =r₀ (r₁)^j … (r_m-1)^jm-1   mod q.

В самом деле:

.

На фазе раздачи секрета дилер вычисляет

s _j = Q(j), j = 1,..., n

и посылает это значение (доли или тени секрета) процессору A _j по защищенному каналу.

Конструкцию протокола для фазы восстановления секрета рассмо­трим в наиболее простом случае, когда дилер честный. На этой фазе каж­дый процессор A _j посылает каждому другому процессору A _i свою долю s_j.

Всякий честный участник A _i, получив некоторое значение s _j от A _j, проверяет это значение, как описано выше, и отбрасывает все доли s_j, не прошедшие проверку. Поскольку честных участников не ме­нее m, A_i получит по крайней мере m правильных долей секрета.

Используя алгоритм восстановления секрета из схемы Шамира, вос­становим значение S. Доли секрета являются гиперплоскостями в пространстве многочленов над полем Z _q. Для восстановления секрета строится единственная точка пересечения m гиперплоскостей с помощью интерполяционного полинома Лагранжа:

, где .

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