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

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

Теорема 2.3. Схема ПРСК является (n/31)устойчивой.

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

(то есть полином, созданный, с использованием случайного параметра r дилера Д).

При рассмотрении протокола РзПр напомним, что ti трафик процессора Pi. Ясно, что для всех процессоров Pi, in, функция входа всегда возвращает пустую строку Ii(ti)=ε, так как процессоры не вносят никакие входы в процессе вычисления функции g. Для дилера Д, Д=Pn+1, функция входа немного сложнее. Пусть mi сообщение, который дилер распространяет процессору Pi в 5м раунде, если Pi сообщил об ошибке в 4м раунде или сообщение, которое дилер послал процессору Pi в 1м раунде, если Pi не заявлял об ошибке. Тогда ID(tD)=f(0), где f=BW(m1,...,mn) полином степени t+1, следующий из интерполяции БерлекампаВелча. Функция выхода более простая: Oi(ti)=mi, где mD.

При рассмотрении протокола ВсПр, определим вход и выход функции g. Функция входа Ii для процессора Pi определена как следующая: пусть mi,j сообщение, посланное процессором Pi процессору Pj в 1м раунде; Ii(ti)=hi(0), где hi=BW(mi,1,...,mi,n) многочлен степени t+1, следующий из интерполяции БерлекампаВелча. Если такого полинома не существует, то Ii(ti)=0. Функция выхода следующая: пусть Mi сообщение, распространяемая процессором Pi в раунде 9; Oi(ti)=F(0)=s, где F=BW(M1,...,Mn) полином степени t+1, следующий из интерполяции БерлекампаВелча.

Далее для доказательства теоремы необходимо доказать выполнения условий полноты, корректности и конфиденциальности. Полнота. Если дилер Д честный, исходя из свойств схемы ПРСК, любой несбоящий процессор может восстановить секрет s с вероятностью 1, так как посредством определенных выше функций g и h

реализуется

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

Лемма 2.3. Пусть функция g имеет вид

Тогда g корректно вычисляет доли секрета s1,...,sn1.

Доказательство. Сначала мы должны доказать, что для всех несбоящих процессоров Pi, значение Ii(ti) равно корректному входу. Если дилер Д честный, то mi=f(i), где f многочлен степени t+1 со свободным членом s (секретом). Таким образом, ID(tD)=s если дилер честный. Второе условие корректности состоит в том, что с высокой вероятностью должно выполняться O(t)=g(I(t)). В нашем случае это означает, что с высокой вероятностью значения mi, находящиеся у несбоящих процессоров, должны предназначаться для единственного полинома степени t+1. Это справедливо с вероятностью, где не менее битов выбраны действительно случайно несбоящими процессорами в раундах 2 и 6. Каждый бит представляет запрос, на который нечестный дилер, распределивший "плохие" доли, должен будет ответить правильно в следующем раунде только с вероятностью 1/2 (то есть, если он предскажет правильно значение бита). Следовательно, это и есть граница для вероятности ошибки

Лемма 2.4. Пусть функция h имеет вид

Тогда h корректно восстанавливает секрет s.

Доказательство. Понятно, что для всех несбоящих процессоров Ii(ti)=si корректная доля входа. В этом случае необходимо проверить, что с высокой вероятностью O(t)=h(I,t), а это означает, что необходимо доказать, что

Это равенство не выполняется, если:

  • любой сбоящий процессор Pl "преуспевает" в получении случайного "мусора" вместо значений pl(j) в раунде 2 (в этом случае, сообщения Mi не будут интерполировать полином);
  • процессор Pi распределяет pl(j) в раунде 2 и использует полином со свободным членом, отличным от нуля (в этом случае, Mi восстановит другой секрет).

Так как мы уже знаем, что Pl "преуспевает" в любом из двух описанных случаев с вероятностью, то, следовательно, имеется не более, чем n/3 сбоящих процессоров и вероятность того, что протокол вычисляет неправильный выход не более, чем n/3, что для достаточного большого K, является экспоненциально малым.

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

Лемма 2.5. Пусть функция g имеет вид

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

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

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

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

Случай B: Дилер честен до начала 1ого раунда. Моделирующее устройство в 1м раунде будет создавать случайный "ложный" секрет s' и распределять его процессорам в соответствии с командами протокола с полиномом f'. Если дилер честен в течение всего протокола, тогда он будет выполняться с точки зрения противника как обычный протокол проверяемого разделения секрета с честным дилером. Если дилер нечестен после первого раунда противник и моделирующее устройство получит из оракула истинный вход s дилера. В этом случае моделирующее устройство передает управление от дилера к противнику и меняет полином, используемый для разделения на новый многочлен f" такой, что f"(0)=s и f"(i)=f'(i) для всех процессоров Pi, которые были "подкуплены" противником. Изменения моделирующего устройства в соответствии со случайным полиномом fi, используемым для доказательств с нулевым разглашением (см, например, [6,27,29]) делает их совместимыми с любым широковещательным каналом. Моделирующее устройство может всегда сделать это, так как противник имеет не более t точек полинома степени t+1. Далее моделирующее устройство использует полином f" для работы несбоящих процессоров, все еще находящихся под его управлением. Можно утверждать, что для противника эти вычисления не отличимы от реальных вычислений. Единственный момент, отличающийся от реальных вычислений, это тот факт, что доли секрета, которые противник получает до того, как дилер становится нечестным, созданы с использованием другого полинома. Но благодаря свойствам полиномов это не является проблемой для моделирующего устройства, в том случае, если дилер нечестен.

Лемма 2.6. Пусть функция h имеет вид

Тогда h конфиденциально вычислима в отношение секрета s.

Доказательство. Работа моделирующего устройства M сводится к следующему.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок