Mix-Match
M.Jakobsson和A.Juels提出了基于Mix-Match的安全多方计算协议构造方法，该类协议包括Mix与Match两个阶段：
- Mix阶段：通过构造混合网络，生成盲表（Blinded table）
- Match阶段：通过执行PET协议进行查表，得到对应的输出
最后参与者共同解密输出，该类协议参与者之间所需传输的消息量较少，对于逻辑运算和Bit运算较为高效。
1. 混合网络
从直观上讲，混合网络是一个多方协议，协议的输入是一个密文表，该密文表中的密文与一组明文有着一一对应的关系。协议将这个密文表随机置换后得到另外一个密文表，输出的密文表和相同的一组明文也是一一对应的。即输出的密文表是输入密文表的随机置换。
混合网络的安全性在于攻击者无法确定输出密文表中的某一条密文与输入密文表中的哪一条密文是对应的。
基于ElGamal加密方案的混合网络
假定参与混合网络的
nnn个参与者都共享一个具备身份认证的广播信道（或存在一个公告板），将一个ElGamal加密方案的公钥yyy公布给每个参与者。由参与者集合PPP的某一个子集充当混合服务器（Mix Server）的角色，与yyy对应的私钥使用(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σ 表示在kkk个元素上的随机置换。
2. PET协议
假设
(α,β)(\alpha,\beta)(α,β) 和(α′,β′)(\alpha',\beta')(α′,β′)分别表示m1,m2m_{1},m_{2}m1,m2 使用ElGamal加密方案加密后的密文，参与相同明文测试协议的参与者在不解密的情况下通过执行协议判断(α,β)(\alpha,\beta)(α,β)和(α′,β′)(\alpha',\beta')(α′,β′)所对应的明文是否相同。
考虑密文
(ε,ζ)=(α/α′,β/β′)(\varepsilon,\zeta) = (\alpha/\alpha',\beta/\beta')(ε,ζ)=(α/α′,β/β′)，如果(α,β)≡(α′,β′)(\alpha, \beta)\equiv(\alpha',\beta')(α,β)≡(α′,β′)，则(ε,ζ)( \varepsilon, \zeta)(ε,ζ) 表示明文111加密后的密文。
PET（Plaintext Equivalence Test） 协议的基本思路是让协议的参与者
PiP_{i}Pi使用如下的方法隐藏(ε,ζ)(\varepsilon, \zeta)(ε,ζ):PiP_{i}Pi选择zi∈Zqz_{i} \in Z_{q}zi∈Zq ,然后计算(εi,ζi)=(εzi,ζzi)(\varepsilon_ {i}, \zeta_ {i}) = (\varepsilon^{z_{i}},\zeta^{z_{i}})(εi,ζi)=(εzi,ζzi)
- 如果 ( α , β ) ≡ ( α ′ , β ′ ) (\alpha, \beta)\equiv(\alpha',\beta') (α,β)≡(α′,β′)， ( ε , ζ ) (\varepsilon, \zeta) (ε,ζ)代表 1 1 1加密后的密文，则 ( ε i , ζ i ) (\varepsilon_ {i}, \zeta_ {i}) (εi,ζi)仍是 1 1 1加密后的密文
- 如果 ( α , β ) ≠ ( α ′ , β ′ ) (\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 h h是 Z q Z_{q} Zq的一个生产元， log g h \log_{g}h loggh对所有的参与者都是未知的。
- (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 1 1，则 ( α , β ) ≡ ( α ′ , β ′ ) (\alpha, \beta)\equiv(\alpha',\beta') (α,β)≡(α′,β′)；如果解密结果不为 1 1 1，则 ( α , β ) ≠ ( α ′ , β ′ ) (\alpha, \beta)\neq (\alpha',\beta') (α,β)=(α′,β′)。
3. Mix-Match协议
使用
Bi={bi1,bi2,⋯,bik}B_{i}=\{b_{i1},b_{i2},\cdots,b_ {ik}\}Bi={bi1,bi2,⋯,bik}表示参与者PiP_{i}Pi的输入，基于Mix-Match的安全多方计算协议目标就是正确计算f(B1,B2,⋯,Bn)f(B_{1}, B_ {2},\cdots,B_{n})f(B1,B2,⋯,Bn)，同时保证PiP_{i}Pi的输入BiB_{i}Bi的保密性。
执行步骤如下：
（1）构建门电路
计算之前，所有协议的参与者将需计算的函数
fff用一个由若干门电路组成的单向图CfC_fCf来表示。假设CfC_{f}Cf由NNN个门电路组成，记作G1,G2,⋯,GNG_ {1},G_{2},\cdots, G_{N}G1,G2,⋯,GN 。不失一般性，假设每个门电路Gi+1G_{i+1}Gi+1都比GiG_{i}Gi深，也就是说每个门电路的计算应该按照顺序从G1G_{1}G1到GNG_{N}GN，GNG_{N}GN的输出就是整个电路CfC_{f}Cf的输出。
（2）生成逻辑表
为描述简单起见，假定所有的门电路
GiG_{i}Gi都只有两个输入值，一个输出值，并且输入值和输出值都可以用一个位来表示。
使用逻辑表
TiT_{i}Ti 表示CfC_{f}Cf中的门电路GiG_{i}Gi，由于假定GiG_{i}Gi都是二进制的门电路，则TiT_{i}Ti是一个4行3列的表。例如，GiG_{i}Gi是一个AND门，则TiT_{i}Ti如下表所示。
左输入右输入输出000010100111
可以看出，
TiT_{i}Ti为一个标准的真值表，包含所有可能的输入与输出。Ti(u,v)T_{i}(u,v)Ti(u,v)表示逻辑表TiT_{i}Ti的uuu行vvv列的值。
（3）输入阶段
所有协议参与者中使用秘密分享方案分享系统的私钥，系统的公钥是公开的。协议参与者
PiP_iPi将自己的输入BiB_iBi使用公钥随机加密（如ElGamal加密方案），广播加密结果(或贴上公告牌)。
（4）混合阶段（Mix）
使用MN对
TiT_{i}Ti进行混合，隐秘，随机置换。经过MN作用后，输出盲表T1ˉ,T2ˉ,⋯,TNˉ\bar{T_{1}},\bar{T_{2}},\cdots,\bar{T_{N}}T1ˉ,T2ˉ,⋯,TNˉ。Tiˉ\bar{T_{i}}Tiˉ表示经过MN混合网络加密、隐秘、随机置换后的逻辑盲表(只有随机行置换，列的顺序不变)。
（5）匹配阶段（Match）
每个协议参与者使用PET协议将加密的输入与混合后的逻辑表进行比较，即查表。和普通的查表不一样的地方在于，Match比较的是密文，所以要使用PET协议，查完一个盲表即是计算了一个门电路，每个参与者依次计算所有的门电路即可得到函数的输出，这个输出也是加密的。
对于组成
CfC_{f}Cf的门电路G1,G2,⋯,GNG_{1},G_ {2},\cdots,G_ {N}G1,G2,⋯,GN，协议的每个参与者PiP_{i}Pi独立的进行如下计算：假设lil_{i}li和rir_{i}ri分别表示GiG_{i}Gi输入的密文，PiP_{i}Pi使用PET协议对二元组(li,ri)(l_{i},r_{i})(li,ri)和Tiˉ\bar{T_{i}}Tiˉ中的每一行的前两项进行比较。
如果
PET(li,Tiˉ[u,1])=1PET(l_{i},\bar{T_{i}}[u,1])=1PET(li,Tiˉ[u,1])=1且PET(ri,Tiˉ[u,2])=1PET(r_{i},\bar{T_{i}}[u,2])=1PET(ri,Tiˉ[u,2])=1，则GiG_{i}Gi的输出应该是Tiˉ[u,3]\bar{T_{i}}[u,3]Tiˉ[u,3]。PiP_{i}Pi分别对u=1,2,3,⋯u=1,2,3,\cdotsu=1,2,3,⋯进行比较,直到发现匹配的一行为止。
（6）输出阶段
计算完
GNG_{N}GN后，PiP_{i}Pi得到了ONO_{N}ON，即GNG_{N}GN的输出，这个输出结果也是fff的输出结果。所有协议的参与者PiP_{i}Pi共同解密ONO_{N}ON，即可得到正确的计算结果。
如果参与者
PiP_{i}Pi提供了错误的输入，即该参与者所提供的输入密文不对应任何一个有效的位，则匹配一个Tiˉ\bar{T_{i}}Tiˉ就会找不到匹配的行，由此可发现PiP_{i}Pi提供了错误的输入。其他参与者发现PiP_{i}Pi有欺诈行为后，可将PiP_{i}Pi驱逐出协议的执行，有正确性行协议的参与者一起重新执行协议。Mix-Match 协议的安全性在很大程度上依赖于混合网络的安全性。
Mix-Match协议可以比较容易地扩展到非二进制门电路的形式，如果
GiG_{i}Gi有jjj个输入，则GiG_{i}Gi对应的逻辑表的输人部分也有jjj列，相应的，TiT_{i}Ti应该有2j2^{j}2j行。如果GiG_{i}Gi需要不止一个输出，则扩展GiG_{i}Gi对应的逻辑表TiT_{i}Ti，使TiT_{i}Ti的输出部分具有多个值即可。如果CfC_{f}Cf需要多个值的输出，则只需简单地将最后的若干门电路GN−k′,GN−k+1′,…,GNG_{N-k^{\prime}},G_{N-k+1'}, \ldots, G_{N}GN−k′,GN−k+1′,…,GN的输出作为CfC_{f}Cf的输出，在输出阶段进行多次共同解密即可。
使用Mix-Match的协议所需要传输的信息量较少，广播传输的信息量是
O(nN)Ο(nN)O(nN)，其中nnn是协议参与者的数量，NNN是需要计算的函数被表示为门电路之后电路中门的数量。
4. 百万富翁问题的Mix-Match解决方案
问题描述
Alice拥有财富为A，Bob拥有财富为B，其中
A=a1a2,B=b1b2A=a_1a_2,B=b_1b_2A=a1a2,B=b1b2，Alice与Bob需要在不泄露A,BA,BA,B的前提下，计算F(A,B)F(A,B)F(A,B)。F(A,B)={0ifA=B1ifA>B2ifA<BF(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个门G1,G2,G3G_1,G_2,G_3G1,G2,G3的两层门电路来构造。其中G1,G2G_1,G_2G1,G2构成第一层，G1G_1G1的输入为a1,b1a_1,b_1a1,b1，输出为o1o_1o1，G2G_2G2的输入为a2,b2a_2,b_2a2,b2，输出为o2o_2o2；G3G_3G3构成第二层，输入为o1,o2o_1,o_2o1,o2，输出为F(A,B)F(A,B)F(A,B)。
（2）生成逻辑表
为
G1,G2,G3G_1,G_2,G_3G1,G2,G3生成逻辑表T1,T2,T3T_1,T_2,T_3T1,T2,T3（包含所有输入及对应输出），其中o1,o2o_1,o_2o1,o2的输出逻辑与F(A,B)F(A,B)F(A,B)一致。oi(i=1,2)={0ifai=bi1ifai>bi2ifai<bio_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针对逻辑表T1,T2,T3T_1,T_2,T_3T1,T2,T3，需要对其进行编码，确保每组输入都是被唯一定义的。编码规则如下：LiL_iLiLi′{L_i}'Li′RiR_iRiRi′{R_i}'Ri′F(A,B)F(A,B)F(A,B)e(F(A,B))e(F(A,B))e(F(A,B))010407121518232629
如，针对
G1G_1G1的输入a1=0,b1=0a_1=0,b_1=0a1=0,b1=0，对应表中的Li=0,Ri=0L_i=0,R_i=0Li=0,Ri=0将会被分别编码为Li′=1,Ri′=4{L_i}'=1,{R_i}'=4Li′=1,Ri′=4。因此针对a1=0,b1=0a_1=0,b_1=0a1=0,b1=0，将其转换为对应编码的乘积1×4=41\times 4 =41×4=4
（3）输入阶段
Alice与Bob使用秘密分享方案分享系统的私钥，系统的公钥是公开的。并将自己的输入
A=a1ab,B=b1b2A=a_1a_b,B=b_1b_2A=a1ab,B=b1b2使用公钥随机加密，广播加密结果(或贴上公告牌)。
（4）混合阶段（Mix）
使用MN对
T1,T2,T3T_{1},T_{2},T_{3}T1,T2,T3进行混合，隐秘，随机置换，输出盲表T1ˉ,T2ˉ,TNˉ\bar{T_{1}},\bar{T_{2}},\bar{T_{N}}T1ˉ,T2ˉ,TNˉ。
（5）匹配阶段（Match）
Alice与Bob使用PET协议将加密的输入与混合后的逻辑表进行比较，依次计算所有的门电路，即得到对应的输出。
(6)输出阶段
Alice与Bob然后共同解密得到结果。
本文转载自: https://blog.csdn.net/apr15/article/details/129801364
版权归原作者 机器学习Zero 所有， 如有侵权，请联系我们删除。
版权归原作者 机器学习Zero 所有， 如有侵权，请联系我们删除。