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



         

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


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

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

Определение 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] и строится как



Содержание  Назад  Вперед