共享随机数
本次科普次要介绍多方比拟的实现办法。回顾一下，之前介绍过的Shamir(t,n)机密分享协定能够实现机密分享，Shamir(t,n)协定次要基于拉格朗日插值，也能够艰深地了解成个方程求解个未知数。
BGW协定能够实现单比特分享，本次要介绍另一个比特分享形式。利用比特分享的形式，能够对比特的一个数按比特进行多方分享，之后能够据此实现多方比拟。多方比拟则能够用来结构平安多方计算的根底模块，无论是隐衷爱护的机器学习还是隐衷爱护的DNA比拟等，都须要用到多方比拟模块。
按比特分享
如有一个比特串\( =__{-1}…_1 \)，\( _1 \)到\( _ \)别离是组成的各个比特，即的值为\( a=\sum {_{i=1}^{l}} 2^{i-1} a_{i} \)。对进行比特分享即对的各个比特进行分享，每个参与者拿到\( _1,…,_ \)的个子机密。将参与者\( _ \)拿到的\( _ \)的子机密记为\( _{,} \)，则对比专长的进行比特分享后参与者\( _ \)可能取得\( _{1,},_{2,},…,_{,} \)。
首先简要介绍一个多个参与者独特产生同一个随机数的形式：假如有个参与者\( _1,…,_ \)，每个参与者\( _ \)都产生一个随机数\( _ \)，并通过Shamir(t,n)机密分享机制将\( _ \)进行分享，记\( _{,} \)为参与者\( _ \)取得的\( _ \)的子机密。因而当每个参与者都产生随机数并分享后，参与者\( _ \)能够取得\( _{1,},…,_{,} \)。
多方随机数生成
参与者\( _ \)取得子机密\( _{1,},…,_{,} \)之后，将它们进行累加，将累加后果记为\( {_}' \)，\( r_{i}^{\prime}=\sum{_{j=1}^{n}} r_{j, i} \)。用符号示意\( _1,…,_ \)之和，即\( r=\sum{_{i=1}^{n}} r_{i} \)，则\( {_}' \)就是的一个子机密。
因为\( _{1,} \)是\( _1 \)的一个子机密，\( _{,} \)是的一个子机密，因为Shamir(t,n)具备可加性（在第二次科普中介绍过）。假如参与者\( _1 \)的\( _1 \)的机密调配函数是\( _1() =_{t-1}^{t-1}+⋯+_1+_1 \)，参与者\( _2 \)的\( _2 \)的机密调配函数是\( _2()=_{t-1}^{t-1}+⋯+_1+_2 \)，则参与者\( _1 \)和\( _2 \)调配给参与者\( _ \)的子机密别离为\( _{1,}=_1() \)和\( _{2,}=_2() \)，二者相加为：
\( _{1,}+_{2,}=_1()+_2()=(_{t-1}+_{t-1})^{t-1}+⋯+(_1+_1)+_1+_2 \)
即\( _{1,}+_{2,} \)也是\( _1+_2 \)的一个子机密，\( _{1,1}+_{2,1},_{1,2}+_{2,2},…,_{1,}+_{2,} \)也是\( _1+_2 \)的子机密。
同理\( {_}'=_{1,1}+⋯+_{,1}, {_2}'=_{1,2}+⋯+_{,2}, {_}'=_{1,}+⋯+_{,} \)是\( r=\sum{_{i=1}^{n}} r_{i}=r_{1}+\cdots+r_{n} \)的子机密。
留神此时每个参与者\( _ \)都不晓得其余参与者产生的随机数\( _ \)，因而参与者\( _ \)也无奈计算出的具体值，然而他通过计算\( r_{i}^{\prime}=\sum{_{j=1}^{n}} r_{j, i} \)能够计算出的一个子机密\( {_}' \)。通过每个参与者都产生一个随机数并进行机密共享，所有参与者独特合作产生了一个随机数\( r=\sum{_{i=1}^{n}} r_{i} \)，然而每个参与者\( _ \)都不晓得的具体值，都只把握的一个子机密\({_}' \)。
随机单比特分享（Joint Random Bit Sharing）
在学习了多方独特产生随机数后，能够利用此来实现多方的随机单比特分享，每个参与者拿到一个随机比特的Share，在重构之前每个参与者都不晓得该随机比特的具体值。首先所有参与者利用上节所讲述的共享随机数生成形式独特生成一个随机数，将其记为，将参与者\( _ \)拿到的的子机密记为\( {_}' \)（放弃与上节的符号对立），用[]示意处于被分享成子机密的状态，[]由\( {_1}',…,{_}' \)组成。
之后通过第二次科普介绍的Shamir多方乘法，计算\( [^2] \)，参与者\( _ \)可能计算出\( ^2 \)的一个子机密。之后所有参与者分享本人计算出的\( ^2 \)的子机密，即公开\( [^2] \)，每个参与者通过公开的\( [^2] \)都可应用拉格朗日插值法重构出\( ^2 \)，若重构出的\( ^2=0 \)则各方再从新生成随机数。
参与者\( _ \)在计算出\( ^2 \)后，计算\( r=\sqrt{r^2} \) ，因为这些操作都是在无限域内进行，因而0<<，此时可能计算出两个′′，′′=−或′′=。则\( (′′)^{-1} \)的逆乘上有两种后果，\( (′′)^{-1}=^{−1} \)或者\( (′′)^{-1}=1 \)。因为\( ′′\cdot(′′)^{-1}=1 \)，当′′=时，\( (′′)^{-1}=^{-1}=1 \)；当′′=−时，\( (′′)^{-1}= (−)^{-1} =(−1)\cdot^{-1}=−1 \)。 参与者能够约定选取\( 0<′′<\frac{q}{2} \)，那么所有参与者就能够计算出雷同的′′，参与者\( _ \)设置\( ^{-1}=(′′)^{-1} \)
对于参与者\( _ \)来说，\( _ \)把握的子机密\( {_}' \)，\( _ \)设置\( _=2^{-1}((^{-1}){_}'+1) \)，\( _ \)即为\( _ \)取得的随机比特的一个子机密。因为参与者\( _ \)只晓得，对于\( _ \)来说仍旧有两种可能，别离是\( ±\sqrt{r^2} \)，因而\( _ \)无奈确定的值是0还是1，只有所有参与者对进行重构能力确定的值，从而计算出。是所有参与者独特产生的随机数，因而的值也是随机的，且在重构之前每个参与者都只把握随机比特的一个子机密，不晓得的具体值。