MENU

BMR 协议

• November 7, 2022 • Read: 1254 • 隐私计算

思想

BMR(Beaver-Micali-Rogaway)协议的执行轮数为常数,与电路 $ \mathcal{C} $ 的深度无关。

BMR 协议将混淆电路的思想引入到多参与方场景下(混淆电路协议的执行轮数为常数)。BMR 协议的基本思想是分布式执行乱码电路生成过程,任何参与方(包括所有参与方的真子集)都无法单独得到乱码电路的秘密信息(导线标签和导线值的对应关系)。具体方法是让每个参与方独立(并行)生成所有导线标签,并独立(并行)生成所有门的乱码表。由于所有门/导线的处理过程都是并行的,因此生成过程的通信复杂度与待计算电路 $ \mathcal{C} $ 的深度相互独立。无论 $ \mathcal{C} $ 多么复杂,只要确认好安全参数 $ \kappa $,那么生成电路 $ \mathcal{C}_{GEN} $ 的深度都是常数。虽然求值时的通信复杂度由 $ \mathcal{C}_{GEN} $ 来决定,但 BMR 协议的总通信轮数仍为常数。

可以将 $ \mathcal{C}_{GEN} $ 安全求值后生成的乱码电路交付给指定的参与方 $ P_1 $,$ P_1 $ 按照乱码电路求值过程对电路求值。而对于如何将激活输入标签交付给 $ P_1 $,目前已有多种方法,具体取决于使用哪种 MPC 协议执行乱码电路生成过程。最简单的交付方法是把交付过程也看作乱码电路生成过程中的一部分。

在分布式生成乱码表时的开销可能非常大,需要用 MPC 对用于加密乱码表条目的加密函数求值(PRF/哈希函数等)。为此提出了许多优化协议,这些协议将 PRF/哈希函数求值过程从 MPC 中剥离出来。各个参与方只需要在本地对 PRF/哈希函数求值,并将求值结果提供给 MPC 即可。此类协议的思想史让不同参与方生成导线标签的不同部分。各个参与方生成导线 $ \omega_a^\nu $ 的子标签 $ \omega_{a,j}^\nu $,再将其串联起来得到 $ \omega_a^\nu $。随后对于输入导线标签为 $ \omega_a^{\nu_a} $,$ \omega_b^{\nu_b} $,输出导线标签为 $ \omega_c^{\nu_c} $ 的门 $ G_i $,可以简单地将与其关联的乱码表条目设置为:$ e_{\nu_\a,\nu_b} = \omega_c^{\nu_c} \displaystyle\oplus_{j=1..n} (F(i,\omega_{a,j}^{\nu_a}) \oplus F(i,\omega_{b,j}^{\nu_b})) $,其中 $ F $ 是一个 PRF,其以电路门的序号为索引值,将 $ \kappa + 1 $ 比特的输入扩展为 $ n \cdot (\kappa + 1) $ 比特的输出。
乱码表各行生成几乎完全由各参与方在本地完成,每个参与方计算 $ F(i,\omega_{a,j}^{\nu_a}) \oplus F(i,\omega_{b,j}^{\nu_b}) $ 并将结果提交给 MPC 协议,MPC 协议只要简单地对所有值求异或即可生成乱码表的各行条目。
在乱码求值时需要重建出激活标签,由于 $ P_1 $ 知道自己所生成的子标签,所以可以根据这一信息判断哪个导线标签是激活标签,从而破坏协议的安全性。解决这个问题的方法是让每个参与方为每一条导线再增加一个翻转比特 $ f_{a,j} $。由 $ n $ 个翻转比特的异或值决定明文所对应的导线标签 $omega^{\nu_a} $。翻转比特也需要作为附加输入。这样即使从标签中识别出自己所贡献的子标签,求值方也无法得知一起相关的明文值是什么,因为任何参与方自己都无法得知真正的翻转比特是什么,也就无法完整地计算出非激活标签。

参考文献

  • 实用安全多方计算导论 /(美)戴维・埃文斯(David Evans),(美)弗拉基米尔・科列斯尼科夫(Vladimir Kolesnikov),(美)迈克・罗苏莱克(Mike Rosulek)著;刘巍然,丁晟超译。北京:机械工业出版社,2021.5
Last Modified: November 28, 2022