协议描述
BGW 协议可以用于对域 $ \mathcal{F} $ 上包含加法、乘法、常数乘法门的算数电路求值。此协议强依赖于 Shamir 秘密共享方案，运用了 Shamir 秘密共享方案的同态特性对各个秘密份额进行适当的处理，可以实现在秘密值上实现安全计算。
给定 $ v \in \mathcal{F} $，我们令 $ [\nu] $ 标识各个参与方持有 $ v $ 的Shamir秘密份额。
BGW 协议的固定范式为：对于算数电路的每一条导线 $ \omega $，各个参与方都持有导线值 $ \nu_\omega $ 所对应的秘密份额 $ [\nu_\omega] $。
- 输入导线
对于属于参与方 $ P_i $ 的输入导线，$ P_i $ 知道明文导线值 $ \nu $。参与方 $ P_i $ 将秘密份额 $ [\nu_\omega] $ 分发给其他所有参与方。 - 加法门
考虑输入导线为 $ \alpha $ 和 $ \beta $、输出导线为 $ \gamma $ 的加法门。各个参与方共同持有输入导线秘密份额 $ [\nu_\alpha] $ 和 $ [\nu_\beta] $。参与方的目标是获得输入导线值 $ [\nu_\alpha] $ 和 $ [\nu_\beta] $ 求和的秘密份额 $ [\nu_\alpha + \nu_\beta] $。假设输入导线对应的多项式分别为 $ p_\alpha $ 和 $ p_\beta $。如果每个参与方 $ P_i $ 在本地对秘密份额求和，得到 $ p_\alpha(i) + p_\beta(i) $，则各个参与方将共同持有多项式 $ p_{\gamma}(x) \rightarrow p_{\alpha}(x) + p_{\beta}(x) $ 上的一个点。加法求值过程不需要进行交互，所有计算过程在本地完成。 - 乘法门
参与方的目标是获得输入导线值 $ [\nu_\alpha] $ 和 $ [\nu_\beta] $ 求和的秘密份额 $ [\nu_\alpha \cdot \nu_\beta] $。这使得各个参与方将共同持有多项式 $ q(x) = p_{\alpha}(x) \cdot p_{\beta}(x) $ 上的一个点。然而得到的多项式阶数最高为 $ 2t $，超过了秘密分享的阈值，这时候各方就需要一起完成多项式的降阶步骤。每个参与方 $ P_i $ 持有的秘密份额是 $ q(i) $，其中 $ q $ 是一个阶数最高可达 $ 2t $ 的多项式。参与方的目标是得到 $ q(0) $ 的有效秘密份额，且对应多项式的阶不超过阈值 $ t $。
降阶所用到的核心结论是可以用各个参与方的秘密份额的线性函数表示 $ q(0) $，也就是说 $ q(0) = \displaystyle\sum^{2t+1}_{i=1} \lambda_i[q(i)] $，其中 $ \lambda_i $ 项表示对应的拉格朗日系数。因此，降阶过程如下所示：- 每个参与方生成 $ q(i) $ 的 $ t $ 阶秘密共享，并将秘密份额 $ [q(i)] $ 发送给其他参与方。每个参与方选择的多项式最高为 $ t $ 阶，且常系数为 $ q(i) $
- 各参与方在本地计算 $ [q(0)] = \displaystyle\sum^{2t+1}_{i=1} \lambda_i[q(i)] $，该表达式仅涉及秘密份额的加法和常数乘法运算。
由于 $ [q(i)] $ 的秘密分享阈值为 $ t $，因此 $ [q(0)] $ 的秘密分享阈值也为 $ t $，满足了固定范式的要求。
需要注意的是，参与方对乘法门求值时需要进行交互（发送秘密份额 $ [q(i)] $），还需要注意的是 BGW 协议要求 $ 2t + 1 \leq n $，否则由于 $ q $ 的阶可能会达到 $ 2t $，$ n $ 个参与方没有足够的信息确定 $ q(0) $ 的值，因此当 $ 2t < n $ 时，BGW 协议在 $ t $ 个参与方被攻陷的条件下是安全的（安全性依赖于多数诚实假设）
- 输出导线
完成求值后参与方会持有输出导线 $ \alpha $ 的秘密份额 $ [\nu_{\alpha}] $，每个参与方将秘密份额广播给其他方使得所有参与方得到 $ \nu_{\alpha} $
参考文献
- 实用安全多方计算导论 /（美）戴维・埃文斯（David Evans），（美）弗拉基米尔・科列斯尼科夫（Vladimir Kolesnikov），（美）迈克・罗苏莱克（Mike Rosulek）著；刘巍然，丁晟超译。北京：机械工业出版社，2021.5