本文由 Bing AI/New Bing/Sydney 根据这篇文章总结得出。
首先,我们假设有两个参与方S1和S2,他们分别持有秘密值x和y的加法分享值x1和x2,y1和y2。也就是说,x = x1 + x2,y = y1 + y2。他们想要计算x和y的乘积,但是不想暴露自己的分享值。
为了实现这个目的,他们需要在离线阶段预先生成一个三元组(a, b, c),满足c = a * b,并且将这个三元组的加法分享值分配给S1和S2。也就是说,S1持有(a1, b1, c1),S2持有(a2, b2, c2),其中a = a1 + a2,b = b1 + b2,c = c1 + c2。
在在线阶段,S1和S2分别计算e = x - a和f = y - b的分享值e1 = x1 - a1,e2 = x2 - a2,f1 = y1 - b1,f2 = y2 - b2。然后,他们通过一轮交互【加法】恢复出e和f。具体来说,S1将e1发送给S2,S2将e2发送给S1,然后他们分别计算e = e1 + e2。同理,他们也可以通过交换f1和f2来计算f = f1 + f2。
这样,他们就得到了e和f的真实值,而不是分享值。这是因为加法秘密共享的性质,即任何两个分享值的和等于原始秘密值的和。也就是说,e = x - a = (x1 + x2) - (a1 + a2) = (x1 - a1) + (x2 - a2) = e1 + e2。同理,f = y - b = f1 + f2。
有了e和f,他们就可以利用以下公式计算x和y的乘积的分享值:
xy = ef + af + be + c
这个公式可以通过展开(x - a)(y - b)=xy - a(y-b) - b(x-a) - ab得到。由于S1和S2已经知道a,b,c的分享值,他们可以在本地计算af,be,c的分享值。例如,S1可以计算af1 = a1 * f,be1 = b1 * e,c1 = c1。然后,他们可以利用加法秘密共享的同态性,将这些分享值相加,得到xy的分享值。例如,S1可以计算xy1 = ef + af1 + be1 + c1。同理,S2可以计算xy2 = ef + af2 + be2 + c2。这样,他们就完成了密文乘法,而不需要暴露自己的分享值。
参考文章:https://www.cnblogs.com/pam-sh/p/16994056.html
致谢:Bing AI/New Bing/Sydney