资料:
- 主要参考 - 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.
- 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.
- 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.
- 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.
- Shamir秘密共享方案:https://blog.csdn.net/weixin_44885334/article/details/124640944
我们用MPC来指代 n ≥ 3 n \ge 3 n≥3的参与者,我们用2PC来表示 n = 2 n=2 n=2的情况。
- 某些 MPC 方案是需要大多数诚实的,因此 n = 2 n=2 n=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 n≥2的所有情况。它可以工作在布尔电路(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},
- 生成随机比特 r i ∈ R { 0 , 1 } r_i \in_R \{0,1\} ri∈R{0,1},
- 将 r i r_i ri发送给 P 2 P_2 P2,自己保留 x i ⊕ r i x_i \oplus r_i xi⊕ri
类似的, 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=s1⊕s2
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=si1⊕si2
让
P
1
P_1
P1翻转自己的share,
s
j
1
=
s
i
1
⊕
1
s_j^1 = s_i^1 \oplus 1
sj1=si1⊕1,而
P
2
P_2
P2的share保持不变,那么输出线
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=sj1⊕sj2=si⊕1
这就是非门。
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=si1⊕si2sj=sj1⊕sj2
让
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=si1⊕sj1,
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=si2⊕sj2,那么
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=sl1⊕sl2=si⊕sj
这就是异或门。
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 si∧sj, P 1 P_1 P1和 P 2 P_2 P2执行 1-out-of-4 OT协议:
-
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)=(si1⊕si2)∧(sj1⊕sj2)=si∧sj -
P 1 P_1 P1生成随机掩码(random mask bit) r ∈ R { 0 , 1 } r \in_R \{0,1\} r∈R{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=⎝ ⎛r⊕S(0,0)r⊕S(0,1)r⊕S(1,0)r⊕S(1,1)⎠ ⎞ -
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)=r⊕S(si2,sj2) -
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=sl1⊕sl2=Ssi1,sj1(si2,sj2)=si∧sj
对于其他的 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},
- 生成 n − 1 n-1 n−1个随机比特 ∀ j ≠ i , r j ∈ R { 0 , 1 } \forall j \neq i,\, r_j \in_R \{0,1\} ∀j=i,rj∈R{0,1},
- 将 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=s1⊕s2⊕⋯⊕sn
NOT Gate
让
P
1
P_1
P1翻转自己的share,而
P
2
,
⋯
,
P
n
P_2,\cdots,P_n
P2,⋯,Pn的share保持不变,那么输出线上的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′=(s1⊕1)⊕s2⊕⋯⊕sn=s⊕1
这就是非门。
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=si1⊕si2sj=sj1⊕sj2
让
∀
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=sik⊕sjk,那么
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=(si1⊕sj1)⊕⋯⊕(sin⊕sjn)=si⊕sj
这就是异或门。
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=si∧sj=(si1⊕⋯⊕sin)∧(sj1⊕⋯⊕sjn)=(k=1⨁nsik∧sjk)⊕⎝
⎛k1=k2⨁sik1∧sjk2⎠
⎞
对于前半部分,
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=sik∧sjk
对于后半部分,每一对
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,k2⊕sl,2k2,k1=sik1∧sjk2
其中
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′=k⨁sl,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=k⨁slk=k⨁⎣
⎡sl,1k⊕⎝
⎛k′=k⨁sl,2k,k′⎠
⎞⎦
⎤=(k=1⨁nsl,1k)⊕⎝
⎛k1=k2⨁(sl,2k1,k2⊕sl,2k2,k1)⎠
⎞=si∧sj
这就完成了与门的计算。
对于 n ≥ 3 n \ge 3 n≥3,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 n≥3
Shamir SS scheme
对于秘密值
v
∈
F
v \in \mathbb F
v∈F,构造一个
t
−
1
t-1
t−1次的随机多项式
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=1∑t−1ai⋅xi
然后将
∀
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=i∏t−xj(xi−xj)−1
v
←
∑
i
=
1
t
y
i
⋅
λ
i
∈
Z
q
v \leftarrow \sum_{i=1}^t y_i \cdot \lambda_i \in Z_q
v←i=1∑tyi⋅λi∈Zq
这里的 λ 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=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β
因此,
[
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α]=c⋅pα(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=1∑t[vγ]i⋅λi=i=1∑t(c⋅[vα]i)λi=c⋅i=1∑t[vα]iλi=c⋅vα
因此,
[
v
γ
]
=
[
c
⋅
v
α
]
[v_\gamma] = [c \cdot v_\alpha]
[vγ]=[c⋅vα],这就完成了数乘门。
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
2t−2次的
q
(
x
)
q(x)
q(x),原则上需要
2
t
−
1
2t-1
2t−1个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=1∑2t−1[vγ]i⋅λi=vα⋅vβ=q(0)
当然,我们要的仅仅是
q
(
0
)
q(0)
q(0)而非
q
(
x
)
q(x)
q(x)。为了保持秘密分享的
t
−
t-
t−threshold,可以重新选择一个多项式
Q
(
x
)
Q(x)
Q(x),使得
Q
(
0
)
=
q
(
0
)
Q(0) = q(0)
Q(0)=q(0),这就是 degree-reduction step:
-
每个 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)
-
每个 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=1∑2t−1[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=1∑t[q(0)]i⋅Λi=i=1∑t(j=1∑2t−1[q(xj)]i⋅λj)⋅Λi=j=1∑2t−1(i=1∑t[q(xj)]i⋅Λi)⋅λj=j=1∑2t−1q(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
2t−1个点,因此需要
2
t
−
1
≤
n
2t-1 \le n
2t−1≤n,那么
t
−
1
≤
n
−
1
2
<
n
2
t-1 \le \frac{n-1}{2} < \frac{n}{2}
t−1≤2n−1<2n
由于任意
t
t
t个人串通就可以重构秘密,因此敌手数量不能超过
t
−
1
t-1
t−1,因此上述不等式要求
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,b∈RF,且 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β的乘积,
-
每个 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α的任何信息。
-
每个 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β的任何信息。
-
易知,
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)],这需要点对点的隐私信道,网络拓扑是完全图。文章来源:https://www.toymoban.com/news/detail-593142.html
在预处理阶段,存在有效算法可以批量地(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模板网!