1、安全多方计算的概念安全多方计算的概念 n安全多方计算（Secure Multi-Party Computation，SMPC）是一种协议，在这个协议中，一群人可在一起用一种特殊的方法计算含有许多变量的任何函数。这一群中的每个人都知道这个函数的值，但除了函数输出的明显东西外，没有人知道关于任何其他成员输入的任何信息。安全多方计算的概念安全多方计算的概念n(1)参与者安全多方计算协议的参与者的行为，决定了安全多方计算协议设计的难易程度，根据参与者在协议中的行为，我们将参与者分为三种类型：n诚实参与者 n半诚实参与者 n恶意参与者 安全多方计算的概念安全多方计算的概念n(2)变量n(3)攻击者根据攻
2、击者腐败的参与者的不同类型，攻击者可以分为两类：n1)被动攻击者n2)主动攻击者 n(4)网络条件安全多方计算的概念安全多方计算的概念n(5)通信信道n1)安全信道n2)非安全信道n3)未认证的信道安全多方计算模型 n安全多方计算一般分为两种模型：n半诚实模型如果所有参与者都是半诚实或诚实的，称此模型为半诚实模型。半诚实模型中的攻击者是被动的。n恶意模型在攻击者的腐败集中，有恶意参与者的模型称为恶意模型。即攻击者能完全控制腐败方的模型。恶意模型中的攻击者是主动的。n半诚实模型安全多方计算较恶意模型的安全多方计算要容易得多，大多数情况下，如果协议中有恶意行为，协议得不到正确结果。要保证在恶意模型
3、的计算中得到正确结果，需要使用较多的密码学技术。安全多方计算可行性 nn表示参与者总数，t表示腐败者总数n（1）如果t n/3，那么在点对点网络中，任何函数的安全多方协议都是可获得的。这个协议是完全公平和保证输出传递的，并且在协议中不需要任何设置假设。n（2）如果t j。n(6)Alice把这个结论告诉Bob。nBob在第(3)步中所作的验证完全是为了保证第(4)步产生的数列中没有任何一个数出现两次，否则，如果za=zb，Alice就将知道ai j b。“百万富翁百万富翁”协议协议n该协议有一个缺点：Alice在Bob之前就熟悉了计算的结果。没有什么能阻止她完成该协议直到第(5)步，然后在第(
4、6)步拒绝告诉Bob结果，甚至在第(6)步有可能对Bob撒谎。n当然，这个协议不能防止主动欺骗者。密码学家晚餐问题密码学家晚餐问题 nDavid Chaum提出了密码学家晚餐问题：三位密码学家正坐在他们最喜欢的三星级餐馆准备吃晚餐。侍者通知他们晚餐需匿名支付帐单。其中一个密码学家可能正在付帐，或者可能已由美国国家安全局NSA付过了。这三位密码学家都尊重彼此匿名付帐的权利，但他们要知道是不是NSA在付帐。n假设这三个密码学家分别叫Alice、Bob和Carol，他们怎样才能确定他们之中的一个正在付帐同时又要保护付帐者的匿名呢？密码学家晚餐问题密码学家晚餐问题n这个问题可以这样解决：每个密码学家在
5、他的菜单后，在他和他右边的密码学家之间抛掷一枚硬币，以致只有他们两个能看到结果。然后每个密码学家都大声说他能看到两枚梗币他抛的一个和他左手邻居抛的那个落下来是同一面还是不同的一面。如果有一个密码学家付帐，他就说所看到的相反的结果。在桌子上说不同的人数为奇数表明有一个密码学家在付帐；不同为偶数表明NSA在付帐（假设晚餐只付一次帐）。还有，如果一个密码学家在付帐，另两个人都不能从所说的话中得知关于那个密码学家付帐的任何事。密码学家晚餐问题密码学家晚餐问题nCrypt(i)（i=0,1,2）与Coin(i)（i=0,1,2）分别表示密码学家和硬币结果nCrypt(i)付款输出为 Coin(i 1)C
6、oin(i)1，没付款输出Coin(i 1)Coin(i)Crypt(0)Coin(0)Crypt(1)Coin(1)Crypt(2)Coin(2)密码学家晚餐问题密码学家晚餐问题n这个协议可以应用到匿名消息广播。这是一个无条件的发方和收方不可追踪性的例子。在网络上的一群用户可以用这个协议发送匿名报文。n（1）用户把他们自己排进一个逻辑圆圈。n（2）在一定的时间间隔内，相邻的每对用户对在他们之间抛掷硬币，使用一些公正的硬币抛掷协议防止窃听者。n（3）在每次抛掷之后每个用户说“相同”或“不同”。n这个协议的一个问题是虽然一个恶意的参与者不能读出报文，但他能通过在第（3）步中说谎来破坏系统。一般安
7、全多方计算结构(GMW)n考虑两方的情况nf 是参与者想要计算得到的函数n把 f 看成一个电路门运算，运算最终归结为GF(2)上的普通加法与乘法运算。n目标 逐个计算门,每次计算就得到一个随机共享随机共享示例na的一些值:nP 1 有随机值 a1nP 2 有 a+a1n注意：不知道a1,a+a1仅仅是一个随机值，不能获得的a任何信息，隐藏了a.n那么我们说，有关各方 随机共享 a.n所有中间值都是随机共享的。(没有泄露任何信息).电路计算 nStage 1:每一个参与方与其他方随机的共享他的输入。nStage 2:门电路的计算如下：n假设随机共享作为电路输入线，计算输出线nStage 3:连接
8、所有共享的输出线，得到真正的输出。加法n输入:nP1：a1，b1nP2：a2，b2n注意:a1+a2=a，b1+b2=bn计算随机共享的输出 c=a+bnP1 计算 c1=a1+b1nP2 计算 c2=a2+b2n注意:c1+c2=a1+a2+b1+b2=a+b=c乘法n输入:nP1：a1，b1nP2：a2，b2n要计算 c=ab=(a1+a2)(b1+b2)nP1知道具体的共享值 rnP1,不知道P2的值，但存在四种可能(这取决于通信 00,01,10,11)乘法nP1制表格如下:n列 1：P2的输入00n列 2：P2的输入01n列 3：P2的输入10n列 4：P2的输入11nr是由P1选择
9、的一个随机位n列1：ab+r 当 a2=0,b2=0n列2：ab+r 当 a2=0,b2=1n列3：ab+r 当 a2=1,b2=0n列4：ab+r 当 a2=1,b2=1例子n假设:a1=0,b1=1n假设:r=1列P2的共享输出1a2=0,b2=0(0+0).(1+0)+1=12a2=0,b2=1(0+0).(1+1)+1=13a2=1,b2=0(0+1).(1+0)+1=04a2=1,b2=1(0+1).(1+1)+1=1门协议n各参与方执行 1/4轮不经意传输协议 nP1 是发送者:消息 i 是列i.nP2 是接受者:它输入 1 如果a2=0且b2=0,2 如果 a2=0 且 b2=1,等 n输出:nP2 收到 c2=c+r 这个是他的输出nP1 输出 c1=rn注意:c1 和 c2 是 c的随机共享,根据需要。n每次都用这种方法计算门,最后各参与方 获得输出共享。n很简单就可以得到函数的输出只需要将共享发送给每一个参与者。
