Skip to content

算法Algorithm

Beaver三元组乘法

Beaver triple multiplication · Multiplication triples

借助一次性随机乘法三元组,只打开两个掩码差值并用局部线性修正输出积共享,给出含预处理份额及全部广播的单次完美模拟。

形式陈述 ​

预先算一个随机乘积 ​

多方计算在线性共享上做加法很自然;直接把本地份额相乘却会改变共享结构。Beaver方法先准备随机a、b及c=ab的共享,在线只打开与随机值的差,再用线性操作得到真实乘积。[1,§2;2,§3.4]

本页固定素域F_q、次数上界t、n≥2t+1个互异非零坐标βᵢ。用Shamir表示,参与方Pᵢ持有xᵢ=F(βᵢ)、yᵢ=G(βᵢ),其中F/G次数至多t,秘密为x=F(0)、y=G(0)。这些输入多项式及辅助信息z在预处理随机币生成前固定;z可与输入相关,但与新预处理随机币独立。

理想预处理独立均匀抽取A、B的全部t+1个系数;令a=A(0)、b=B(0)。再独立均匀抽取C的t个非恒定系数,并固定C(0)=ab。Pᵢ只收到(aᵢ,bᵢ,cᵢ)=(A(βᵢ),B(βᵢ),C(βᵢ))。不同门使用独立新三元组,生成方不与观察者共享隐藏状态。三元组正确性、均匀性和独立性都是输入合同,在线公式不负责制造这些条件。

安全结论针对单次执行、静态被动腐化集合I、|I|≤t;所有方按协议执行,信道认证可靠,消息身份与次序固定,不含在线选输入、丢包、中止攻击或自适应腐化。允许泄漏由理想功能规定:收集合法的输入共享,计算xy,均匀抽取次数至多t且零点为xy的Z,并仅把Z(βᵢ)交给Pᵢ。输出是积的共享,并不公开xy。

在线只有两个打开 ​

各方形成dᵢ=xᵢ−aᵢ、eᵢ=yᵢ−bᵢ,并在同一轮广播这两个域元素。大家用插值得到d=x−a、e=y−b。随后各方局部计算

zi=ci+dbi+eai+de.

这些份额来自多项式Z(T)=C(T)+dB(T)+eA(T)+de,次数仍至多t,且

Z(0)=ab+(x−a)b+(y−b)a+(x−a)(y−b)=xy.

Shamir中,公开常数de对应常数多项式,所以每份都加de。若换成各份相加重构的加法共享,公开常数通常只加到一个指定份额;把两种表示的规则混用会算错。

直觉

公开偏移,保留随机基点 ​

可以把x看成a+d,y看成b+e。随机基点a、b保持共享状态,偏移d、e公开。展开乘积后,唯一需要两个秘密相乘的ab已经在预处理完成;剩余db、ea都只把公开数乘到秘密共享上。

但不只d和e可见。打开时每个人实际广播dᵢ、eᵢ,足够多的广播会确定完整差值多项式D=F−A、E=G−B。完整安全证明必须把这些向量与被腐化方原先拿到的三元组份额联合处理。

一次性三元组与局部线性乘法
例子与边界

三个坐标算4乘7 ​

在F₁₁上取坐标1、2、3及t=1。输入与预处理多项式为

F(T)=4+3T,G(T)=7+2T,A(T)=3+4T,B(T)=5+6T,C(T)=4+7T.

C(0)=4=3·5 mod11,满足相关性。完整表仅供离线复算;真实参与者只持自己的列。

量 坐标1 坐标2 坐标3
xᵢ 7 10 2
yᵢ 9 0 2
aᵢ 7 0 4
bᵢ 0 6 1
cᵢ 0 7 3
广播dᵢ 0 10 9
广播eᵢ 9 5 1
输出zᵢ 5 4 3

插值给D(T)=1+10T、E(T)=2+7T,故d=1、e=2。第二方算z₂=7+1·6+2·0+1·2=15≡4;整体得到Z(T)=6+10T,任意两份恢复6=4·7 mod11。

如果直接计算xᵢyᵢ,得到(8,0,4)。它们位于FG=6+7T+6T²上,次数已升到2。误把前两份当直线,零点为2·8−0=5,错于真实乘积6。三份虽然能插值这一个二次多项式,却已经改变门限和表示,继续连乘还会升次数。

一次性是信息条件,不只是编号习惯 ​

若同一a用于两次输入x/x′,公开差满足d′−d=x′−x。主例把F改成8+T,却重复同一A,第二次d′=5,观察者立刻得到5−1=4,也就是两个秘密之差。甚至完整广播还给出了两次输入多项式之差。

附件的三元组池在发出任何差值前,将该编号标为已用。打开后即使演示中止,该编号也不能重试。给同一组三元组复制一个新编号仍会泄漏;池只能拦截自身注册表内的编号复用,不能证明输入随机材料真的独立,也没有处理持久存储回滚或跨设备复制。

若错误地令a=b,即使只用一次,d−e=x−y也公开。因此不能只说“两个数各自均匀”:必须要求它们联合独立,并与输入及腐化者的额外旁信息满足所述预处理合同。

合法份额不保证合法三元组 ​

