基于秘密共享的理性安全多方计算的研究

通过对以往的基于秘密共享的理性安全多方计算协议的分析，指出了其中存在的一些问题，为了解决这些问题，本文重新设计了一种基于秘密共享的理性安全多方计算协议，通过在真实影子份额中随机的混入虚假影子份额，并且屏蔽掉参与者对于秘密分发阶段对于秘密多项式阶数等私密信息的了解，从而解决了之前协议所暴露出的问题。

多方安全计算指在一个参与者都不信赖彼此的环境中，每位参与者都通过网络来共同完成各种计算任务的同时又不会泄露自己的数据[1]。这里面的安全是说我们既能够通过计算得到正确的结果，又不会让别的参与者得知我们输入的各种隐私信息。多方安全计算在我们的生活中随处可见，尤其是在现在这个互联网时代，比如在网上的拍卖会，网络上的投票系统[2]等等。

借助博弈论思想，我们可以实现在传统的协议中很难实现的公平性。文献[3]提出了一个思想，当人们无法预测何时得到计算结果时，他们会非常乐于去遵循协议。Naor [4]等人为了使参与者严格的去遵守协议的约定，引入了博弈论的相关概念。但该方案设计比较复杂。在参考文献[5]中，Amjed 设计了一个引入博弈论的方案， 但是这个方案要求生成的多项式的幂次数之间的差值必须小于等于一， 具有局限性。

参考文献[6] [7]需要在我们使用的时候提供一些物理性的材料， 比如信件等， 不利于应用。

在参考文献[8]中，同时考虑了善意的参与者和具有攻击性的参与者，在这个基础上，设计出了一种新的理性安全多方计算的方案。

现有的基于秘密共享的理性安全多方计算协议的基本思路均为屏蔽掉参与者对于多轮数据交互中“最后一轮”的认识，使参与者不知道协议到底在第几轮结束，因为如果参与者知道协议在第几轮结束， 那么参与者完全可以在最后一轮中拒绝发送自己的影子份额，而会收到别的参与者的影子份额从而恢复出秘密，尽管别的参与者知道有参与者没有发出自己的影子份额，但是也已经晚了，因为那个参与者已经自己得到了秘密，因此根据反向递归原则，作为一个理性的参与者，他们从协议的第一轮开始就不会去执行这个协议。因此学者们提出了采用随机性策略的思想。将秘密重组过程重复很多轮，重复的次数是有限的但是参与者不知道协议要重复多少轮，其中，每一轮以一定概率是有意义的，只有在有意义的轮中才可以恢复出秘密，若在无意义的轮中背离，则协议将要终止，所有参与者都无法得到秘密。这一随机性，使得参与者由于无法判断当前轮是否能够得到秘密而不会去冒险背离，从而遵守协议，实现协议的公平性。

2. 背景知识 2.1. 传统的基于秘密共享多方安全计算模型 现有的基于秘密共享的多方安全计算模型一般是下面这种形式： 假设f ′ 是这样的一个函数：给定输入1, , nxx，计算()1, , nSf xx←。接着利用(), m n 秘密共享机制在参与者之间分享结果S， 即产生子份额1, , nss， 其中1, , nss可以通过某种运算计算出最终的结果S。

然后分发者构造多个秘密多项式( )1011titF xaa xax −−=+++，使( )0iiFs=。并产生多组影子份额队列( )()( )(){}( )()( )(){}111, 1 , , , , , 1, 1 , , , nnFn F nFn Fn， 分别将这些影子子份额队列发送给对应的参与者iP 。

参与者们通过不断的交换彼此的影子子份额恢复出彼此的秘密多项式从而获得秘密子份额，最终构造出