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

Вычисления при By-сбоях


Как и в случае FS-сбоев нам необходимо вычислить функцию f:Fn®F. Предположим, что процессоры имеют общую арифметическую схему для вычисленияf. Ниже описывается n-сторонний протокол для безопасного

t-вычисления f в асинхронной сети с произвольными (то есть, при By-сбоях) противниками, при условии n³4t+1.

Основная идея заключается в адаптации вышеописанного протокола для FS-сбоев к аналогичному протоколу, но для By-сбоев. Для этого используем вышеописанную схему АПРС, а затем, этап умножения адаптируется к аналогичной конструкции, но для By-сбоев.

Пусть c=a·b – мультипликативный вентиль и пусть A(·), B(·) – полиномы, ассоциированные с входными линиями, а именно доли каждого процессора Pi

этих линий - A(i) и B(i) соответственно и A(0)=a и B(0)=b. Как и в случае FS-сбоев процессоры совместно вычисляют свои доли случайного полинома C(·) степени t, где C(0)=A(0)·B(0), так, что доля каждого несбоящего процессора Pi

на выходной линии будет C(i).

Процедура умножения при By-сбоях следует из соответствующей процедуры, но для FS-сбоев. А именно, процессоры сначала генерируют случайный полином D(·) степени 2t со свободными коэффициентами D(0)=A(0) ·B(0). Тогда процессоры вычисляют свои доли усеченного полинома D(·) степени t

и этот усеченный полином есть выходной полином C(·).

Собственно сама процедура умножения начинается с описания двух модифицированных шагов: умножения и редукции степени.

Рандомизация. Отличие от случая для FS-сбоев состоит в том, как каждый процессор Pi

делит полином Hi(·) степени 2t с Hi(0)=0. Для этого используется следующий метод [BGW]. Каждый процессор Pi делит t равномерно выбранных значений, используя t вызовов субпротокола АРзПр. Пусть zi,j,k, - выход процессора Pk

при j-том вызове АРзПр, где Pi - дилер. После завершения всех t вызовов АРзПр, каждый процессор Pk локально вычисляет Hi(k)=

.

Для этого пусть Si,j(·) – полином степени t определенный j-тым вызовом АРзПр, инициированным Pi (а именно, Si,j(k)=zi,j,k для каждого несбоящего процессора Pk).



Полином Hi(·) теперь определен как Hi(x)=
. Каждый процессор Pk

локально вычисляет Hi(k)=
=
. Пусть si,j,l

- коэффициент xl в Si,j(x). Это можно показать как

Hi(x)=

=si,1,0x

+

si,1,1x2

+

...

+

si,1,t-1xt

+

si,1,txt+1

+

si,2,0x2

+

...

+

si,2,t-2xt

+

si,2,t-1xt+1

+

si,2,txt+2

+

...

si,t,0xt

+

si,t,1xt+1

+

...

+

si,t,tx2t

Свободный коэффициент Hi(·) равен 0 и, таким образом, Hi(0)=0. Каждый полином Si,j(·) имеет степень t и, таким образом, Hi(x) имеет степень 2t. Кроме того, можно заметить, что коэффициенты членов x,...,xt в Hi(x) равномерно распределены над F. Следовательно, коэффициенты всех ненулевых степеней усеченного полинома C(·) равномерно распределены над F.

Ясно, что сбоящие процессоры накапливают некоторую дополнительную информацию относительно t

долей Hi(·). Однако эта информация независима от A(0)·B(0), так как процессор Pi выбирает t2+t случайных коэффициентов, а сбоящие процессоры получает только t2 значений.

Редукция степени. Процессоры используют свои доли полинома D(·) для совместного и конфиденциального вычисления своих долей «усечения» полинома D(·) степени t. А именно t+1 коэффициентов выходного полинома C(·) являются коэффициентами D(·) с более низкой степенью.

В протоколе для FS-сбоев процессоры вычисляли свои доли C(·), вызывая протокол для «умножения вектора входов на  фиксированную матрицу».

