基于秘密共享的MPC:GMW、BGW、Beaver triple

这篇具有很好参考价值的文章主要介绍了基于秘密共享的MPC:GMW、BGW、Beaver triple。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

资料:

  1. 主要参考 - MPC综述电子书:Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation[J]. Foundations and Trends® in Privacy and Security, 2018, 2(2-3): 70-246.
  2. Goldreich, O., S. Micali, and A. Wigderson. 1987. “How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority”. In: 19th Annual ACM Symposium on Theory of Computing. Ed. by A. Aho. ACM Press. 218–229.
  3. Ben-Or, M., S. Goldwasser, and A. Wigderson. 1988. “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)”. In: 20th Annual ACM Symposium on Theory of Computing. ACM Press. 1–10.
  4. Beaver, D. 1992. “Efficient Multiparty Protocols Using Circuit Randomization”. In: Advances in Cryptology – CRYPTO’91. Ed. by J. Feigenbaum. Vol. 576. Lecture Notes in Computer Science*. Springer, Heidelberg. 420–432.
  5. Shamir秘密共享方案:https://blog.csdn.net/weixin_44885334/article/details/124640944

我们用MPC来指代 n ≥ 3 n \ge 3 n3的参与者,我们用2PC来表示 n = 2 n=2 n=2的情况。

  1. 某些 MPC 方案是需要大多数诚实的,因此 n = 2 n=2 n=2时不存在解。
  2. 对于 2PC 的 Yao’s GC,推广到 MPC 是不容易的,因为电路生成者与任意的电路计算者串通,就可以得到中间结果的一些方程。需要一些新技术来推广GC。

可以利用有同态性质的秘密共享方案,基于GMW范式(1.Share, 2.Eval, 3.Recover)来搭建MPC协议。由于如下方案使用的 SS 协议都不是 VSS,因此搭建的 MPC 都是抵抗半诚实敌手的,无法阻止恶意敌手的破坏。

GMW Protocol(1987)

GMW方案是基于可加的秘密共享(additive shares)的MPC方案,它可以处理 n ≥ 2 n \ge 2 n2的所有情况。它可以工作在布尔电路(Boolean circuit)和算术电路(Arithmetic circuit)上,这里仅介绍布尔电路的协议。

2PC

SS scheme

P 1 P_1 P1拥有隐私输入 x ∈ { 0 , 1 } n x \in \{0,1\}^n x{0,1}n P 2 P_2 P2拥有隐私输入 y ∈ { 0 , 1 } n y \in \{0,1\}^n y{0,1}n

P 1 P_1 P1对于第 i i i个输入比特 x i ∈ { 0 , 1 } x_i \in \{0,1\} xi{0,1}

  1. 生成随机比特 r i ∈ R { 0 , 1 } r_i \in_R \{0,1\} riR{0,1}
  2. r i r_i ri发送给 P 2 P_2 P2,自己保留 x i ⊕ r i x_i \oplus r_i xiri

类似的, P 2 P_2 P2共享 y y y的各个比特。

秘密重构:两方广播各自的 ”share” s 1 , s 2 ∈ { 0 , 1 } s^1,s^2 \in \{0,1\} s1,s2{0,1},计算 s = s 1 ⊕ s 2 s=s^1 \oplus s^2 s=s1s2

NOT Gate

对于门 G G G的输入线 w i w_i wi上的秘密 s i s_i si P 1 P_1 P1持有 s i 1 s_i^1 si1 P 2 P_2 P2持有 s i 2 s_i^2 si2,易知
s i = s i 1 ⊕ s i 2 s_i = s_i^1 \oplus s_i^2 si=si1si2
P 1 P_1 P1翻转自己的share s j 1 = s i 1 ⊕ 1 s_j^1 = s_i^1 \oplus 1 sj1=si11,而 P 2 P_2 P2share保持不变,那么输出线 w j w_j wj上的share满足:
s j = s j 1 ⊕ s j 2 = s i ⊕ 1 s_j = s_j^1 \oplus s_j^2 = s_i \oplus 1 sj=sj1sj2=si1
这就是非门

XOR Gate

