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

       

Вычисления на мультипликативном вентиле


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

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

Сначала каждый процессор локально вычисляет свою долю полинома E(·)=A(·)·B(·), устанавливая E(i)=A(i)·B(i). Ясно, что E(·) имеет требуемый свободный коэффициент. Однако, полином E(·) имеет степень 2t и, кроме того, полином не является равномерно распределенным. Процессоры используют свои доли полинома E(·), чтобы вычислить свои доли требуемого полинома C(·) безопасным способом. Вычисления осуществляются в два этапа: на первом этапе процессоры совместно генерируют случайный полином D(·) степени 2t такой, чтобы D(0)=E(0). А именно, каждый процессор Pi будет иметь D(i). Затем, стороны используют их доли D(·), чтобы совместно вычислить свои доли полиномаC(·). Эти шаги описаны ниже.

Рандомизация. Сначала покажем, как генерируется полином D(·). Сначала процессоры генерируют случайный полином H(·) степени 2t и с H(0)=0; а именно, каждая сторона Pi будет иметь H(i). Мы сначала описываем, как полином H(·) делится в синхронной модели вычислений [BGW].

Каждый процессор Pi выбирает случайный полином Hi(·) степени 2t с Hi(0)=0 и делит его среди процессоров; а именно, каждый процессор Pj

получает Hi(j). Полином H(·) – устанавливается в H(·)=

j(·); а именно каждый процессор Pi вычисляет H(i)=
j(i).

В асинхронной модели вычислений процессор не может ждать, пока получит свою долю от всех других процессоров. Вместо этого, стороны соглашаются, используя субпротокол СОАМ, о множестве C процессоров, которые успешно разделили полиномы Hi. Затем полином H(·) будет установлен в H(·)=

(·). Другими словами, процессоры запускают протокол АГПРС, получают на выходе (C,f{Hj(i)½jÎC}) и каждый процессор Pi вычисляет H(i)=
(i).


Полином D(·)теперь определен как D(·)=E(·)+H(·); а именно каждый процессор Pi вычисляет D(i)=E(i)+H(i). Ясно, что D(0)=A(0)·B(0) и все другие коэффициенты D(·) равномерно и независимо распределены над F.

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

Пусть
=D(1),...,D(n) и пусть
=C(1),...,C(n). В работе [BGW] отмечено, что существует фиксированная матрица M

размерностью n´n такая, что
=
. Отсюда следует, что требуемый выход каждого процессора Pi - линейная комбинация входов процессоров: C(i)=[
]i=
. Будем называть такую операцию «умножение входов на фиксированную матрицу». В этом случае, входы процессоров являются их долями полинома D(·).

В синхронной модели вычислений умножение входов на фиксированную матрицу может быть выполнено посредством безопасного вычисления соответствующих n фиксированных линейных комбинаций входов таких, что значение i-той линейной комбинации вскрываемо только процессором Pi. Линейные комбинации безопасно вычисляются следующим образом. Сначала каждый процессор разделяет свой вход; затем каждый процессор вычисляет линейную комбинацию своих долей и открывает эту линейную комбинацию специальному процессору; в заключение специальный процессор вычисляет значение выхода, интерполируя полином степени t из полученных комбинаций [Ca2].



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


Ниже приводится решение для асинхронной модели вычислений. Сначала мы описываем метод для умножения входов на фиксированную матрицу в асинхронной модели для случая, когда матрица и множество входов связаны специальным образом. Кроме того, мы отметим также, что матрица М

и множество возможных входов (на этапе редукции степени) тоже связаны специальным образом.

Определение 3.7.

Пусть A – матрица размерностью n´n и пусть SÍFn - множество входных векторов. Будем говорить, что S – t-умножаемо на A, если для каждого множества GÍ[n] с |G|³n-t существует (легко вычислимая) матрица AG размером |G|´n такая, что для каждого входа
ÎS мы имеем
G·AG=
A.

Пусть S – t-умножаемо на A. Тогда протокол, описанный ниже, «умножает входы из множества S

на матрицу». Пусть
ÎS. Процессоры сначала выполняют протокол АГПРС (с входным вектором
). Как только общее множество G

вычислено, каждый процессор локально вычисляет AG. Затем, процессоры запускают n протоколов восстановления секрета АВс, где в i-том протоколе АВс процессоры позволяют процессору Pi вычислить
G·AG, посылая ему соответствующую линейную комбинацию своих долей. Ниже описывается протокол для умножения входа на фиксированную матрицу.

Протокол МАТ (xi,A)

Процессор Pi на входе xi и матрице A работает следующим образом.

1. Устанавливает (t,xi)АГПРС=(G,{si,j½G}).

2. Нумерует G=g1,...,g|G| и пусть в этом случае
=
.

3. Вычисляет AG.

4. Для 1£k£n

устанавливает ([
·AG]k,t,{k})Авс=yk.

Подает на выход yi.

Далее будем говорить, что входной вектор
 есть – d-сгенерирован, если существует полином P(·) степени d, удовлетворяющий xi=P(i) для каждого i; множество возможных входов на шаге редукции степени – это множество 2t-сгенерированных векторов.

Для дальнейших рассуждений нам необходима матрица особого вида. Эта матрица, назовем ее M, описана в работе [BGW] и строится как



М=V-1TV, где V – матрица Вандермонда размерностью n´n (см, например, [Кн, стр.474]), определенная как Vi,j=ij, а T построена установкой всех элементов, кроме элементов первых t+1 столбцов, единичной матрицы в нули. (Пусть
,
 - вектора, определенные выше). Для того чтобы увидеть, что
·М=
 необходимо заметить, что
·V -1

– это вектор коэффициентов полинома D(·) и, таким образом,
V -1T – вектор коэффициентов полинома C(·) и
V-1TV=
).

Пусть GÍ[n] с |G|³n-t и пусть

G=g1,...,g|G|. Матрица MG строится следующим образом. Пусть матрица VG

размерностью |G|´|G| - это матрица V, спроектированная на индексы из матрицы G; а именно
=(gi)j.Далее строиться матрица
 размерностью |G|´n, присоединением n-|G| нулевых столбцов к (VG)-1. В итоге установить MG=
TV, где T – определена выше.

Так как n³3t+1 мы имеем |G|³2t+1. Можно проверить, что в этом случае
·
- тоже вектор коэффициентов полинома D(·), а именно
·
=
·V-1. Таким образом,
TV=
V-1TV=
M.                  <

Объединяя шаги рандомизации и редукции степени, мы получаем протокол для вычислений на мультипликативном вентиле. Этот протокол, обозначенный MUL, представлен ниже.

Субпротокол MUL(ai,bi)

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

1. Установить (t)АГПРС=(C¢,{hi,j½jÎC¢}).

2. Пусть di=ai·bi+
.

3. Пусть Mn´n – матрица, определенная выше как M.

4. Установить (di,M)MAT=ci.

Подать на выход ci.


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