关于区块链:隐私计算笔谈MPC系列专题十一共享随机数和比特分享

共享随机数

本次科普次要介绍多方比拟的实现办法。回顾一下，之前介绍过的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，只有所有参与者对𝑟进行重构能力确定𝑟的值，从而计算出𝑎。𝑟是所有参与者独特产生的随机数，因而𝑎的值也是随机的，且在重构之前每个参与者都只把握随机比特𝑎的一个子机密，不晓得𝑎的具体值。