对于门 G G G的输入线 w i , w j w_i,w_j wi,wj和输出线 w l w_l wl P 1 P_1 P1持有 s i 1 , s j 1 s_i^1,s_j^1 si1,sj1 P 2 P_2 P2持有 s i 2 , s j 2 s_i^2,s_j^2 si2,sj2,易知
s i = s i 1 ⊕ s i 2 s j = s j 1 ⊕ s j 2 s_i = s_i^1 \oplus s_i^2\\ s_j = s_j^1 \oplus s_j^2 si=si1si2sj=sj1sj2
P 1 P_1 P1将自己的share相加,即 s l 1 = s i 1 ⊕ s j 1 s_l^1 = s_i^1 \oplus s_j^1 sl1=si1sj1 P 2 P_2 P2同理, s l 2 = s i 2 ⊕ s j 2 s_l^2 = s_i^2 \oplus s_j^2 sl2=si2sj2,那么
s l = s l 1 ⊕ s l 2 = s i ⊕ s j s_l = s_l^1 \oplus s_l^2 = s_i \oplus s_j sl=sl1sl2=sisj
这就是异或门

AND Gate

对于门 G G G的输入线 w i , w j w_i,w_j wi,wj和输出线 w l w_l wl P 1 P_1 P1持有 s i 1 , s j 1 s_i^1,s_j^1 si1,sj1 P 2 P_2 P2持有 s i 2 , s j 2 s_i^2,s_j^2 si2,sj2

为了计算 s i ∧ s j s_i \wedge s_j sisj P 1 P_1 P1 P 2 P_2 P2执行 1-out-of-4 OT协议

  1. P 1 P_1 P1设置如下函数
    S : = S s i 1 , s j 1 ( s i 2 , s j 2 ) = ( s i 1 ⊕ s i 2 ) ∧ ( s j 1 ⊕ s j 2 ) = s i ∧ s j S := S_{s_i^1,s_j^1}(s_i^2,s_j^2) = (s_i^1 \oplus s_i^2) \wedge (s_j^1 \oplus s_j^2) = s_i \wedge s_j S:=Ssi1,sj1(si2,sj2)=(si1si2)(sj1sj2)=sisj

  2. P 1 P_1 P1生成随机掩码(random mask bit) r ∈ R { 0 , 1 } r \in_R \{0,1\} rR{0,1},然后计算表格
    T G = ( r ⊕ S ( 0 , 0 ) r ⊕ S ( 0 , 1 ) r ⊕ S ( 1 , 0 ) r ⊕ S ( 1 , 1 ) ) T_G = \left( \begin{matrix} r \oplus S(0,0)\\ r \oplus S(0,1)\\ r \oplus S(1,0)\\ r \oplus S(1,1)\\ \end{matrix} \right) TG= rS(0,0)rS(0,1)rS(1,0)rS(1,1)

  3. P 1 P_1 P1 P 2 P_2 P2执行OT协议, P 2 P_2 P2输入 s i 2 , s j 2 s_i^2,s_j^2 si2,sj2挑选出其中一行
    s l 2 = T G ( s i 2 , s j 2 ) = r ⊕ S ( s i 2 , s j 2 ) s_l^2 = T_G(s_i^2,s_j^2) = r \oplus S(s_i^2,s_j^2) sl2=TG(si2,sj2)=rS(si2,sj2)

  4. P 1 P_1 P1设置 s l 1 = r s_l^1 = r sl1=r,容易验证,
    s l = s l 1 ⊕ s l 2 = S s i 1 , s j 1 ( s i 2 , s j 2 ) = s i ∧ s j s_l = s_l^1 \oplus s_l^2 = S_{s_i^1,s_j^1}(s_i^2,s_j^2) = s_i \wedge s_j sl=sl1sl2=Ssi1,sj1(si2,sj2)=sisj

对于其他的 2-to-1 Gate,修改 S S S的定义即可。当然, { N O T , X O R , A N D } \{NOT,XOR,AND\} {NOT,XOR,AND}是布尔完备的,其他门不必额外构造。

MPC

SS scheme

