Теория и практика защиты программ


Доказательство безопасности схемы проверяемого разделения секрета - часть 3


·     процессор Pi распределяет pl(j) в раунде 2 и использует полином со свободным членом, отличным от нуля (в этом случае, Mi

восстановит другой секрет).

Так как мы уже знаем, что Pl «преуспевает» в любом из двух описанных случаев с вероятностью

, то, следовательно, имеется не более, чем n/3 сбоящих процессоров и вероятность того, что протокол вычисляет неправильный выход не более, чем n/3(
), что для достаточного большого K, является экспоненциально малым.

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

Лемма 3.3. Пусть функция g имеет вид g((w1,...,wn-1,s

r),(
,...,
))=

=((s1,...,sn-1,wn),(

,...,
)).

Тогда g конфиденциально вычислима в отношение долей секрета s1,...,sn-1.

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

Необходимо рассмотреть два случая.

Случай A:

Дилер нечестен до начала 1-ого раунда. Моделирующее устройство будет следовать только командам процессоров с единственным исключением, что оно будет «передавать» их в какое-либо время противнику в случае «сговора». Так как процессоры не сотрудничают по любому входу, то это сводит моделирование к работе схемы проверяемого разделения секрета с нечестным дилером. Так что моделирование будет неразличимо с точки зрения противника.

Случай B:

Дилер честен до начала 1-ого раунда. Моделирующее устройство в 1-м раунде будет создавать случайный «ложный» секрет s'

и распределять его процессорам в соответствии с командами протокола с полиномом f'. Если дилер честен в течение всего протокола, тогда он будет выполняться с точки зрения противника как обычный протокол проверяемого разделения секрета с честным дилером.


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