Mpc

回顾一下，最近几次的科普咱们介绍了三方复制机密共享的机密分享形式，其次要利用为作为隐衷爱护机器学习的隐衷爱护框架，将数据作为机密，按机器学习对数据的操作进行平安多方计算。 机器学习须要对数据进行定点数的加法、乘法、矩阵运算等，须要三方复制机密共享也有对应的这些操作。因而之后咱们介绍了在和下三方复制机密共享的乘法。在进行定点数运算时会带来定点数精度扩充问题，于是咱们接着介绍了两个定点数截断算法Truncate I和Truncate II。机密在三方复制机密共享中有\( Z_2 \)和\( Z_{2^k} \)两种示意形式，须要有相互转换的形式，咱们接着介绍了将在\( Z_{2^k} \)下的子机密\( [x]^A \)转换为在\( Z_2 \)下的子机密\( [x]^B \)的 Bit Decomposition算法。  有两种子机密的示意模式，那么当须要两个不同示意模式的机密进行计算，如须要子机密\( [x]^A \)和子机密\( [y]^B \)进行计算\( [x]^A[y]^B=[xy]^A \)时又该怎么办呢？将\( [x]^A \)转换为\( [x]^B \)，或者将\( [y]^B \)转换为\( [y]^A \)进行计算，是一种方法。本次科普将介绍更高效的跨机密示意模式的计算方法。在介绍实现夸机密示意模式的计算方法之前，先介绍一种半诚恳的三方OT和计算\( a[b]^B=[ab]^A \)的办法。 三方OT 与单方 OT 相比，这个三方 OT 协定较为简单，是单方 OT 的一个变形，理论仍旧只有两方进行OT，而让第三方作为 OT 协定的帮助者。假如参与者为Alice、Bob、Candy，Alice是机密的发送方，Bob是机密的接管方，而Candy则是帮助者，则整个三方 OT 协定能够被示意成\( ((m_0,m_1),,)→ (⊥,m_c,⊥) \),符号「⊥」示意空，即未接管到信息。 OT 协定的具体流程为：首先Alice和Candy独特产生两个比特的随机数\( w_0,w_1 \)，Alice和Candy都晓得\( w_0,w_1 \)的具体值，接着Alice计算\( m_0\oplus w_0,m_1\oplus w_1 \)，并且将\( m_0\oplus w_0,m_1\oplus w_1 \)发送给Bob。Bob将本人的抉择比特发送给Candy，Candy依据抉择比特的值发送\( w_c \)给Bob，Bob利用\( w_c \)即可胜利解密出\( m_c \)。 ...

在三方复制机密共享的基本操作中，有些操作在算数电路的环\( Z_{2^k} \)上进行效率高，而有些则在布尔电路上进行效率高，因而须要有操作将在环上示意的操作数转换为布尔示意（二进制示意），而操作数在平安多方计算中都是以子机密（Share）的模式，因而理论是将环上示意的三方复制机密共享子机密转换为按比特共享的子机密模式，记为\( [x]^{A} \rightarrow[x]^{B} \)。 之前的科普曾经介绍过将在域\( F_q \)下的子机密转换为按比特共享的子机密模式，三方复制机密共享则是在环上，因而须要应用新的比特合成和比特合成形式。本次科普就要介绍一下三方复制机密共享的比特合成和比特合成。 比特合成 比特合成\( [x]^{A} \rightarrow[x]^{B} \)，是将\( x\in Z_{2^k} \)的子机密转换为{ \( x[1],x[2],...,x[k] \) } ,\( x[i]\in \) { 0,1} 的子机密，并且 \( x[1],x[2],...,x[k] \)满足\( x=\Sigma_{i=1}^{k} 2^{i-1} x[i] \)。留神在之前的科普中，咱们把Alice、Bob、Candy别离把握\( (x_1,x_2),(x_2,x_3),(x_3,x_1) \)，作为对的机密分享，记为\( (x_1,x_2,x_3) \)： 图：对的机密分享\( (x_1,x_2,x_3) \) 那么显然Alice能在本地实现对\( x_1 \)的比特合成，因为Alice把握了\( x_1 \)，Alice只需本地将组成\( x_1 \in Z_{2^k} \)的各个比特离开，即可实现从\( Z_{2^k} \)到布尔示意的转换。 同理，Bob和Candy也可本地实现\( x_2,x_3 \)从\( Z_{2^k} \)到布尔示意的转换。 因为Alice、Bob、Candy三者把握的子机密对别离为：\( (x_1,x_2),(x_2,x_3),(x_3,x_1) \) 因而Alice、Bob、Candy别离本地实现对\( x_1,x_2,x_3 \)的比特合成，\( [x_1]^B=(x_1,0,0),[x_2]^B=(0,x_2,0),[x_3]^B=(0,0,x_3) \)，即Alice把握\( x_1 \)和\( x_2 \)的比特示意，Bob把握\( x_2 \)和\( x_3 \)的比特示意，Candy把握\( x_3 \)和\( x_1 \)的比特示意。用\( x_{i,j} \)示意子机密\( x_i \)的第位： ...