假设有 n n n个参与者, P i P_i Pi拥有隐私输入比特 x i ∈ { 0 , 1 } x_i \in \{0,1\} xi{0,1}

  1. 生成 n − 1 n-1 n1个随机比特 ∀ j ≠ i ,   r j ∈ R { 0 , 1 } \forall j \neq i,\, r_j \in_R \{0,1\} j=i,rjR{0,1}
  2. s j = r j s^j = r_j sj=rj发送给 P j P_j Pj P i P_i Pi自己保留 s i = x i ⊕ ( ⨁ j ≠ i r j ) s^i = x_i \oplus (\bigoplus_{j \neq i} r_j) si=xi(j=irj)

类似的, P j P_j Pj共享的隐私输入的各个比特。

秘密重构:多方广播各自的 ”share” s 1 , s 2 , ⋯   , s n ∈ { 0 , 1 } s^1,s^2,\cdots,s^n \in \{0,1\} s1,s2,,sn{0,1},计算 s = s 1 ⊕ s 2 ⊕ ⋯ ⊕ s n s=s^1 \oplus s^2 \oplus \cdots \oplus s^n s=s1s2sn

NOT Gate

P 1 P_1 P1翻转自己的share,而 P 2 , ⋯   , P n P_2,\cdots,P_n P2,,Pnshare保持不变,那么输出线上的share满足:
s ′ = ( s 1 ⊕ 1 ) ⊕ s 2 ⊕ ⋯ ⊕ s n = s ⊕ 1 s' = (s^1 \oplus 1) \oplus s^2 \oplus \cdots \oplus s^n = s \oplus 1 s=(s11)s2sn=s1
这就是非门

XOR Gate

对于门 G G G的输入线 w i , w j w_i,w_j wi,wj和输出线 w l w_l wl P k P_k Pk持有 s i k , s j k s_i^k,s_j^k sik,sjk,易知
s i = s i 1 ⊕ s i 2 s j = s j 1 ⊕ s j 2 s_i = s_i^1 \oplus s_i^2\\ s_j = s_j^1 \oplus s_j^2 si=si1si2sj=sj1sj2
∀ k ,   P k \forall k,\,P_k k,Pk将自己的share相加,即 s l k = s i k ⊕ s j k s_l^k = s_i^k \oplus s_j^k slk=siksjk,那么
s l = ( s i 1 ⊕ s j 1 ) ⊕ ⋯ ⊕ ( s i n ⊕ s j n ) = s i ⊕ s j s_l = (s_i^1 \oplus s_j^1) \oplus \cdots \oplus (s_i^n \oplus s_j^n) = s_i \oplus s_j sl=(si1sj1)(sinsjn)=sisj
这就是异或门

AND Gate

对于门 G G G的输入线 w i , w j w_i,w_j wi,wj和输出线 w l w_l wl P k P_k Pk持有 s i k , s j k s_i^k,s_j^k sik,sjk

容易看出,
s l = s i ∧ s j = ( s i 1 ⊕ ⋯ ⊕ s i n ) ∧ ( s j 1 ⊕ ⋯ ⊕ s j n ) = ( ⨁ k = 1 n s i k ∧ s j k ) ⊕ ( ⨁ k 1 ≠ k 2 s i k 1 ∧ s j k 2 ) \begin{aligned} s_l &= s_i \wedge s_j = (s_i^1 \oplus \cdots \oplus s_i^n) \wedge (s_j^1 \oplus \cdots \oplus s_j^n)\\ &= \left( \bigoplus_{k=1}^n s_i^k \wedge s_j^k \right) \oplus \left( \bigoplus_{k_1 \neq k_2} s_i^{k_1} \wedge s_j^{k_2} \right) \end{aligned} sl=sisj=(si1sin)(sj1sjn)=(k=1nsiksjk) k1=k2sik1sjk2
对于前半部分, P k P_k Pk可以本地计算
s l , 1 k = s i k ∧ s j k s_{l,1}^k = s_i^k \wedge s_j^k sl,1k=siksjk
对于后半部分,每一对 P k 1 , P k 2 P_{k_1},P_{k_2} Pk1,Pk2利用 2PC-GMW 里的 AND Gate,使用OT协议计算出
s l , 2 k 1 , k 2 ⊕ s l , 2 k 2 , k 1 = s i k 1 ∧ s j k 2 s_{l,2}^{k_1,k_2} \oplus s_{l,2}^{k_2,k_1} = s_i^{k_1} \wedge s_j^{k_2} sl,2k1,k2sl,2k2,k1=sik1sjk2
其中 s l , 2 k 1 , k 2 s_{l,2}^{k_1,k_2} sl,2k1,k2 P k 1 P_{k_1} Pk1持有, s l , 2 k 2 , k 1 s_{l,2}^{k_2,k_1} sl,2k2,k1 P k 2 P_{k_2} Pk2持有。

