【隐私计算笔谈】MPC系列专题（五）：Beaver三元组和BMR协议

Beaver三元组（ Beaver Triple ）主要用于安全多方计算协议中的乘法计算。它的应用范围为加法和乘法均为线性的秘密分享机制。 用[∗]表示秘密被分享之后的状态，如[𝑎]表示秘密𝑎已经通过秘密分享函数被分享给了参与者，如果有n个参与者，则[𝑎] = {𝑎1,𝑎2,…,𝑎𝑛}。假设秘密共享函数为𝑓(𝑥)，𝑥为待共享的秘密，参与者为𝑃1,𝑃2,…,𝑃𝑛，参与者𝑃𝑖拿到的𝑥的子秘密记为𝑥𝑖。

假设需要分享的秘密为𝑎、𝑏，参与者𝑃𝑖获得的𝑎、𝑏的子秘密为𝑎𝑖、𝑏𝑖。

加法秘密分享机制为线性的意思为：存在一组常数𝜆1, 𝜆2,…,𝜆𝑛，使得： 𝑎+𝑏 = 𝜆1∙ (𝑎1+𝑏1) + 𝜆2∙(𝑎2 + 𝑏2) + ⋯+ 𝜆n∙(𝑎n+𝑏n)

将其抽象简记为：[𝑎 + 𝑏] = [𝑎] + [𝑏]

乘法秘密分享机制为线性的意思为：存在一组常数𝜆1, 𝜆2,…,𝜆𝑛，使得： 𝑎∙𝑏 = 𝜆1∙𝑎1∙𝑏1+ 𝜆2∙𝑎2∙𝑏2+ ⋯+𝜆n∙𝑎n∙𝑏n

将其抽象简记为：[𝑎 ∙ 𝑏] = [𝑎] ∙ [𝑏]

Beaver Multiplication的主要流程为：

在协议开始之前预先产生一个随机三元组：[𝑎], [𝑏], [𝑐],其中𝑎和𝑏对所有参与者保密，𝑐满足𝑐=𝑎∙𝑏。假设秘密𝑥和𝑦已经被分享，现在需要计算 [𝑥𝑦] 。

所有参与者公开 [𝛼],[𝛼]=[𝑥]−[𝑎]

所有参与者公开 [𝛽],[𝛽] = [𝑦]−[𝑏]

所有参与者计算 [𝑧]=[𝑐]+𝛼∙[𝑏]+𝛽∙[𝑎]+𝛼∙𝛽

因为 [𝛼] 和 [𝛽] 已公开，因此所有参与者都可以通过秘密重构函数独立计算出𝛼和𝛽。又因为： [𝑧] = [𝑐] + 𝛼 ∙ [𝑏] + 𝛽 ∙ [𝑎] + 𝛼 ∙ 𝛽 = [𝑎] ∙ [𝑏] + ([𝑥] − [𝑎]) ∙ [𝑏] + ([𝑦] − [𝑏]) ∙ [𝑎] + ([𝑥] − [𝑎]) ∙ ([𝑦] − [𝑏]) = [𝑎] ∙ [𝑏] + [𝑥] ∙ [𝑏] − [𝑎] ∙ [𝑏] + [𝑦] ∙ [𝑎] − [𝑏] ∙ [𝑎] + [𝑥] ∙ [𝑦] + [𝑎] ∙ [𝑏] − [𝑏] · [𝑥] − [𝑎] ∙ [𝑦] = [𝑥] ∙ [𝑦] = [𝑥 ∙ 𝑦]

由于[𝑎],[𝑏],[𝑐]是预先产生和分配的三元组，因此在乘法计算时参与者只需要本地计算[𝛼]=[𝑥]−[𝑎]和[𝛽]=[𝑦]−[𝑏]，并对计算结果[𝛼]和[𝛽]进行公开。

而对于上次叙述的BGW协议，在计算乘法时，需要每一个参与者计算[&#