Тройки Бивера

Тройка Бивера - это кортеж ([a], [b], [c]) из разделённых случайных значений, где c = a · b, сгенерированный на офлайн-фазе до начала основных вычислений. Дон Бивер предложил их в 1991 году, чтобы решить давнюю проблему в secure-multiparty-computation на основе secret-sharing: при наивном умножении двух разделённых значений степень многочлена удваивается, что повышает порог восстановления секрета.

Суть трюка - тождество прямоугольника. Имея доли [x], [y] и свежую тройку ([a], [b], [c=ab]):

1. Вычислить [d] = [x] - [a] и [e] = [y] - [b] - локально, без сетевого взаимодействия.
2. Открыть d и e (один раунд broadcast'а). Это безопасно, так как a, b - равномерно случайные маски.
3. Вычислить [xy] = [c] + d·[b] + e·[a] + d·e - локально, без роста степени.

Два условия корректности:

• Тройка должна быть свежей (использоваться строго один раз). Повторное использование раскрывает линейные зависимости между секретными входами.
• a, b должны быть равномерно случайными. Смещение приводит к тому, что открытие d = x - a раскрывает информацию об x.

На практике офлайн-фаза генерации троек оказывается самой ресурсоёмкой. Распространённые подходы:

• На базе OT (TinyOT, MASCOT): генерация троек через oblivious transfer; константное число раундов, высокий расход полосы пропускания
• На базе HE (SPDZ): использование гомоморфного шифрования Paillier или BFV/BGV; меньше трафика, больше вычислений
• На базе TTP (фаза обучения/настройки или аппаратные анклавы): доверенный дилер генерирует тройки; самый дешёвый вариант, но требует предположения о доверии, от которого MPC как раз призван избавить

Тройки Бивера обобщаются: существуют матричные тройки (для линейной алгебры), булевы тройки AND (для вычислений в стиле garbled circuits) и квадратичные тройки ((a, a²) для операций деления).

Пример работы приведён в mpc-beaver-triples (сценарий со счётом в ресторане от Stoffel).