最后, P k P_k Pk将自己所有的share本地相加,
s l k = s l , 1 k ⊕ ( ⨁ k ′ ≠ k s l , 2 k , k ′ ) s_l^k = s_{l,1}^k \oplus \left( \bigoplus_{k' \neq k} s_{l,2}^{k,k'} \right) slk=sl,1k k=ksl,2k,k
容易验证,
s l = ⨁ k s l k = ⨁ k [ s l , 1 k ⊕ ( ⨁ k ′ ≠ k s l , 2 k , k ′ ) ] = ( ⨁ k = 1 n s l , 1 k ) ⊕ ( ⨁ k 1 ≠ k 2 ( s l , 2 k 1 , k 2 ⊕ s l , 2 k 2 , k 1 ) ) = s i ∧ s j \begin{aligned} s_l &= \bigoplus_k s_l^k = \bigoplus_k \left[ s_{l,1}^k \oplus \left( \bigoplus_{k' \neq k} s_{l,2}^{k,k'} \right) \right] \\ &= \left( \bigoplus_{k=1}^n s_{l,1}^k \right) \oplus \left( \bigoplus_{k_1 \neq k_2} \left(s_{l,2}^{k_1,k_2} \oplus s_{l,2}^{k_2,k_1}\right) \right) \\ &= s_i \wedge s_j \end{aligned} sl=kslk=k sl,1k k=ksl,2k,k =(k=1nsl,1k) k1=k2(sl,2k1,k2sl,2k2,k1) =sisj
这就完成了与门的计算。

对于 n ≥ 3 n \ge 3 n3,MPC-GMW 调用了 A 2 n A_2^n A2n次 2PC-GMW 的 AND Gate,也就是使用了 A 2 n A_2^n A2n次 OT 协议。对于 n = 2 n=2 n=2,只需调用 1 1 1次而非 A 2 2 = 2 A^2_2=2 A22=2次。

BGW Protocol(1988)

本协议工作在算术电路上,算术运算的域为 F \mathbb F F,要求大多数诚实(honest majority),也就是 n ≥ 3 n \ge 3 n3

Shamir SS scheme

对于秘密值 v ∈ F v \in \mathbb F vF,构造一个 t − 1 t-1 t1次的随机多项式 p ( x ) ∈ F [ x ] p(x) \in \mathbb F[x] p(x)F[x],使得 p ( 0 ) = α p(0)=\alpha p(0)=α
p ( x ) : = v + ∑ i = 1 t − 1 a i ⋅ x i p(x):= v + \sum_{i=1}^{t-1} a_i \cdot x^i p(x):=v+i=1t1aixi
然后将 ∀ i = 1 , ⋯   , n ,   p ( i ) \forall i=1,\cdots,n,\,p(i) i=1,,n,p(i)作为 v v v的share分配给 P i P_i Pi,记做 [ v ] [v] [v];确切地说, [ v ] = ( x i , y i = p ( x i ) ) [v] = (x_i,y_i=p(x_i)) [v]=(xi,yi=p(xi))

为了重建秘密, n n n个参与者中任意 t t t个人合作,利用拉格朗日插值公式
λ i : = ∏ j = 1 , j ≠ i t − x j ( x i − x j ) − 1 \lambda_i := \prod_{j=1,j \neq i}^t -x_j(x_i - x_j)^{-1} λi:=j=1,j=itxj(xixj)1
v ← ∑ i = 1 t y i ⋅ λ i ∈ Z q v \leftarrow \sum_{i=1}^t y_i \cdot \lambda_i \in Z_q vi=1tyiλiZq

这里的 λ i \lambda_i λi叫做Lagrange coefficients,只与 x i x_i xi有关,是公开的,可以预计算。于是秘密 v v v就是share y i y_i yi的线性组合。

Addition Gate

假设门 G G G的两条输入线是 α , β \alpha,\beta α,β,一条输出线是 γ \gamma γ

每一个参与者都持有输入线上的秘密的 shares [ v α ] , [ v β ] [v_\alpha],[v_\beta] [vα],[vβ],于是 P i P_i Pi可以本地计算share的加法
[ v γ ] = [ v α ] + [ v β ] = p α ( x i ) + p β ( x i ) [v_\gamma] = [v_\alpha] + [v_\beta] = p_\alpha(x_i)+p_\beta(x_i) [vγ]=[vα]+[vβ]=pα(xi)+pβ(xi)
容易验证,
∑ i = 1 t [ v γ ] i ⋅ λ i = ∑ i = 1 t ( [ v α ] i + [ v β ] i ) λ i = ∑ i = 1 t [ v α ] i λ i + ∑ i = 1 t [ v β ] i λ i = v α + v β \begin{aligned} \sum_{i=1}^t [v_\gamma]_i \cdot \lambda_i &= \sum_{i=1}^t ([v_\alpha]_i + [v_\beta]_i) \lambda_i \\ &= \sum_{i=1}^t [v_\alpha]_i \lambda_i + \sum_{i=1}^t [v_\beta]_i \lambda_i\\ &= v_\alpha + v_\beta \end{aligned} i=1t[vγ]iλi=i=1t([vα]i+[vβ]i)λi=i=1t[vα]iλi+i=1t[vβ]iλi=vα+vβ
因此, [ v γ ] = [ v α + v β ] [v_\gamma] = [v_\alpha + v_\beta] [vγ]=[vα+vβ],这就完成了加法门

Multiplication-by-constant Gate

假设门 G G G的一条输入线是 α \alpha α,一条输出线是 γ \gamma γ

每一个参与者都持有输入线上的秘密的 shares [ v α ] [v_\alpha] [vα],于是 P i P_i Pi可以本地计算share的数乘

[ v γ ] = c ⋅ [ v α ] = c ⋅ p α ( x i ) [v_\gamma] = c \cdot [v_\alpha] = c \cdot p_\alpha(x_i) [vγ]=c[vα]=cpα(xi)

容易验证,
∑ i = 1 t [ v γ ] i ⋅ λ i = ∑ i = 1 t ( c ⋅ [ v α ] i ) λ i = c ⋅ ∑ i = 1 t [ v α ] i λ i = c ⋅ v α \begin{aligned} \sum_{i=1}^t [v_\gamma]_i \cdot \lambda_i &= \sum_{i=1}^t (c \cdot [v_\alpha]_i) \lambda_i \\ &= c \cdot \sum_{i=1}^t [v_\alpha]_i \lambda_i\\ &= c \cdot v_\alpha \end{aligned} i=1t[vγ]iλi=i=1t(c[vα]i)λi=ci=1t[vα]iλi=cvα
因此, [ v γ ] = [ c ⋅ v α ] [v_\gamma] = [c \cdot v_\alpha] [vγ]=[cvα],这就完成了数乘门

Multiplication Gate

假设门 G G G的两条输入线是 α , β \alpha,\beta α,β,一条输出线是 γ \gamma γ

