SPDZ и арифметический MPC над разделёнными секретами

Булевы MPC работают с битами (XOR/AND). Арифметические MPC работают с целыми числами или элементами поля, напрямую поддерживая сложение и умножение. Они лучше подходят для приложений машинного обучения и статистики.

Значение x ∈ Z_p распределяется как x = x_1 + x_2 + ... + x_n mod p. Сложение распределённых значений бесплатно: каждая сторона локально складывает свои доли. Обмен данными не требуется.

Чтобы перемножить доли [a] и [b], стороны заранее получают тройку Бивера ([a_t], [b_t], [c_t]), где c_t = a_t·b_t. Для умножения на этапе выполнения требуется один раунд обмена данными.

SPDZ (Damgård и др., 2012) = «Распределённые вычисления с нулевым разглашением на основе частично гомоморфного шифрования». На автономном этапе с помощью SHE создаются аутентифицированные тройки. Этап выполнения представляет собой быстрое вычисление с аддитивными долями.

Каждая доля сопровождается MAC: MAC(x_i) = α·x mod p, где α — глобальный секретный ключ. Это не позволяет злоумышленникам незаметно изменить свои доли.

На автономном этапе SPDZ использует частично гомоморфное шифрование (BGV/BFV). Стороны гомоморфно перемножают свои доли, чтобы создать аутентифицированные тройки Бивера. Этот этап требует больших вычислительных ресурсов, но его можно распараллелить.

Имея тройку ([a],[b],[c]) и входы [x],[y], раскройте d=x-a и e=y-b (значения замаскированы, поэтому информация не утекает). Затем [x·y] = [c] + d·[b] + e·[a] + d·e. Требуется один раунд обмена данными.

MASCOT заменяет автономный этап SHE расширением OT и быстрее создаёт тройки для малых полей. Это предпочтительный автономный этап для двухстороннего SPDZ.

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

SPDZ-2k (Cramer и др., 2018) расширяет протокол на Z_{2^k} для арифметики с фиксированной точкой, удобной для машинного обучения. Библиотека MP-SPDZ показывает производительность 1 млн умножений в секунду по LAN для 2 сторон.

Для чего нужны тройки умножения Бивера в арифметических MPC?

Арифметические MPC используют аддитивные доли над Z_p. Сложение бесплатно, а для умножения в одном раунде используются тройки Бивера. SPDZ добавляет MAC для защиты от злоумышленников. MASCOT использует OT для быстрого создания троек. MP-SPDZ делает эти методы практически применимыми.