Введение в криптографию
[an error occurred while processing this directive]

Еще раз о разделении секрета - часть 3


Пусть и  - полиномы, которые использовались для разделения секретов и соответственно. Пусть

и для . Для любого пусть и - доли секретов и , полученные процессором . Ясно, что

- также полином степени и .

Поэтому каждый процессор может вычислить долю секрета просто по формуле . Эти доли проверяемы с помощью значений .

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

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

;

2) при любых действиях нечестных участников остальные участники вычисляют правильное значение , если только количество нечестных участников не превосходит .

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

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

Next: 3.6. Поиграем в ``кубики''.

Up: 3. Криптографические протоколы

Previous: 3.4. Протоколы типа ``подбрасывание

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]