В протоколе для By-сбоев процессоры используют субпротоколы АРзПр и АВсПр вместо простой схемы разделения секрета для FS-сбоев.


Однако проблема заключается в том, что согласованное множество  G может содержать сбоящие процессоры Pi, совместно использующие некоторое значение, отличное от ожидаемого значения D(i). В этом случае, процессоры не будут иметь требуемых выходов.

Далее мы описываем, как процессоры Pi могут удостовериться в том, что значение, связанное с каждым процессором Pi в согласованном множестве (а именно, свободный коэффициент полинома степени t, определенного долями несбоящих процессоров Pi) – действительно D(i).

Для процессоров Pi пусть si - значение, связанное с Pi; для множества A процессоров, пусть SA=f{(i,si)½PiÎA}. Cначала отметим, что достаточно договориться о множестве G из, по крайней мере, 3t+1 процессоров, такое, что SG

является (2t,0)-интерполируемым (а именно, все значения, общедоступные для процессоров из G «находятся на полиноме степени 2t»). Это так, потому, что множество G размером 3t + 1, содержит, по крайней мере, 2t+1 несбоящих процессоров. Таким образом, интерполируемый полином SG

связан (ограничен) с полиномом D(·).

Далее описывается протокол для соглашения по множеству A процессоров такому, что SA является (2t,0)-интерполируемым. Этот протокол, обозначаемый СОИМ - Соглашения об интерполируемом множестве, является «распределенным вариантом» схемы СКОП, описанной выше.

Протокол СОИМ состоит из t итераций. На итерации r (0£r£t), процессоры сначала используют протокол СОАМ

(см. выше) чтобы договориться о множестве Gr, состоящее из, по крайней мере, 3t+1+r процессоров, которые успешно объединяют свои входы. Затем, стороны выполняют вычисления, описываемые ниже, для проверки, является ли множество
 (2t,r)-интерполируемым. Если
 является (2t,r)-интерполируемым, тогда существует множество Gr¢ÍGr размером из, по крайней мере, 3t+1 процессоров такое, что
 является (2t,0)-интерполируемым. Тогда процессоры вычисляют и выдают Gr¢.


В противном случае (т.е., когда
 - не является (2t,r)-интерполируемым), процессоры переходят к следующей итерации. Подчеркиваем, что стороны не будут знать интерполируемый полином для каждого 
. Они будут только знать, что такой полином существует.

Остается только описать, как проверить по данному множеству G размера 3t+1+r является ли SG (2t,r)-интерполируемым, и как вычислить соответствующее множество G¢ (то есть, G¢ÍG, ½G¢½³3t+1 и SG¢

является (2t,0)-интерполируем). Как и в процедуре СКОП, мы используем обобщенные коды с исправлением ошибок Рида-Соломона. Однако, в процедуре СКОП «слово» SG, было (динамическим) входом для одного процессора и, таким образом, каждый процессор мог бы локально запускать процедуру, реализующую схему с исправлением ошибок. В данной установке, каждый процессор имеет только одну долю каждого элемента SG; стороны будут вызывать совместные вычисления, выполняющее специфическую процедуру, реализующую схему с исправлением ошибок и использовать это для проверки, является ли G - (2t,r)-интерполируемым и вычисления G¢.

Сначала опишем частичную процедуру с исправлением ошибок. Входы для этой процедуре - (d,r,W). Если ½W½³d+2r+1 и W является

(d,r)-интерполируем, тогда выход - интерполируемый полином W. (В противном случае, выводится соответствующее сообщение). Процедура состоит из трех шагов.

Процедура СОИМ

Вычисление синдрома.

Для входного слова W=(i1,s1)...(il,sl), пусть Vl´l – матрица Вандермонда (см., например, [Кн, стр.474]), определенная как Vj,k=(ik)j. Пусть
=s1...sl. Синдром W

есть

l-(d+1) наибольших правых элементов l-размерного вектора произведения
·V-1. Таким образом, на этом шаге вычисляется синдром W.

