安全多方计算之八：Mix-Match

M.Jakobsson和A.Juels提出了基于Mix-Match的安全多方计算协议构造方法，该类协议包括Mix与Match两个阶段：

• Mix阶段：通过构造混合网络，生成盲表（Blinded table）
• Match阶段：通过执行PET协议进行查表，得到对应的输出

最后参与者共同解密输出，该类协议参与者之间所需传输的消息量较少，对于逻辑运算和Bit运算较为高效。

1. 混合网络

从直观上讲，混合网络是一个多方协议，协议的输入是一个密文表，该密文表中的密文与一组明文有着一一对应的关系。协议将这个密文表随机置换后得到另外一个密文表，输出的密文表和相同的一组明文也是一一对应的。即输出的密文表是输入密文表的随机置换。

混合网络的安全性在于攻击者无法确定输出密文表中的某一条密文与输入密文表中的哪一条密文是对应的。

基于ElGamal加密方案的混合网络

假定参与混合网络的n nn个参与者都共享一个具备身份认证的广播信道（或存在一个公告板），将一个ElGamal加密方案的公钥y yy公布给每个参与者。由参与者集合P PP的某一个子集充当混合服务器（Mix Server）的角色，与y yy对应的私钥使用( t , n ) (t,n)(t,n)门限方案在混合服务器中分享。

