Доказательство безопасности схемы проверяемого разделения секрета
Теорема 3.1.
Схема ПРСК является (n/3-1)-устойчивой.
Доказательство. Пусть
g((w1,...,wn-1,s
и
h((s1,...,sn-1,wn),(
где si=f0(i), f0(x)=s+a1x+...+at+1xt+1 и r=a1
(то есть полином, созданный, с использованием случайного параметра r дилера Д).
При рассмотрении протокола РзПр
напомним, что ti – трафик процессора Pi. Ясно, что для всех процессоров Pi, i£n, функция входа всегда возвращает пустую строку Ii(ti)=e, так как процессоры не вносят никакие входы в процессе вычисления функции 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=e.
При рассмотрении протокола ВсПр, определим вход и выход функции 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
g((w1,...,wn-1,s
h((s1,...,sn-1,wn),(
реализуется
f(w1,...,wn-1,s)=((s,s,...,s,wn),(
Корректность. Для доказательства теоремы необходимо доказать следующие две леммы.
Лемма 3.1. Пусть функция g имеет вид
g((w1,...,wn-1,s
Тогда g корректно вычисляет доли секрета s1,...,sn-1.
Доказательство. Сначала мы должны доказать, что для всех несбоящих процессоров Pi, значение Ii(ti) равно корректному входу. Если дилер Д - честный, то mi=f(i), где f - многочлен степени t+1 со свободным членом s
(секретом). Таким образом, ID(tD)=s, если дилер честный. Второе условие корректности состоит в том, что с высокой вероятностью должно выполняться O(t)=g(I(t)). В нашем случае это означает, что с высокой вероятностью значения mi, находящиеся у несбоящих процессоров, должны предназначаться для единственного полинома степени t+1. Это справедливо с вероятностью ³
Лемма 3.2. Пусть функция h имеет вид
h((s1,...,sn-1),(
Тогда h корректно восстанавливает секрет s.
Доказательство. Понятно, что для всех несбоящих процессоров Ii(ti)=si – корректная доля входа. В этом случае необходимо проверить, что с высокой вероятностью O(t)=h(I,t), а это означает, что необходимо доказать, что
h((s1,...,sn-1),(
Это равенство не выполняется, если:
· любой сбоящий процессор Pl «преуспевает» в получении случайного «мусора» вместо значений pl(j) в раунде 2 (в этом случае, сообщения Mi не будут интерполировать полином);
· процессор Pi распределяет pl(j) в раунде 2 и использует полином со свободным членом, отличным от нуля (в этом случае, Mi
восстановит другой секрет).
Так как мы уже знаем, что Pl «преуспевает» в любом из двух описанных случаев с вероятностью
Конфиденциальность. Для доказательства теоремы необходимо доказать следующие две леммы.
Лемма 3.3. Пусть функция g имеет вид g((w1,...,wn-1,s
=((s1,...,sn-1,wn),(
Тогда g конфиденциально вычислима в отношение долей секрета s1,...,sn-1.
Доказательство. Доказательство условия конфиденциальности для функции g заключается в описании работы моделирующего устройства М, которое взаимодействует со сбоящими процессорами (в том числе с нечестным дилером) и создает «почти» такое же распределение вероятностей, которое возникает у сбоящих процессоров во время реального выполнения протокола РзПр.
Необходимо рассмотреть два случая.
Случай A:
Дилер нечестен до начала 1-ого раунда. Моделирующее устройство будет следовать только командам процессоров с единственным исключением, что оно будет «передавать» их в какое-либо время противнику в случае «сговора». Так как процессоры не сотрудничают по любому входу, то это сводит моделирование к работе схемы проверяемого разделения секрета с нечестным дилером. Так что моделирование будет неразличимо с точки зрения противника.
Случай B:
Дилер честен до начала 1-ого раунда. Моделирующее устройство в 1-м раунде будет создавать случайный «ложный» секрет s'
и распределять его процессорам в соответствии с командами протокола с полиномом f'. Если дилер честен в течение всего протокола, тогда он будет выполняться с точки зрения противника как обычный протокол проверяемого разделения секрета с честным дилером.
Если дилер нечестен после
1-ого раунда противник и моделирующее устройство получит из оракула истинный вход s дилера. В этом случае моделирующее устройство передает управление от дилера к противнику и меняет полином, используемый для разделения на новый полином f" такой, что f"(0)=s и f"(i)=f'(i) для всех процессоров Pi, которые были «подкуплены» противником. Изменения моделирующего устройства в соответствии со случайным полиномом fi, используемым для доказательств с нулевым разглашением (см, например, [Ка14,КУ4] и приложение) делает их совместимыми с любым широковещательным каналом. Моделирующее устройство может всегда сделать это, так как противник имеет не более t точек полинома степени t+1. Далее моделирующее устройство использует полином f"
для работы несбоящих процессоров, все еще находящихся под его управлением. Можно утверждать, что для противника эти вычисления не отличимы от реальных вычислений. Единственный момент, отличающийся от реальных вычислений, - это тот факт, что доли секрета, которые противник получает до того, как дилер становится нечестным, созданы с использованием другого полинома. Но благодаря свойствам полиномов – это не является проблемой для моделирующего устройства, в том случае, если дилер нечестен. -
Лемма 3.4. Пусть функция h имеет вид
h((s1,...,sn-1),(
Тогда h конфиденциально вычислима в отношение секрета s.
Доказательство. Работа моделирующего устройства M
сводится к следующему.
Описание работы моделирующего устройства M
1. В раунде 1, M
моделирует процессор Pi, выбирая случайный полином h'i степени t+1 и посылает h'i(j) к Pj. В этом месте моделирующему устройству позволено получить из оракула выход функции, так что M будет изучать истинный секрет s. Если такой процессор является «подкупленным» противником Прот в конце этого раунда (или в следующих раундах), то и M, и Прот узнают истинную долю sl и M должен изменить полином h'l в соответствии с тем, что h'l(0)=sl, но без изменения значения в точках, уже известных противнику.
Моделирующее устройство M
может всегда cделать это, потому что противник имеет не более t точек полинома степени t+1.
2-8. В течение раундов 2-8 моделирующее устройство полностью следует явно командам процессоров. Так как все что делают процессоры в этих раундах полностью случайно и нет влияния на их входы, M будет всегда способно создать неразличимые распределения.
10. Моделирующее устройство M выбирает полином g степени t+1 такой, что g(0)=s и затем для каждого процессора Pi, устройство M
распространяет g(i)+pi(i)+...+pn(i), где pj - полином, распределенный процессором Pj
в течение раундов 2-8 моделирования. Интерполяция Рида-Соломона этих значений даст как результат секрет s. Если процессор Pl является сбоящим в конце этого раунда, тогда и M, и Прот узнают из оракула истинную долю входа sl. Если sl¹g(l), тогда M только изменит значение pl в точке l так, чтобы сделать полную сумму соответствующей такой широковещательной передаче.
Моделирование неотличимо от реального выполнения с точки зрения противника. Фактически, в раундах 2-8 все сообщения случайны и не связаны с входом, так что моделирующее устройство может легко играть роль несбоящих процессоров. В раунде 1 противник просматривает не более t долей реального входа несбоящих процессоров. В соответствии со свойствами схемы разделения секрета Шамира, эти доли полностью случайны и, таким образом, могут моделироваться даже без знания реального входа (как и в случае с моделирующим устройством). В раунде 9 реальная доля распространена «скрытым образом» как случайный «мусор», а это позволит моделирующему устройству распространять сообщение несбоящих процессоров с необходимым распределением даже без знания реального входа. -
С доказательством лемм 3.1 – 3.4 доказательство теоремы 3.1 следует считать законченным. -
Здесь уместно сделать следующее замечание.Схемы (протоколы) конфиденциальных вычислений являются чрезвычайно сложным объектом исследований. Как видно из сказанного выше, даже описание и доказательство безопасности одного из базовых примитивов в протоколах конфиденциального вычисления функции, - схемы проверяемого разделения секрета являются чрезвычайно громоздкими и сложными.
