3.5. Еще раз о разделении секрета

Next: 3.6. Поиграем в ``кубики''. Up: 3. Криптографические протоколы Previous: 3.4. Протоколы типа ``подбрасывание Contents: Содержание

3.5. Еще раз о разделении секрета

В работе [16] со ссылкой на книгу ``Gent und seine schoenheiten'' (Thill-Verlag, Bruessel, 1990) описывается следующий исторический пример. В XIII-XIV веках в г. Генте была построена ратушная башня. В ``секрете'' (secreet), самом надежном помещении башни, хранились уставы и привилегии, имевшие важное значение. Помещение имело две двери, каждая с тремя замками, ключи от которых находились во владении различных цехов. Документы хранились в шкафу, который, в свою очередь, также запирался на три ключа. Один из этих ключей хранился у фогта, а два других - у главного шеффена.

Мы привели этот пример в разделе, посвященном протоколам разделения секрета, главным образом для того, чтобы показать, что хотя криптографические протоколы - сравнительно молодая отрасль криптографии, задачи, которые решаются с помощью протоколов, возникли очень давно и имеют свою историю.

Почему ``еще раз о разделении секрета''? В главе 5 разделение секрета рассматривается в основном как математическая, прежде всего комбинаторная, задача. Здесь же мы его обсуждаем как криптографический протокол. При этом предполагается, что читатель знаком с главой 5.

В протоколе разделения секрета имеются участников $P_1,\dots, P_n$ , которых мы будем называть процессорами, и один выделенный участник , называемый дилером (или, иногда, лидером). Протокол состоит из двух фаз.

На фазе разделения секрета дилер, знающий некоторый секрет , генерирует долей секрета $s_1, \dots, s_n$ и посылает процессору по защищенному каналу связи. На фазе восстановления секрета любое подмножество из не менее чем процессоров, где - параметр протокола, однозначно восстанавливает секрет, обмениваясь сообщениями по защищенным каналам связи. А любое подмножество из не более чем процессоров не может восстановить секрет (что означают слова ``не может восстановить'' будет пояснено ниже).

Как и в других типах криптографических протоколов, в протоколе разделения секрета участники, вообще говоря, не доверяют друг другу и каждый из них может оказаться противником. В том числе и дилер. Можно ли обеспечить какую-либо защиту честных участников даже и в этом случае? Безусловно, нечестный дилер может просто саботировать выполнение протокола. Но если дилер пытается обмануть более хитрым способом, то от этого, оказывается, можно защититься следующим образом. Фаза разделения секрета начинается с того, что дилер публикует секрет в ``зашифрованном'' виде (точнее было бы сказать - выполняет привязку к строке , по аналогии с привязкой к биту). С помощью этой информации каждый процессор может проверить, что значение , полученное им от дилера, действительно является долей секрета . Такой протокол называется протоколом проверяемого разделения секрета. В обычных схемах разделения секрета рассматривается пассивный противник, а именно, противником являются не более чем участников, которые, объединив свои доли, пытаются получить какую-либо информацию о значении секрета. На фазе восстановления секрета в протоколе проверяемого разделения секрета действует активный противник: нечестные участники могут преследовать цель сорвать восстановление значения честными участниками, посылая им вместо своих долей секрета любую другую информацию. От протокола требуется, чтобы честные участники, если их по крайней мере , всегда правильно восстанавливали значение .

Рассмотрим конструкцию протокола проверяемого разделения секрета из работы [17]. Конструкция основана на задаче дискретного логарифмирования.

В соответствии со схемой Шамира дилер выбирает случайный полином $Q(x)=a_0+a_1x+\dots +a_tx^t$ степени , где , вычисляет $r_i=g^{a_i}\nmod p$ ( $i=0,1,\dots ,t$ ) и публикует $r_0,\dots ,r_t$ . После этого для всякого $j=1,\dots ,n$ дилер вычисляет и посылает это значение процессору по защищенному каналу. Процессор , проверяя равенство

$\begin{displaymath} g^{s_j}=r_0\cdot (r_1)^j\cdot \ldots \cdot(r_t)^{j^t}\pmod p, \end{displaymath}$

убеждается, что

- доля секрета

. В самом деле,

$\begin{displaymath} r_0\cdot (r_1)^j\cdot \ldots \cdot(r_t)^{j^t}=g^{a_0}\cdot ... ...\cdot g^{a_tj^t}=g^{a_0+a_1j+\dots +a_tj^t}=g^{Q(j)}\pmod p. \end{displaymath}$

Конструкцию протокола для фазы восстановления секрета рассмотрим в наиболее простом случае, когда дилер честный. На этой фазе каждый процессор посылает каждому другому процессору свою долю . Всякий честный участник , получив некоторое значение от , проверяет это значение, как описано выше, и отбрасывает все доли , не прошедшие проверку. Поскольку честных участников не менее , получит по крайней мере правильных долей секрета. Используя алгоритм восстановления секрета из схемы Шамира, восстановит значение .

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

Одно из возможных приложений схем разделения секрета - организация хранения криптографических ключей. Свойство проверяемости представляется далеко не лишним для таких приложений. Но круг приложений схем проверяемого разделения секрета существенно шире.

Предположим, что с помощью описанной выше схемы разделены два секрета и и что оба эти секреты являются числами. Теперь представим себе ситуацию, что после этого потребовалась разделить секрет . Конечно, это может сделать дилер с помощью того же протокола. А могут ли процессоры выполнить то же самое без участия дилера?

Пусть $Q_1(x)=a_0+a_1x+\dots +a_tx^t$ и $Q_2(x)=b_0+b_1x+\cdots +b_tx^t$ - полиномы, которые использовались для разделения секретов и соответственно. Пусть $r_i^1=g^{a_i}\nmod p$ и $r_i^2=g^{b_i}\nmod p$ для $i=0,\dots ,t$ . Для любого $j=1,\dots ,n$ пусть и - доли секретов и , полученные процессором . Ясно, что - также полином степени и .

Поэтому каждый процессор может вычислить долю секрета просто по формуле . Эти доли проверяемы с помощью значений $r_i=r_i^1\cdot r_i^2\nmod p$ .

Рабин и Бен-Ор показали [18], что выполняя такого рода вычисления над долями секретов, процессоры могут вычислить любую функцию над конечным полем ``проверяемым образом''. Этот результат относится к области протоколов конфиденциального вычисления (secure multi party computation). Типичная задача здесь такая. Требуется вычислить значение функции на некотором наборе значений аргументов $y_1,\dots ,y_m$ . С помощью схемы проверяемого разделения секрета вычисляются доли $x_1,\dots ,x_n$ этих значений. В начале выполнения протокола доля известна процессору и только ему. Протокол должен обеспечивать вычисление значения $f(x_1,\dots ,x_n)=f(y_1,\dots,y_m)$ таким образом, чтобы для некоторого параметра :

1) в результате выполнения протокола любое подмножество из не более чем процессоров не получало никакой информации о значениях других процессоров (кроме той, которая следует из известных им долей и значения функции $f(x_1,\dots ,x_n))$ ;

2) при любых действиях нечестных участников остальные участники вычисляют правильное значение $f(x_1,\dots ,x_n)$ , если только количество нечестных участников не превосходит .

Протоколы конфиденциального вычисления, ввиду своей общности, представляют несомненный теоретический интерес. Кроме того, многие типы прикладных криптографических протоколов (например, протоколы голосования) по существу являются частными случаями протоколов конфиденциального вычисления.

При различных предположениях о процессорах и о сети связи доказан ряд теорем следующего типа: если не превосходит некоторого порогового значения (зависящего от и от предположений), то всякая вычислимая функция имеет протокол конфиденциального вычисления.