乐趣区

关于mpc:隐私计算笔谈MPC系列专题十九三方复制秘密共享五

回顾一下,最近几次的科普咱们介绍了三方复制机密共享的机密分享形式,其次要利用为作为隐衷爱护机器学习的隐衷爱护框架,将数据作为机密,按机器学习对数据的操作进行平安多方计算。

机器学习须要对数据进行定点数的加法、乘法、矩阵运算等,须要三方复制机密共享也有对应的这些操作。因而之后咱们介绍了在和下三方复制机密共享的乘法。在进行定点数运算时会带来定点数精度扩充问题,于是咱们接着介绍了两个定点数截断算法 Truncate I 和 Truncate II。机密在三方复制机密共享中有 \(Z_2 \) 和 \(Z_{2^k} \) 两种示意形式,须要有相互转换的形式,咱们接着介绍了将在 \(Z_{2^k} \) 下的子机密 \([x]^A \) 转换为在 \(Z_2 \) 下的子机密 \([x]^B \) 的 Bit Decomposition 算法。

有两种子机密的示意模式,那么当须要两个不同示意模式的机密进行计算,如须要子机密 \([x]^A \) 和子机密 \([y]^B \) 进行计算 \([x]^A[y]^B=[xy]^A \) 时又该怎么办呢?将 \([x]^A \) 转换为 \([x]^B \),或者将 \([y]^B \) 转换为 \([y]^A \) 进行计算,是一种方法。本次科普将介绍更高效的跨机密示意模式的计算方法。在介绍实现夸机密示意模式的计算方法之前,先介绍一种半诚恳的三方 OT 和计算 \(a[b]^B=[ab]^A \) 的办法。

三方 OT

与单方 OT 相比,这个三方 OT 协定较为简单,是单方 OT 的一个变形,理论仍旧只有两方进行 OT,而让第三方作为 OT 协定的帮助者。假如参与者为 Alice、Bob、Candy,Alice 是机密的发送方,Bob 是机密的接管方,而 Candy 则是帮助者,则整个三方 OT 协定能够被示意成 \(((m_0,m_1),𝑐,𝑐)→ (⊥,m_c,⊥) \), 符号「⊥」示意空,即未接管到信息。

OT 协定的具体流程为:首先 Alice 和 Candy 独特产生两个𝑘比特的随机数 \(w_0,w_1 \),Alice 和 Candy 都晓得 \(w_0,w_1 \) 的具体值,接着 Alice 计算 \(m_0\oplus w_0,m_1\oplus w_1 \),并且将 \(m_0\oplus w_0,m_1\oplus w_1 \) 发送给 Bob。Bob 将本人的抉择比特𝑐发送给 Candy,Candy 依据抉择比特的值发送 \(w_c \) 给 Bob,Bob 利用 \(w_c \) 即可胜利解密出 \(m_c \)。

残缺执行实现后,Bob 只取得了 \(m_c \),Candy 只晓得 \(c,w_0,w_1 \) 而不晓得 \(m_0,m_1 \),Alice 只晓得 \(w_o,w_1,m_0,m_1 \), 而不晓得 Bob 的抉择,三者都只把握了局部信息。

跨示意模式的子机密计算

接着介绍计算 \(a[b]^B=[ab]^A \) 的形式:最简略的例子是𝑎为 \(Z_{2^k} \) 上的明文,而𝑏为单比特。机密𝑏以 \((b_1,b_2,b_3) \) 的模式被三方分享,Alice 把握 \((b_1,b_2) \),Bob 把握 \((b_2,b_3) \),Candy 把握 \((b_3,b_1) \)。首先 Alice(发送者)在环 \(Z_{2^k} \) 上产生一个随机数 𝑟,接着产生两个音讯 \(m_0=(0\oplus b_1\oplus b_2)a-r \) 和 \(m_1=(1\oplus b_1\oplus b_2)a-r \)。Bob(接收者)把握有 \(b_3 \),而 Candy(帮助者)也把握有 \(b_3 \),因而三者能够进行上述的三方 OT。Alice 作为 OT 的发送方,在这次 OT 中的输出为 \(m_i=(i\oplus b_1\oplus b_2)a-r,i\in \) {0,1};Bob 作为接管方,在这次 OT 的输出为 \(b_3 \);Candy 则作为帮助者。留神 \(b_1,b_2,b_3 \) 都是单比特值,因而 Bob 通过 OT 能够取得 \(m_{b_3}=(b_3\oplus b_1\oplus b_2)a-r=ba-r \)。留神咱们指标是让参加的三方取得 \([ab]^A \)。

接着,Alice、Bob 和 Candy 能够利用之前事后产生的 \((s_1,s_2,s_3) \) 来计算 \(^A=[ab]^A=(s_1+r,ab-r+s_3,s_3) \)。留神 Bob 曾经取得了𝑏𝑎−𝑟,也把握了 \(s_2,s_3 \),因而 Bob 能够本地计算 \(c_2=ab-r+s_3 \),同样 Alice 也可本地间接计算 \(c_1=s_1+r \),Candy 自身就把握有 \(c_3=s_3 \)。

图:三方 OT 计算 \(a[b]^B \)

回顾一下三方复制机密共享的规定,要求 Alice 把握 \(c_1 \),Bob 把握 \(c_2,c_3 \),Candy 把握 \(c_3,c_1 \)。因而为了合乎复制机密共享的规定,Bob 计算 \(c_2=ab-r+s_3 \) 之后,须要再将 \(c_2 \) 发送给 Alice,同样 Alice 在计算完 \(s_1+r \) 后须要将它发送给 Candy。或者也能够再进行一次三方 OT,这次由 Bob 来表演发送方,Bob 在 OT 协定的输出为 \(m_i=(i\oplus b_2\oplus b_3)a-r+s_3 \), 𝑖∈{0,1},接管方由 Alice 表演,Alice 输出抉择比特 \(b_1 \) 来取得音讯 \(c_2=ab-r+s_3 \)。这样就胜利的实现了 \(^A=[ab]^A=(s_1+r,ab-r+s_3,s_3) \) 的计算。

有了 \(a[b]^B=[ab]^A \) 的计算形式,咱们就能够进一步计算 \([a]^A[b]^B=[ab]^A \) 了。\(a[b]^B \) 和 \([a]^A[b]^B \) 的区别只是前者𝑎以明文的模式,而后者是以密文的模式,思考一下复制秘钥共享的性质,实际上 \([a]^A=a_1+a_2+a_3 \),因而 \([a]^A[b]^B=a_1[b]^B+(a_2+a_3)[b]^B \)。只需进行两次 \(a[b]^B \) 模式的乘法,再进行加法,即可胜利计算出 \([a]^A[b]^B \)。

退出移动版