Вычисления при FS-сбоях
В данном разделе показывается, как надежно при наличии FS-сбоях
t-вычислить любую функцию, вход которой разделен между n
процессорами, когда n³3t+1.
Пусть F – конечное поле, известное всем процессорам и |F|>n. Пусть также f:Fn®F - вычислимая функция. Предположим, что процессоры имеют арифметическую схему, вычисляющую функциюf. Схема состоит из вентилей сложения и умножения степени 2. Добавление константы рассматривается как частный случай сложения. Все вычисления в выполняются в поле F.
Общее описание протокола выглядит следующим образом [BCG]. Пусть xi - вход процессора Pi. На первом шаге каждый процессор разделяет вход среди других процессоров, используя, например, схему разделения секрета Шамира (см. выше). А именно, для каждого процессора Pi, который успешно разделил свой вход, случайным образом генерируется полином pi(·) степени t, сгенерирован такой, что каждый процессор Pj имеет pi(j) и pi(0) - значение входа процессор Pi. Будем говорить, что pi(j) - доля pi(0) процессора Pi. Затем, стороны договариваются, используя протокол СОАМ,
о множестве С процессоров, которые успешно разделили свои входы. Как только C вычислено, процессоры начинают вычислять fC(
зафиксировано.
Для каждого вентиля процессоры используют свои доли входных линий для совместного и безопасного «генерирования» случайного полинома p(·) степени t, такого, что каждый процессор Pi вычисляет p(i) и p(0) - является выходным значением этого вентиля. А именно, p(i) - доля процессора Pi на выходной линии этого вентиля. Как только процессоры вычислили свои доли на выходных линиях всей схемы, процессоры восстанавливают свои доли на выходной линии и интерполируют выходное значение.