Вычисление вектора погрешности. Вектор погрешности – это l-размерный вектор
=e1...el, где ej

– «смещение sj от правильного значения».


А именно, предположим, что W

- (d,r)-интерполируем и пусть P(·) - (d,r)-интерполируемый полином W. Тогда ej=P(ij)- sj алгоритм для каждого элемента (ij,sj)ÎW. Вектор погрешности уникален, так как интерполируемый полином P(·) – уникален. (Отметим, что вектор погрешности может быть вычислен только на основании синдрома. Если входное слово W - не является (d,r)-интерполируемым, тогда вычисленный вектор погрешности может быть ошибочным).

Вычисление выходного полинома. Выбрать 2t+1 корректных элементов из W (а именно, элементы (ij,aj) такие, что ej=0) для использования их, чтобы интерполировать P(·). (Этот шаг не будет выполнен).

Важно отметить, что синдром может быть представлен как функция только от вектора погрешности и, таким образом, он не содержит никакой информации относительно (d,r)-интерполируемого полинома P(·). А именно, пусть
 (в отн. 
) - вектор коэффициентов полинома P(·) (в отн.  Q(·)) длины l. (Полином Q(·) - полином, удовлетворяющий Q(i)=a для каждой пары (i,a)ÎW). Тогда
=
·V-1=(
·V+
)·V-1=
+
·V-1.

Последние l-(d+1) элементов из
 является нулевыми. Так как

l-(d+1)<i£l, мы имеем Qi=[
·V]i. Следовательно, последние l-(d+1) элементов из
 (т.е. синдром) являются линейной комбинацией
 и, таким образом, процессоры могут совместно вычислять синдром. То есть для данного согласованного множества G, каждый элемент синдрома SG

вычисляется следующим образом. Каждый процессор вычисляет соответствующую линейную комбинацию долей и вызывает субпротокол АВсПр

с результатом этой линейной комбинации как входом. Как только все эти субпротоколы завершаться, каждый процессор будет иметь полный синдром SG.

Как только синдром вычислен, каждый процессор использует алгоритм Берлекампа-Месси, чтобы локально вычислить вектор погрешности. Если на итерации r
 является (2t,r)-интерполируем, тогда вычисленный вектор погрешности является «истинным» вектором погрешности множества
, однако, если
 не является (2t,r)-интерполируемым, тогда вычисленный вектор погрешности может быть некорректным.


Следовательно, процессоры должны выполнить следующие действия. (Каждый выполняет эти операции локально, а все несбоящие процессоры выполняют одни и те же действия). Если вычисленный вектор погрешности, обозначаемый
¢ содержит более чем r ненулевых элементов, то несомненно
 не является (2t,r)-интерполируемым и процессоры переходят к следующей итерации. Если
¢ содержит не более r ненулевых элементов, то процессоры все еще должны проверять, что
¢ - корректный вектор погрешности. Для этого пусть Gr¢ - множество процессоров Pi такое, что ei¢=0, тогда процессоры повторно вычисляют синдром, основанный только на Gr¢. Если повторно вычисленный синдром представляет собой одни нули, тогда
 является (2t,0)-интерполируем и процессоры выдают Gr¢ и заканчивают. Если повторно вычисленный синдром ненулевой, тогда процессоры заключают, что
 - не является (2t,r)-интерполируемым и переходят к следующей итерации.

Далее опишем непосредственно протокол СОИМ. Пусть zi,j - доля Pi' значения общего с Pj. Динамический вход каждого процессора Pi является следующим аккумулируемым множеством, обозначаемым как Zi: как только Pi успешно завершил субпротокол АРзПр для Pj, пара (j,zi,j) добавляется к Zi. Общий выход сторон – это множество G из, по крайней мере, 3t+1 процессоров такое, что каждый несбоящий процессор Pi завершает субпротокол АРзПр для каждой стороны из G (а именно, GÍ{Pj½(j,zi,j)ÎZi}) и SG – является (2t,0)-интерполируем.