混合网络的参与者将自己的输入广播或传送到公告板上，混合网络的输入是一个ElGamal的密文序列( α 1 , β 1 ) , ( α 2 , β 2 ) , ⋯   , ( α k , β k ) (\alpha_1,\beta_1),(\alpha_{2},\beta_{2}),\cdots,(\alpha_{k},\beta_{k})(α1,β1),(α2,β2),⋯,(αk,βk)混合服务器依次独立地将混合网络输入的密文序列进行再次加密，随机置换顺序，混合网络的输出也是一个ElGamal密文序列( α σ ( 1 ) ′ ′ , β σ ( 1 ) ′ ) , ( α σ ( 2 ) ′ ′ , β σ ( 2 ) ′ ) , ⋯   , ( α σ ( k ) ′ , β σ ( k ) ) (\alpha'_{\sigma(1)'},\beta'_{\sigma(1)}),(\alpha'_ {\sigma(2)'},\beta'_{\sigma(2)}), \cdots,(\alpha_{\sigma(k)'},\beta_{\sigma(k)})(ασ(1)′′,βσ(1)′),(ασ(2)′′,βσ(2)′),⋯,(ασ(k)′,βσ(k))其中( α i ′ ′ , β i ′ ) (\alpha'_{i'}, \beta'_ {i})(αi′′,βi′) 表示( α i , β i ) (\alpha_{i},\beta_{i})(αi,βi) 的随机再次加密结果, σ \sigmaσ 表示在k kk个元素上的随机置换。

2. PET协议

假设( α , β ) (\alpha,\beta)(α,β) 和( α ′ , β ′ ) (\alpha',\beta')(α′,β′)分别表示 m 1 , m 2 m_{1},m_{2}m1,m2 使用ElGamal加密方案加密后的密文，参与相同明文测试协议的参与者在不解密的情况下通过执行协议判断( α , β ) (\alpha,\beta)(α,β)和( α ′ , β ′ ) (\alpha',\beta')(α′,β′)所对应的明文是否相同。

考虑密文( ε , ζ ) = ( α / α ′ , β / β ′ ) (\varepsilon,\zeta) = (\alpha/\alpha',\beta/\beta')(ε,ζ)=(α/α′,β/β′)，如果( α , β ) ≡ ( α ′ , β ′ ) (\alpha, \beta)\equiv(\alpha',\beta')(α,β)≡(α′,β′)，则( ε , ζ ) ( \varepsilon, \zeta)(ε,ζ) 表示明文1 11加密后的密文。

PET（Plaintext Equivalence Test） 协议的基本思路是让协议的参与者P i P_{i}Pi使用如下的方法隐藏( ε , ζ ) (\varepsilon, \zeta)(ε,ζ):

P i P_{i}Pi选择z i ∈ Z q z_{i} \in Z_{q}zi∈Zq ,然后计算( ε i , ζ i ) = ( ε z i , ζ z i ) (\varepsilon_ {i}, \zeta_ {i}) = (\varepsilon^{z_{i}},\zeta^{z_{i}})(εi,ζi)=(εzi,ζzi)

• 如果( α , β ) ≡ ( α ′ , β ′ ) (\alpha, \beta)\equiv(\alpha',\beta')(α,β)≡(α′,β′)，( ε , ζ ) (\varepsilon, \zeta)(ε,ζ)代表1 11加密后的密文，则( ε i , ζ i ) (\varepsilon_ {i}, \zeta_ {i})(εi,ζi)仍是1 11加密后的密文
• 如果( α , β ) ≠ ( α ′ , β ′ ) (\alpha, \beta)\neq (\alpha',\beta')(α,β)=(α′,β′)，( ε , ζ ) (\varepsilon, \zeta)(ε,ζ)代表 m 1 / m 2 m_{1}/m_{2}m1/m2 加密后的密文，由于z i z_{i}zi 是一个随机数，所以( ε i , ζ i ) (\varepsilon_ {i}, \zeta_ {i})(εi,ζi)是一个随机数加密后的密文。

执行过程如下:

• (1)每个协议参与者P i P_ {i}Pi选择z i z_ {i}zi。P i P_{i}Pi 对选择的z i z_{i}zi公布一个Pedersen承诺，C i = g z i h r i C_{i}=g^{z_i}h^{r_i}Ci=gzihri，其中r i ∈ Z q r_{i} \in Z_{q}ri∈Zq，h hh是Z q Z_{q}Zq的一个生产元，log ⁡ g h \log_{g}hloggh对所有的参与者都是未知的。
• (2)每个P i P_ {i}Pi计算( ε i , ζ i ) = ( ε z i , ζ z i ) (\varepsilon_ {i}, \zeta_ {i}) = (\varepsilon^{z_{i}},\zeta^{z_{i}})(εi,ζi)=(εzi,ζzi),然后广播( ε i , ζ i ) (\varepsilon_ {i}, \zeta_ {i})(εi,ζi)。
• (3)每个P i P_ {i}Pi向其他参与者证明( ε i , ζ i ) (\varepsilon_ {i}, \zeta_{i})(εi,ζi)是与C i C_{i}Ci 相关的并且是正确计算的。需要使用零知识证明协议证明他知道一个二元组( z i , r i ) (z_ {i}, r_{i})(zi,ri)，使得C i = g z i h r i C_{i}=g^{z_i}h^{r_i}Ci=gzihri ,并且 ε i = ε z i , ζ i = ζ z i \varepsilon_{i}=\varepsilon ^ {z_ {i}},\zeta_{i}=\zeta^{z_i}εi=εzi,ζi=ζzi。
• (4)协议的参与者共同计算( γ , δ ) = ( ∏ n i = 1 ε i , ∏ n i = 1 ζ i (\gamma,\delta)=(\prod^{i=1}_{n}\varepsilon_ {i}, \prod^{i=1}_{n}\zeta_{i}(γ,δ)=(∏ni=1εi,∏ni=1ζi，并解密( γ , δ ) (\gamma,\delta)(γ,δ)。
• (5)如果解密结果是1 11，则( α , β ) ≡ ( α ′ , β ′ ) (\alpha, \beta)\equiv(\alpha',\beta')(α,β)≡(α′,β′)；如果解密结果不为1 11，则( α , β ) ≠ ( α ′ , β ′ ) (\alpha, \beta)\neq (\alpha',\beta')(α,β)=(α′,β′)。

3. Mix-Match协议

使用B i = { b i 1 , b i 2 , ⋯   , b i k } B_{i}=\{b_{i1},b_{i2},\cdots,b_ {ik}\}Bi={bi1,bi2,⋯,bik}表示参与者P i P_{i}Pi的输入，基于Mix-Match的安全多方计算协议目标就是正确计算

f ( B 1 , B 2 , ⋯   , B n ) f(B_{1}, B_ {2},\cdots,B_{n})f(B1,B2,⋯,Bn)，同时保证P i P_{i}Pi的输入B i B_{i}Bi的保密性。

执行步骤如下：

（1）构建门电路

计算之前，所有协议的参与者将需计算的函数f ff用一个由若干门电路组成的单向图C f C_fCf来表示。假设C f C_{f}Cf由N NN个门电路组成，记作 G 1 , G 2 , ⋯   , G N G_ {1},G_{2},\cdots, G_{N}G1,G2,⋯,GN 。不失一般性，假设每个门电路G i + 1 G_{i+1}Gi+1都比G i G_{i}Gi深，也就是说每个门电路的计算应该按照顺序从G 1 G_{1}G1到G N G_{N}GN，G N G_{N}GN的输出就是整个电路C f C_{f}Cf的输出。

（2）生成逻辑表

为描述简单起见，假定所有的门电路G i G_{i}Gi都只有两个输入值，一个输出值，并且输入值和输出值都可以用一个位来表示。

使用逻辑表T i T_{i}Ti 表示C f C_{f}Cf中的门电路G i G_{i}Gi，由于假定G i G_{i}Gi都是二进制的门电路，则T i T_{i}Ti是一个4行3列的表。例如，G i G_{i}Gi是一个AND门，则T i T_{i}Ti如下表所示。

可以看出，T i T_{i}Ti为一个标准的真值表，包含所有可能的输入与输出。T i ( u , v ) T_{i}(u,v)Ti(u,v)表示逻辑表 T i T_{i}Ti的u uu行v vv列的值。

（3）输入阶段

所有协议参与者中使用秘密分享方案分享系统的私钥，系统的公钥是公开的。协议参与者P i P_iPi将自己的输入B i B_iBi使用公钥随机加密（如ElGamal加密方案），广播加密结果(或贴上公告牌)。

（4）混合阶段（Mix）

使用MN对T i T_{i}Ti进行混合，隐秘，随机置换。经过MN作用后，输出盲表T 1 ˉ , T 2 ˉ , ⋯   , T N ˉ \bar{T_{1}},\bar{T_{2}},\cdots,\bar{T_{N}}T1ˉ,T2ˉ,⋯,TNˉ。T i ˉ \bar{T_{i}}Tiˉ表示经过MN混合网络加密、隐秘、随机置换后的逻辑盲表(只有随机行置换，列的顺序不变)。

（5）匹配阶段（Match）

每个协议参与者使用PET协议将加密的输入与混合后的逻辑表进行比较，即查表。和普通的查表不一样的地方在于，Match比较的是密文，所以要使用PET协议，查完一个盲表即是计算了一个门电路，每个参与者依次计算所有的门电路即可得到函数的输出，这个输出也是加密的。

对于组成C f C_{f}Cf的门电路G 1 , G 2 , ⋯   , G N G_{1},G_ {2},\cdots,G_ {N}G1,G2,⋯,GN，协议的每个参与者P i P_{i}Pi独立的进行如下计算：假设l i l_{i}li和r i r_{i}ri分别表示G i G_{i}Gi输入的密文，P i P_{i}Pi使用PET协议对二元组( l i , r i ) (l_{i},r_{i})(li,ri)和T i ˉ \bar{T_{i}}Tiˉ中的每一行的前两项进行比较。

如果P E T ( l i , T i ˉ [ u , 1 ] ) = 1 PET(l_{i},\bar{T_{i}}[u,1])=1PET(li,Tiˉ[u,1])=1且P E T ( r i , T i ˉ [ u , 2 ] ) = 1 PET(r_{i},\bar{T_{i}}[u,2])=1PET(ri,Tiˉ[u,2])=1，则 G i G_{i}Gi的输出应该是T i ˉ [ u , 3 ] \bar{T_{i}}[u,3]Tiˉ[u,3]。P i P_{i}Pi分别对u = 1 , 2 , 3 , ⋯ u=1,2,3,\cdotsu=1,2,3,⋯进行比较,直到发现匹配的一行为止。

（6）输出阶段

计算完G N G_{N}GN后，P i P_{i}Pi得到了O N O_{N}ON，即G N G_{N}GN的输出，这个输出结果也是f ff的输出结果。所有协议的参与者P i P_{i}Pi共同解密O N O_{N}ON，即可得到正确的计算结果。

如果参与者P i P_{i}Pi提供了错误的输入，即该参与者所提供的输入密文不对应任何一个有效的位，则匹配一个T i ˉ \bar{T_{i}}Tiˉ就会找不到匹配的行，由此可发现P i P_{i}Pi提供了错误的输入。其他参与者发现P i P_{i}Pi有欺诈行为后，可将P i P_{i}Pi驱逐出协议的执行，有正确性行协议的参与者一起重新执行协议。Mix-Match 协议的安全性在很大程度上依赖于混合网络的安全性。

Mix-Match协议可以比较容易地扩展到非二进制门电路的形式，如果G i G_{i}Gi有j jj个输入，则G i G_{i}Gi对应的逻辑表的输人部分也有j jj列，相应的， T i T_{i}Ti应该有2 j 2^{j}2j行。如果G i G_{i}Gi需要不止一个输出，则扩展G i G_{i}Gi对应的逻辑表T i T_{i}Ti，使T i T_{i}Ti的输出部分具有多个值即可。如果 C f C_{f}Cf需要多个值的输出，则只需简单地将最后的若干门电路G N − k ′ , G N − k + 1 ′ , … , G N G_{N-k^{\prime}},G_{N-k+1'}, \ldots, G_{N}GN−k′,GN−k+1′,…,GN的输出作为C f C_{f}Cf的输出，在输出阶段进行多次共同解密即可。

使用Mix-Match的协议所需要传输的信息量较少，广播传输的信息量是O ( n N ) Ο(nN)O(nN)，其中n nn是协议参与者的数量，N NN是需要计算的函数被表示为门电路之后电路中门的数量。

4. 百万富翁问题的Mix-Match解决方案

问题描述

Alice拥有财富为A，Bob拥有财富为B，其中A = a 1 a 2 , B = b 1 b 2 A=a_1a_2,B=b_1b_2A=a1a2,B=b1b2，Alice与Bob需要在不泄露A , B A,BA,B的前提下，计算F ( A , B ) F(A,B)F(A,B)。F ( A , B ) = { 0        i f    A = B 1        i f    A > B 2        i f    A < B F(A,B)= \begin{cases} 0 \;\;\; if \; A=B \\ \\1 \;\;\; if \; A>B \\ \\2 \;\;\; if \; A<B \end{cases}F(A,B)=⎩⎨⎧0ifA=B1ifA>B2ifA<B

（1）构建门电路

F ( A , B ) F(A,B)F(A,B)可以通过包含3个门G 1 , G 2 , G 3 G_1,G_2,G_3G1,G2,G3的两层门电路来构造。其中G 1 , G 2 G_1,G_2G1,G2构成第一层，G 1 G_1G1的输入为a 1 , b 1 a_1,b_1a1,b1，输出为o 1 o_1o1，G 2 G_2G2的输入为a 2 , b 2 a_2,b_2a2,b2，输出为o 2 o_2o2；G 3 G_3G3构成第二层，输入为o 1 , o 2 o_1,o_2o1,o2，输出为F ( A , B ) F(A,B)F(A,B)。

（2）生成逻辑表

为G 1 , G 2 , G 3 G_1,G_2,G_3G1,G2,G3生成逻辑表T 1 , T 2 , T 3 T_1,T_2,T_3T1,T2,T3（包含所有输入及对应输出），其中o 1 , o 2 o_1,o_2o1,o2的输出逻辑与F ( A , B ) F(A,B)F(A,B)一致。o i ( i = 1 , 2 ) = { 0        i f    a i = b i 1        i f    a i > b i 2        i f    a i < b i o_i(i=1,2) = \begin{cases} 0 \;\;\; if \; a_i=b_i \\ \\1 \;\;\; if \; a_i>b_i \\ \\2 \;\;\; if \; a_i<b_i \end{cases}oi(i=1,2)=⎩⎨⎧0ifai=bi1ifai>bi2ifai<bi针对逻辑表T 1 , T 2 , T 3 T_1,T_2,T_3T1,T2,T3，需要对其进行编码，确保每组输入都是被唯一定义的。编码规则如下：

如，针对G 1 G_1G1的输入a 1 = 0 , b 1 = 0 a_1=0,b_1=0a1=0,b1=0，对应表中的L i = 0 , R i = 0 L_i=0,R_i=0Li=0,Ri=0将会被分别编码为L i ′ = 1 , R i ′ = 4 {L_i}'=1,{R_i}'=4Li′=1,Ri′=4。因此针对a 1 = 0 , b 1 = 0 a_1=0,b_1=0a1=0,b1=0，将其转换为对应编码的乘积1 × 4 = 4 1\times 4 =41×4=4

（3）输入阶段

Alice与Bob使用秘密分享方案分享系统的私钥，系统的公钥是公开的。并将自己的输入A = a 1 a b , B = b 1 b 2 A=a_1a_b,B=b_1b_2A=a1ab,B=b1b2使用公钥随机加密，广播加密结果(或贴上公告牌)。

（4）混合阶段（Mix）

使用MN对T 1 , T 2 , T 3 T_{1},T_{2},T_{3}T1,T2,T3进行混合，隐秘，随机置换，输出盲表T 1 ˉ , T 2 ˉ , T N ˉ \bar{T_{1}},\bar{T_{2}},\bar{T_{N}}T1ˉ,T2ˉ,TNˉ。

（5）匹配阶段（Match）

Alice与Bob使用PET协议将加密的输入与混合后的逻辑表进行比较，依次计算所有的门电路，即得到对应的输出。

(6)输出阶段

Alice与Bob然后共同解密得到结果。