每一个参与者都持有输入线上的秘密的 shares [ v α ] , [ v β ] [v_\alpha],[v_\beta] [vα],[vβ],于是 P i P_i Pi可以本地计算share的乘法
[ v γ ] = [ v α ] ⋅ [ v β ] = p α ( x i ) ⋅ p β ( x i ) [v_\gamma] = [v_\alpha] \cdot [v_\beta] = p_\alpha(x_i) \cdot p_\beta(x_i) [vγ]=[vα][vβ]=pα(xi)pβ(xi)
根据离散傅里叶变换的性质,上述的 [ v γ ] [v_\gamma] [vγ]是多项式乘积 q ( x ) : = p α ( x ) p β ( x ) q(x):=p_\alpha(x)p_\beta(x) q(x):=pα(x)pβ(x)在点 x i x_i xi处的值。为了重构至多 2 t − 2 2t-2 2t2次的 q ( x ) q(x) q(x),原则上需要 2 t − 1 2t-1 2t1个shares,有
∑ i = 1 2 t − 1 [ v γ ] i ⋅ λ i = v α ⋅ v β = q ( 0 ) \begin{aligned} \sum_{i=1}^{2t-1} [v_\gamma]_i \cdot \lambda_i = v_\alpha \cdot v_\beta = q(0) \end{aligned} i=12t1[vγ]iλi=vαvβ=q(0)
当然,我们要的仅仅是 q ( 0 ) q(0) q(0)而非 q ( x ) q(x) q(x)。为了保持秘密分享的 t − t- tthreshold,可以重新选择一个多项式 Q ( x ) Q(x) Q(x),使得 Q ( 0 ) = q ( 0 ) Q(0) = q(0) Q(0)=q(0),这就是 degree-reduction step

  1. 每个 P i P_i Pi都生成自己的 share [ v γ ] i = q ( x i ) [v_\gamma]_i = q(x_i) [vγ]i=q(xi)的 threshold-t sharing [ q ( x i ) ] [q(x_i)] [q(xi)],发送给其他的参与者(也就是对 share 再进行 secret sharing)

  2. 每个 P i P_i Pi都利用拉格朗日插值公式,本地计算新的 share
    [ q ( 0 ) ] i = ∑ j = 1 2 t − 1 [ q ( x j ) ] i ⋅ λ j [q(0)]_i = \sum_{j=1}^{2t-1} [q(x_j)]_i \cdot \lambda_j [q(0)]i=j=12t1[q(xj)]iλj
    可以验证,
    ∑ i = 1 t [ q ( 0 ) ] i ⋅ Λ i = ∑ i = 1 t ( ∑ j = 1 2 t − 1 [ q ( x j ) ] i ⋅ λ j ) ⋅ Λ i = ∑ j = 1 2 t − 1 ( ∑ i = 1 t [ q ( x j ) ] i ⋅ Λ i ) ⋅ λ j = ∑ j = 1 2 t − 1 q ( x j ) ⋅ λ j = q ( 0 ) = Q ( 0 ) \begin{aligned} \sum_{i=1}^t [q(0)]_i \cdot \Lambda_i &= \sum_{i=1}^t \left( \sum_{j=1}^{2t-1} [q(x_j)]_i \cdot \lambda_j \right) \cdot \Lambda_i\\ &= \sum_{j=1}^{2t-1} \left( \sum_{i=1}^t [q(x_j)]_i \cdot \Lambda_i \right) \cdot \lambda_j\\ &= \sum_{j=1}^{2t-1} q(x_j) \cdot \lambda_j\\ &= q(0) = Q(0) \end{aligned} i=1t[q(0)]iΛi=i=1t(j=12t1[q(xj)]iλj)Λi=j=12t1(i=1t[q(xj)]iΛi)λj=j=12t1q(xj)λj=q(0)=Q(0)
    这里 Λ i \Lambda_i Λi Q ( x ) Q(x) Q(x)的拉格朗日系数,而 λ j \lambda_j λj q ( x ) q(x) q(x)的。

在上述步骤中,用到了 2 t − 1 2t-1 2t1个点,因此需要 2 t − 1 ≤ n 2t-1 \le n 2t1n,那么
t − 1 ≤ n − 1 2 < n 2 t-1 \le \frac{n-1}{2} < \frac{n}{2} t12n1<2n
由于任意 t t t个人串通就可以重构秘密,因此敌手数量不能超过 t − 1 t-1 t1,因此上述不等式要求 n n n个参与者大多数是诚实的。对于 n = 2 n=2 n=2,若存在一个敌手,那么就已经不满足条件了,因此无解。

Beaver triple(1992)

构建MPC的一个标准范式是分为预处理阶段(pre-processing phase )和在线阶段(online phase)。预处理阶段,参与者们通过交互,获得计算电路所需的值。在线阶段,参与者们只进行少量的通信,大部分计算都在本地进行。

BGW协议中,加法门、数乘门的计算都不必交互。而乘法门则需要执行大量的秘密共享协议,通信开销将严重影响电路计算。Beaver给出了一种关于任意的线性秘密分享 [ a + b ] = [ a ] + [ b ] , [ a b ] = [ a ] [ b ] [a+b]=[a]+[b],[ab]=[a][b] [a+b]=[a]+[b],[ab]=[a][b])的解决方案,可以将大多数通信转移到预计算阶段,在线阶段只需要很少的通信。GMW 的 AND Gate 以及 BGW 的 Mul Gate,都可以使用 Beaver 的方案加速!