把C(0)从4改成5、其余保持,在线结果变成xy+1=7。这个错误的C仍是一条合法的一次多项式,完全可以被可验证秘密共享诚实分发并通过每份局部检查。逐份一致性没有证明C(0)=A(0)B(0)。

恶意安全实现还须检验预处理相关性并可靠认证打开消息;本页的被动定理没有这些对手动作。附件故意注入错误C,实际输出偏1,用来验证这项边界,而不是让在线算法假装能够识别所有错误预处理。

推论与应用

一个完整的终点模拟器 ​

对固定腐化集合I,视图包含身份、自己的输入份额F_I/G_I、收到的A_I/B_I/C_I、所有带身份的广播向量D⃗/E⃗、自己的输出Z_I,以及固定消息时序。在线不再使用本地随机币;预处理方的隐藏随机带不交给腐化者。

模拟器只拿到I、F_I/G_I和理想功能给出的Z_I,再做两次独立均匀抽样:选次数至多t的完整多项式D、E,每个各有t+1个均匀系数。按公开坐标计算广播向量,令d=D(0)、e=E(0),并对i∈I置

ai=xi−D(βi),bi=yi−E(βi),ci=zi−dbi−eai−de.

按真实字段次序交出全部记录。它不读取诚实方输入,也不单独假造互不相关的预处理份额:第三行专门保证这些份额与公开差值及输出的联合关系正确。

为什么连全部输出一起也同分布 ​

固定合法F/G。在真实世界,A/B的全部系数独立均匀,平移D=F−A、E=G−B使D/E仍是独立均匀的次数至多t多项式。条件于A/B,C的非恒定系数独立均匀;从C到Z只给这些系数加上已固定的dB+eA,所以Z的非恒定系数仍均匀,且独立于D/E。零点恒为xy。

更具体地,映射

(A,B,C1,…,Ct)⟷(D,E,Z1,…,Zt)

在两侧各q^{3t+2}份随机带之间是双射:给右边后,取A=F−D、B=G−E,再取C=Z−dB−eA−de,零点自动为ab。因而右侧恰是理想Z的随机尾系数,配上模拟器的独立D/E随机币。

被腐化方的A_I/B_I/C_I由这份右侧数据和自身输入/输出唯一确定,正是模拟器的三个公式。于是对任意固定输入、允许的辅助信息z和I,有

(ViewIreal,Z,z)=d(Sim(I,FI,GI,ZI),Z,z).

这里的 Z 表示全部参与者输出,用于定义中的联合测试,并不表示在线协议向每方广播整份输出。两侧采用同一个固定z或同一输入先验;由于预处理与它们独立,混合后仍相等。任意后处理也保持同分布。|I|≤t同时保证单看输出共享本身不额外揭示xy。

例如固定主例的第一方输入(7,9)、输出5,模拟器抽到D=(1,10)、E=(2,7)时,恢复a₁=7、b₁=0、c₁=0,完整广播也与上表相同。一个记录相同只是复算;覆盖所有记录的双射才是完美模拟证明。这个终点模拟器会使用理想输出,不据此声称已经构造了必须提前回应在线环境的可组合模拟器。

一轮通信与真实参考器成本 ​

单门在线可把D/E两个打开合并为一轮,每方广播两个域元素;按理想广播计共2n个域元素。用点对点逐收件人发送实现广播时,发送量另为O(n²),广播机制本身的开销不包含在2n中。预处理生成三元组的工作也不属于这项在线成本。[2,§3.4]

数学核心在已有零点插值权重时,每方从k=t+1份消息恢复d/e,需O(k)次域乘加,再做常数次局部修正。下载参考器额外检查整张表是否来自次数至多t的多项式:先预计算k个拉格朗日分母,再对n个坐标逐项求值,一次open用O(nk²)次域乘加及O(k)次求逆。安装、输入检查、差值打开和输出诊断调用固定次数,单门仍为O(nk²)域操作级工作,不能把这些全表检查隐藏在O(k)核心界里。

参考轨迹占O(n+k)个域元素;保留M组三元组的池占O(Mn)元素,已用编号也保留以阻止重放。初始化的小素数试除及整数位费用另计。参考器持有完整表以便重放,不是给真实单方读取其他份额的权限;diagnostic_product仅为离线检查输出,实际协议不发送这个值。

综合练习要求交完整差值向量、同次数输出及一份模拟记录,再实际复现次数上升、复用泄漏和错误相关性。输出共享若作为后续门输入,还须在明确的多门模型里安排每门独立预处理与组合证明。

参考资料
  1. Donald Beaver,Efficient Multiparty Protocols Using Circuit Randomization,CRYPTO’91,LNCS576,Springer,1992,pp.420–432。§1一次性表;§2及图2,pp.424–426;§2.3,pp.428–430。原文处理完整电路和其故障模型,本页另固定单门、理想预处理、静态被动终点接口。
  2. David Evans、Vladimir Kolesnikov、Mike Rosulek,A Pragmatic Introduction to Secure Multi-Party Computation,Foundations and Trends in Privacy and Security,2018,所链版本2020-04-15,§3.4,pp.44–46:两次打开、共享抽象、预处理成本和一次性限制。本文给出完整广播多项式及全部输出的自包含双射证明。
关系图谱5 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系

使用的工具