Тройки Бивера для безопасного умножения

Компания Stoffel Labs (предоставляющая MPC как сервис) написала наглядное руководство по beaver-triples на примере четырёх друзей, выбирающих ресторан. Такая подача важна, потому что протокол выглядит абстрактным ровно до тех пор, пока кто-нибудь не нарисует прямоугольник.

Условия задачи: четыре человека оценивают три ресторана по доступности a и качеству еды f, обе шкалы от 0 до 10. Группа хочет получить итоговые баллы для каждого ресторана S_j = Σ a_ij · f_ij так, чтобы никто не узнал чужие a_ij и f_ij. Для этого они используют secret-sharing с порогом восстановления 2 из 4.

Сложение разделяемых секретов ничего не стоит - разделение секрета линейно, поэтому [x] + [y] = [x+y] не требует взаимодействия участников и не увеличивает степень многочлена. С умножением всё сложнее: прямое вычисление [x][y] удваивает степень многочлена, а значит, порог восстановления возрастает с 2 до 3. Это нарушает базовое условие протокола о том, что двое участников могут раскрыть результат.

Решение - заранее вычисленная тройка ([a], [b], [c]), где c = ab, а a, b выступают случайными масками. Тождество Бивера переписывает площадь прямоугольника xy через (x-a) и (y-b):

xy = c + (x-a)·b + a·(y-b) + (x-a)·(y-b)
   = c + d·b + a·e + d·e          where d = x-a, e = y-b

Важно то, что d и e можно безопасно раскрыть, поскольку a и b - это равномерно распределённые одноразовые маски. Когда d и e становятся публичными, правая часть вычисляется исключительно из долей секрета - без роста степени. Плата за это - одна свежая тройка на каждое умножение плюс один раунд коммуникации для раскрытия d и e.

Две оговорки по корректности и безопасности, которые подчёркивает Stoffel:

• a и b обязаны быть равномерно случайными; если в них есть смещение, раскрытие d=x-a приведёт к утечке информации об x.
• Каждую тройку можно использовать ровно один раз. Повторное применение [a],[b] для двух умножений (x,y) и (x',y') раскроет d'-d = x'-x и e'-e = y'-y, то есть линейные зависимости между секретными входными значениями.

Тройки Бивера обычно генерируются на офлайн-фазе (иногда доверенной третьей стороной - TTP, иногда через протоколы на базе OT/HE) и расходуются в онлайн-фазе. Этот паттерн лежит в основе любого современного MPC-стека для модели с пассивным нарушителем (semi-honest) - SPDZ, MASCOT, TinyOT. Именно благодаря ему Stoffel может продавать "MPC как сервис", не переписывая криптографию под каждый конкретный сценарий.

Ссылки: secret-sharing, secure-multiparty-computation, beaver-triples, stoffel-mpc.