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

三方复制机密分享

复制机密共享（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。 

显然：