Основной протокол

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

Протокол АВФ

Код для процессора Pi по локальному входу xi и данной схеме A.

1. Установить (t,xi)АГПРС=(C,{si,j½jÎC}). Для линии l в схеме пусть l(i) определяет долю процессора Pi, находящуюся на этой линии. Если l

– j-тая входная линия схемы, тогда установить l(i)=si,j, если jÎG и l(i)=0 в противном случае.

2. Для каждого вентиля g в схеме, процессор Pi ожидает, пока i-тые доли всех входных линий вентиля g будут вычислены. Тогда он делает следующее.

2.1. Если g – аддитивный вентиль с выходной линией l и входными линиями l1

и l2, тогда вычисляет l(i)=l1(i)+l2(i).

2.2. Если g – аддитивный вентиль l=l1·l2, тогда вычисляет l(i)=MUL(l1(i),l2(i)).

3. Пусть lout – выходная линия схемы. Как только значение l(i)out – вычислено, послать сообщение «Готово» всем другим процессорам.

4. Дождаться получения n-t сообщений «Готово» от других процессоров. Установить (t,n,l(i)out)Авс=y.

Подать на выход (C,y).

Теорема 3.8. Пусть

f:Fn®F для некоторого поля F

с |F|>n и пусть A – схема, вычисляющая функцию f. Тогда протокол АВФ асинхронно

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

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

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