Beaver triple(Multiplication triple):它是关于秘密共享值 [ a ] , [ b ] , [ c ] [a],[b],[c] [a],[b],[c]的三元组。随机数 a , b ∈ R F a,b \in _R \mathbb F a,bRF,且 c = a b c = ab c=ab,每个参与者都不知道 a , b , c a,b,c a,b,c的任何信息。

对于BGW里的乘法门,为了计算 v α , v β v_\alpha,v_\beta vα,vβ的乘积,

  1. 每个 P i P_i Pi本地计算 [ v α − a ] i = [ v α ] i − [ a ] i [v_\alpha - a]_i = [v_\alpha]_i-[a]_i [vαa]i=[vα]i[a]i,然后一起披露 d = v α − a d=v_\alpha-a d=vαa;由于 v α v_\alpha vα被随机掩码 a a a掩盖,因此没人知道 v α v_\alpha vα的任何信息。

  2. 每个 P i P_i Pi本地计算 [ v β − a ] i = [ v β ] i − [ b ] i [v_\beta - a]_i = [v_\beta]_i-[b]_i [vβa]i=[vβ]i[b]i,然后一起披露 e = v β − b e=v_\beta-b e=vβb;由于 v β v_\beta vβ被随机掩码 b b b掩盖,因此没人知道 v β v_\beta vβ的任何信息。

  3. 易知,
    v α v β = ( d + a ) ( e + b ) = d e + d b + a e + c \begin{aligned} v_\alpha v_\beta &= (d+a)(e+b)\\ &= de+db+ae+c \end{aligned} vαvβ=(d+a)(e+b)=de+db+ae+c

    因此,在 SS 下计算:
    [ v α v β ] = d e + d ⋅ [ b ] + e ⋅ [ a ] + [ c ] [v_\alpha v_\beta] = de+d \cdot [b]+e \cdot [a]+[c] [vαvβ]=de+d[b]+e[a]+[c]

    注意,这儿的 + , ⋅ +,\cdot +, 是指 shares 的加性运算(包括:两个 shares 相加、一个 shares 加上常数、一个 shares 乘以常数)。其中 d , e d,e d,e是公开的, a , b , c a,b,c a,b,c由各个参与者共享。任意的 P i P_i Pi都本地计算
    [ v α v β ] i = [ d e ] i + d ⋅ [ b ] i + e ⋅ [ a ] i + [ c ] i [v_\alpha v_\beta]_i = [de]_i + d \cdot [b]_i + e \cdot [a]_i + [c]_i [vαvβ]i=[de]i+d[b]i+e[a]i+[c]i

    注意,这儿的 + , ⋅ +,\cdot +, 却是 F \mathbb F F 上的运算(每个人持有的值 [ x ] i [x]_i [x]i都是域元素)。这儿可以简单令 P 1 P_1 P1持有 [ d e ] 1 = d e [de]_1=de [de]1=de,而其他的 P i P_i Pi持有 [ d e ] i = 0 [de]_i=0 [de]i=0

在上述在线算法中,唯一的通信就是 step 1、step 2 里的披露 d , e d,e d,e,每个 P i P_i Pi利用广播信道发送自己的 share 一次即可,单一总线网络就可以。而考虑原始的BGW,每次乘法门每个 P i P_i Pi都要生成和分发 [ q ( x i ) ] [q(x_i)] [q(xi)],这需要点对点的隐私信道,网络拓扑是完全图。

在预处理阶段,存在有效算法可以批量地(in a batch)生成 Beaver triple,且均摊成本很低(the amortized cost of each triple is a constant number of field elements per party)文章来源地址https://www.toymoban.com/news/detail-593142.html