Утверждение 3.1.

Предположим, что протокол СОИМ

инициализируется с динамическими входами Z1,...,Zn как описано выше. Тогда все несбоящие процессоры завершают протокол СОИМ

с общим множеством G из, по крайней мере, 3t+1 процессоров, такое, что SG является (2t,0)-интерполируемым.

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

Приведено в работе [Ca1].

 

Протокол СОИМ(Zi)

Код для процессора Pi на динамическом входе Zi.

Выполнить для 0£r£t.

1. Пусть Ui={Pj½(j,zi,j)ÎZi}.


Установить (t,r,n,Ui)СОБМ=G.

2. Как только G вычислено, вычислять синдром SG.

    2.1. Пусть V

- матрица индексов Вандермонда из G. А именно пусть G=k1...k½G½, тогда Vi,j=(kj)i.

2.2. Пусть
.

2.3. Для 2t+1<j£½G½ установить ([
·V-1]j,[n])АВсПр=sj.

2.4. Пусть
, где s - синдром SG.

3. Инициализировать алгоритм Берлекампа-Месси для
 и пусть
¢ - выход.

    3.1. Если
¢ имеет более чем r ненулевых элементов, продолжить следующую итерацию (в этом случае SG, не является (2t,r)-интерполируемым).

3.2. Если
¢ имеет не более чем r ненулевых элементов, проверить, что
¢ корректен.

3.2.1. Пусть G¢ - множество процессоров из G, чьи соответствующие записи в
¢ являются нулевыми. Повторить шаг 2 в отношении G¢.

3.2.2. Если синдром SG¢ является нулевым вектором, выдать G¢ и остановиться. В противном случае перейти к следующей итерации (SG не является (2t,r)-интерполируемым).

При объединении этапов рандомизации и редукции степени, мы получаем протокол для мультипликативного вентиля.

Протокол ByMUL

Код для процессора Pi, на входах ai и bi.

1. Рандомизация.

1.1.    Для 1£k£t выполнить АРзПрi,k по входу rk, где rkÎRF и Pi - дилер.

1.2.    Для 1£j£n и для 1£k£t участвуют в субпротоколах АРзПрj,k.

1.3.    Пусть hi,j,k – выход процессора Pi для субпротокола АРзПрj,k.

1.4.    Пусть Ui={Pj½АРзПрj,k завершен для всех 1£k£n}.

1.5.    Установить (n,t,Ui)СОАМ=G.

1.6.    Установить
 и di=ai·bi+hi.

2. Редукция степени.

2.1. Как только di вычислено, выполнить АРзПрi(di), где Pi - дилер. Для 1£j£n

участвовать в субпротоколе АРзПрj.



2.2. Пусть zi,j – доля (процессора Pi) общего с Pj секрета и пусть Zi¢={(j,zi,j)½АРзПрj

был завершен}. Установить (Zi)СОИМ=G¢.

2.3. Пусть
 - матрица, используемая на шаге умножения для FS-сбоев и пусть
, где j1...j½G¢½

- индексы процессоров из G¢. Для 1£j£n

установить ([
]j,{j})АРзПр=cj.

2.4. Как только ci вычислен, выдать ci.

Полная структура протокола для By-сбоев точно такая же, как для FS-сбоев. А именно, в таком протоколе, обозначаемом ByВыч, процессоры выполняют аналогичные инструкции протокола для FS-сбоев, за исключением того, что протоколы АГРз, MUL, и АГВс

заменены на протоколы АГПРС, ByMUL и АВсПр

соответственно.

Теорема 3.9.

Пусть f:Fn®F

для некоторой области F с ½F½>n

и пусть А - схема, вычисляющая f. Тогда протокол ByВыч по входу A асинхронно

(én/4ù-1)-безопасно вычисляет f в установке с ограниченно защищенными каналами и в присутствии адаптивных противников.

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

Приведено в работе [Сa2].


Содержание раздела