三方复制秘密分享
复制秘密共享(three-party replicated secret sharing),是另一种秘密共享技术。本次科普要介绍的是Araki等人的半诚实的三方复制秘密共享协议,用于在三方环境下的安全多方计算和秘密共享,可以容忍最多一个腐化用户,其相比于Shamir(2, 3)来说有非常小的通信量和计算量。

 

首先介绍在布尔电路下的情景,假设参与者分别为 Alice、Bob和Candy,三者的序号分别记为1、2、3。在复制秘密共享中,一个单比特的秘密𝑥会被生成为三个子秘密𝑥1,𝑥2,𝑥3,且𝑥=𝑥1⊕𝑥2⊕𝑥3。具体方式为:秘密分享者首先生成三个随机数𝑎1,𝑎2,𝑎3,并且满足𝑎1⊕𝑎2⊕𝑎3=0。让子秘密𝑥1=𝑎3⊕𝑥,𝑥2=𝑎1⊕𝑥,子秘密𝑥3=𝑎2⊕𝑥。则𝑥1⊕𝑥2⊕𝑥3=𝑎1⊕𝑎2⊕𝑎3⊕𝑥⊕𝑥⊕𝑥=𝑥。让Alice、Bob和Candy分别持有(𝑎1,𝑥1), (𝑎2,𝑥2), (𝑎3,𝑥3),将这种秘密分享方式简记为[𝑥]。满足限制条件𝑎1⊕𝑎2⊕𝑎3=0下生成随机数𝑎1,𝑎2,𝑎3的具体方式之后再进行介绍。

 

 

在这种情况下,任意两个参与者合谋就可以恢复出秘密𝑥,如Bob和Candy合谋,则Candy可以利用自己手中的𝑥3和Bob手中的𝑎2,计算𝑥3⊕𝑎2=𝑎2⊕𝑥⊕𝑎2=𝑥。 

 

在安全多方计算中,只要实现了多方加法和多方乘法,即可实现完备。因此接下来开始介绍该三方复制秘密共享协议实现多方加法和多方乘法的方式。此时Alice已经持有了(𝑎1,𝑥1), (𝑏1,𝑦1),Bob持有了(𝑎2,𝑥2), (𝑏2,𝑦2), Candy持有了(𝑎3,𝑥3), (𝑏3,𝑦3)。

 

首先是XOR(加法)的实现方式:要计算 [𝑧]=[𝑥+𝑦],Alice、Bob和Candy只需要分别本地计算𝑥𝑖+𝑦𝑖,𝑖∈{ 1,2,3}即可。以Alice为例,因为𝑥1=𝑎3⊕𝑥,𝑦1=𝑏3⊕𝑦,则𝑥1⊕𝑦1=𝑎3⊕𝑥⊕𝑏3⊕𝑦=(𝑎3⊕𝑏3)⊕(𝑥⊕𝑦)=(𝑎3⊕𝑏3)⊕𝑧,若将𝑎1⊕𝑏1记为𝑐1,𝑎2⊕𝑏2记为𝑐2,𝑎3⊕𝑏3记为𝑐3,则Alice、Bob和Candy在分别完成本地计算𝑥𝑖+𝑦𝑖,𝑖∈{ 1,2,3}后,Alice可以得到𝑧1=𝑐3⊕𝑧,Bob可以得到𝑧2=𝑐1⊕𝑧,Candy可以得到𝑧3=𝑐2⊕𝑧;且𝑐1⊕𝑐2⊕𝑐3=𝑎1⊕𝑎2⊕𝑎3⊕𝑏1⊕𝑏2⊕𝑏3=0⊕0=0,由此满足之前的秘密分享定义,𝑧1⊕𝑧2⊕𝑧3=𝑧,𝑐1⊕𝑐2⊕𝑐3=0。

 

 

接着是AND(乘法)的实现方式:要实现乘法首先需要另外引入三个随机数,记为𝛼, 𝛽, 𝛾,且满足𝛼⊕𝛽⊕𝛾=0,Alice掌握𝛼,Bob掌握𝛽,Candy掌握𝛾。

 

 

Alice计算𝑟1=𝑥1𝑦1⊕𝑎1𝑏1⊕𝛼,并把𝑟1发送给Bob;Bob计算𝑟2=𝑥2𝑦2⊕𝑎2𝑏2⊕𝛽,并把𝑟2发送给Candy;Candy 计算𝑟3=𝑥3𝑦3⊕𝑎3𝑏3⊕𝛾,并把𝑟3发送给Alice。 

 

接着Alice本地计算𝑐1=𝑟1⊕𝑟3,𝑧1=𝑟1;Bob本地计算𝑐2=𝑟2⊕𝑟1,𝑧2=𝑟2;Candy本地计算𝑐3=𝑟3⊕𝑟2,𝑧3=𝑟3。 

 

正确性证明: 

 

 

又因为

 

 

因此:

 

𝑥1𝑦1⊕𝑥2𝑦2⊕𝑥3𝑦3=𝑎1𝑏1⊕𝑎2𝑏2⊕𝑎3𝑏3⊕𝑥(𝑏1⊕𝑏2⊕𝑏3)⊕𝑦(𝑎1⊕𝑎2⊕𝑎3)⊕𝑥𝑦=𝑎1𝑏1⊕𝑎2𝑏2⊕𝑎3𝑏3⊕𝑥𝑦 

 

把𝑥1𝑦1⊕𝑥2𝑦2⊕𝑥3𝑦3的结果代入到𝑧1⊕𝑧2⊕𝑧3可得: 

 

 

而𝑐1⊕𝑐2⊕𝑐3=𝑟1⊕𝑟3⊕𝑟2⊕𝑟1⊕𝑟3⊕𝑟2= 0,即:

 

𝑧1=𝑐3⊕𝑥𝑦 

𝑧2=𝑐1⊕𝑥𝑦

𝑧3=𝑐2⊕𝑥𝑦

 

其中𝑧1⊕𝑧2⊕𝑧3=𝑥𝑦,𝑐1⊕𝑐2⊕𝑐3=0,由此得证乘法的正确性。 

 

满足限制条件𝑎1⊕𝑎2⊕𝑎3=0下生成随机数𝑎1,𝑎2,𝑎3的方式为:Alice、Bob、Candy分别生成随机数𝜌1,𝜌2,𝜌3,Alice将𝜌1发送给Bob,Bob将𝜌2发送给Candy,Candy将𝜌3发送给Alice。则Alice计算𝑎1=𝜌1⊕𝜌3,Bob计算𝑎2=𝜌2⊕𝜌1,Candy计算𝑎3=𝜌3⊕𝜌2

 

显然:

𝑎1⊕𝑎2⊕𝑎3=𝜌1⊕𝜌3⊕𝜌2⊕𝜌1⊕𝜌3⊕𝜌2=0。