到了这里,关于基于秘密共享的MPC:GMW、BGW、Beaver triple的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 基于共享矩阵的线性秘密共享方案原理、构造与代码实现

      线性秘密共享方案是一种加密技术,用于将一个秘密信息分割成多个片段,并将这些片段分发给多个参与者,只有当足够数量的参与者合作时,才能还原出完整的秘密信息。   线性秘密共享方案的基本原理是使用多项式插值。假设我们有一个 (t-1) 阶的多项式,其中

    2024年04月27日
    浏览(45)
  • 解析MPC多方计算钱包:私钥分片与备份的新安全前沿

    前言 什么是MPC钱包 1.1 定义和基本原理 当前用户的困境 MPC钱包简介 3.1 工作原理 3.2 解决问题的关键点 MPC钱包优势与劣势 4.1 优势 4.2 缺点 MPC主流算法实现 5.1 概述不同算法 市场竞品 6.1 竞品列表 个人观点 7.1 安全性评价 7.2 中心化问题 7.3 技术黑盒挑战 7.4 移植性局限 7.5 期望

    2024年01月16日
    浏览(45)
  • 基于量子同态的安全多方量子求和加密

    摘要 安全多方计算在经典密码学中一直扮演着重要的角色。量子同态加密(QHE)可以在不解密的情况下对加密数据进行计算。目前,大多数协议使用半诚实的第三方(TP)来保护参与者的秘密。我们使用量子同态加密方案代替TP来保护各方的隐私。在量子同态加密的基础上,提出了

    2024年02月13日
    浏览(43)
  • 基于量子同态加密的安全多方凸包协议

    摘要 安全多方计算几何(SMCG)是安全多方计算的一个分支。该协议是为SMCG中安全的多方凸包计算而设计的。首先,提出了一种基于量子同态加密的安全双方值比较协议。由于量子同态加密的性质,该协议可以很好地保护量子电路执行过程中数据的安全性和各方之间的交互。结

    2024年02月15日
    浏览(45)
  • 秘密共享(Secret Sharing,SS)

        秘密共享是一种重要密码学工具用于构建安全多方计算,其在诸多多方安全计算协议中被使用,例如拜占庭协议、多方隐私集合求交协议、阈值密码学等。 本文首先介绍秘密共享的概念,其次介绍秘密共享生成(基于不同的生成方式我们将其划分为基于位运算的加性秘密

    2024年02月02日
    浏览(36)
  • 深入理解Triple DES算法:安全加密的基础与应用

    title: 深入理解Triple DES算法:安全加密的基础与应用 date: 2024/4/13 19:56:05 updated: 2024/4/13 19:56:05 tags: 数据安全 隐私保护 加密技术 Triple DES DES算法 对称加密 密钥管理 引言 DES算法原理和工作方式 Triple DES(3DES)的介绍 背景 : 原理 : 优势 : 为什么需要对DES进行三次加密以增强

    2024年04月13日
    浏览(50)
  • 安全多方计算之一:什么是安全多方计算

    安全多方计算问题(SMC,Secure Multi-party Computation)由由中国计算机科学家、2000年图灵奖获得者姚启智教授于1982年在论文《Protocols for secure computations》中以百万富翁问题(两个百万富翁Alice和Bob想知道他们两个谁更富有,但他们都不想让对方及其他第三方知道自己财富的任何信

    2024年02月09日
    浏览(45)
  • 基于QSharedMemory的读写安全的共享内存

    多进程交互中,其中共享内存是比较常用的一种交互方式,比较高效且易于调试。网上虽然也有很多基于QSharedMemory的实现,但是都是比较基础的,同时读写,读完后分离进程之类的都没有完全保证安全性。所以我花了一整天重新封装了一个基于QSharedMemory的读写安全的类,包

    2024年01月18日
    浏览(40)
  • 安全多方计算简介

    安全多方计算(Secure Multi-Party Computation,SMPC)用于解决一组互不信任的参与方各自持有秘密数据,协同计算一个既定函数的问题。安全多方计算在保证参与方获得正确计算结果的同时,无法获得计算结果之外的任何信息。在整个计算过程中,参与方对其所拥有的数据始终拥有绝

    2024年02月07日
    浏览(40)
  • 隐私计算-多方安全计算

    多方安全计算(MPC:Secure Muti-Party Computation)理论是姚期智先生为解决一组互不信任的参与方之间在保护隐私信息以及没有可信第三方的前提下协同计算问题而提出的理论框架。 多方计算的目标就是对一组计算的参与者,每个参与者拥有自己的数据,并且不信任其它参与者和

    2024年02月16日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包