Truncate I 上次在【隐衷计算笔谈】系列科普里介绍了在布尔电路下和环下的三方复制机密共享，以及其实现加法和乘法的形式。本次科普介绍两种三方复制机密共享下的截断（Truncate） 操作。其中一种截断形式只须要三个参与者中的两者加入，不须要三者独特进行截断，以此缩小截断操作所须要的通信量。在三方复制机密共享中，任意两方合谋即可复原出机密，即其中任意两方就能够进行截断操作。 让\( =_1+_2+_3 \)，Alice、Bob、Candy别离把握 \( (_1,_2), (_2,_3), (_3,_1) \)。Bob和Candy二者事后产生一个随机数。 首先，Alice和Candy本地计算\( x_{1}^{\prime}=\frac{x_{1}}{2^{d}} \)，则Alice和 Candy都把握了 \( x_{1}^{\prime} \)。接着Bob本地计算\( x_{2}^{\prime}=\frac{x_{2}+x_{3}}{2^{d}} -r \)，并且将\( x_{2}^{\prime} \)发回给Alice，则此时Alice把握了(\( x_{1}^{\prime},x_{2}^{\prime} \))，Bob把握了\( x_{2}^{\prime} \)，Candy把握了\( x_{1}^{\prime} \)。再接着Bob和Candy本地计算\( x_{3}^{\prime} =r \)，协定的输入为(\( x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime} \))，Alice、Bob、Candy别离把握了 \( (x_{1}^{\prime},x_{2}^{\prime}), (x_{2}^{\prime},x_{3}^{\prime}), (x_{3}^{\prime},x_{1}^{\prime}) \)。  将\( x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime} \)相加进行验证可得： 该截断形式利用任意两者所把握的信息之和都蕴含了机密信息这一三方复制机密共享的特点，将单方的信息利用起来进行截断。显然，这个协定是半诚恳的，要求参加的三方都是恪守协定规定的用户，若违反规定，则任意两方串谋都能间接复原出机密信息。  Truncate II 该截断的核心思想是共享[]和[\( r^{\prime}=\frac{r}{2^{d}} \)]，指标是要计算出\( x^{\prime}=\frac{x}{2^{d}} \)，因而先向所有参与者揭发 [−] =[]−[]，每个参与者都取得明文的−，则所有用户都可在明文上计算\( \frac{x-r}{2^d} \)，再如下计算即可： 想要依据[]计算出\([ r^{\prime}]=[\frac{r}{2^{d}}] \)，有很多形式，间接利用Truncate I也能够， 然而Truncate II理论应用的是二进制上的截断。因为\( {[r]}^B \)是按比特分享的，假如的各个比特为从高位到低位别离为\( r_l,r_{l-1},...,r_1 \)，\( {[r]}^B \)理论为\( [r_1],[r_{l-1}],...,[r_1] \)，所以对\( {[r]}^B \)进行截断，只需间接抛弃\( [r_d],...,[r_1] \)即可。 ...

三方复制机密分享 复制机密共享（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 \)。  ...

单方比拟 之前曾经介绍过了利用加密电路或者比特合成来实现平安多方比拟。本次再介绍一种利用不经意传输来实现单方比拟的办法。 不经意传输在之前的科普进行过介绍，该比拟协定的次要思路为：将须要比拟的两个比特串分为多个局部，每个局部再进行比拟，最初利用树形构造进行组合。假如有比特串和比特串，将比特串划分为两个局部，别离为\( _1,_0 \)，将比特串也划分为\( _1 \)和\( _0 \)。 表达式1{<} 示意若<，则表达式1{<} 的值为1，否则为0。同理，表达式1{= } 示意若=则表达式的值为1，反之为0。 思考如下的比拟： $$\begin{array}{c}x=x_{1} \| x_{0} \\y=y_{1} \| y_{0} \\1\{x<y\}=1\left\{x_{1}<y_{1}\right\} \oplus\left(1\left\{x_{1}=y_{1}\right\} \wedge 1\left\{x_{0}<y_{0}\right\}\right) \quad \text { 式 } 1\end{array}$$ 把比特串和比特串分为两局部后，先比拟\( _1和_1 \)的大小，因为\( _1和_1 \)都是高位局部，因而若\( _1<_1 \)则比特串<；反之若\( _1>_1 \)则>，在这两种状况下无需在比拟\( _0,_0 \)的大小了。只有当\( _1=_1 \)时，须要通过比拟\( _0,_0 \)的大小关系来确定, 的大小关系。 式1就是该比拟协定的核心思想。该协定的具体流程为： 首先假如Alice把握比特串，Bob把握比特串，先思考最简略的状况，和等长均为比特且\( \frac{l}{m} \)为2的指数倍。 1. Alice和Bob别离对和进行等分：Alice：把进行等分，每份比特： $$x=x_{q-1}\|\cdots\| x_{0}$$ Bob：把进行等分，每份比特： $$y=y_{q-1}\|\cdots\| y_{0}$$ 2. Alice产生两个随机数，将其别离记为\( {<It_0,j>}_{B}^{0} , {<eq_0,j>}_{B}^{0} \)。Alice利用\( M=2^m \)个比特，别离为\( s_{j,0}...s_{j,M-1} \)来标识\( x_j \)的大小关系；利用个比特，别离为\( t_{j,0}...t_{j,M-1} \)来标识\( x_j \)的相等关系：  ...