摘要: 安全计算的概念是在1982 年由Yao 提出的，最初只是针对安全两方计算问题，后来由Goldreich, Micali，和Winderson 推广到安全多方计算问题。安全多方计算研究的是如何在互不信任的成员中进行交互，使得成员在不泄漏自己的秘密信息的情况下，计算一个关于所有成员秘密输入的公开函数，每个成员得到一个正确的计算结果。假设成员都相信一个可信机构，计算任务就变得简单了：每个成员都把自己的秘密输入提交给可信机构，可信机构计算函数值，把结果分发给各个成员。很显然，这样的计算保证了每个成员都得到了正确的计算结果，并且除了计算结果之外，不能获得任何关于其他人秘密输入的信息。安全多方计算协议就相当于实现了一个可信机构的功能。安全多方计算问题中有一些比较有实用价值的特殊问题，比如比较大小问题，可以用于电子竞价，电子拍卖等，还有集合交集，集合并集等相关问题，可以用于秘密保持的数据挖掘，含有敏感信息的医学数据库访问等。受到多方集合交集问题的启发，提出了一种新的秘密集合运算。假设网络中有n 个成员，每个成员有一个秘密集合。假设其中一个成员P 是领导，t（小于n-1）是一个阈值。对于P的集合S 中的每一个元素w，如果w 在其余成员的集合中出现多于t 次，则P 知道w 出现在哪些成员的集合中，如果w 在其余成员的集合中出现的次数小于等于t 次，则P 不能知道其他任何人的集合中是否包含w。这个问题可以看作是集合交集的一般化，当t=n-2 时，上述集合运算等价于求n 个集合的交集。安全多方计算的研究表明，存在一般化的安全协议，可以安全计算任何多方计算问题。因此，所提出的集合运算问题也可以用一般协议来解决，然而一般的协议都是基于布尔或数学电路的，侧重解决方法的一般性，不能很好地兼顾效率，因此有必要设计专门的协议解决具体的集合运算问题。此外，已有的多集门限并集协议和多集交集协议可组合起来解决所提出的问题，然而这样的解决方案需要的通信轮数与n 成正比，在分布式网络环境中，发送和接受消息是比较耗费时间的，因此，设计常数通信轮数的协议是很有意义的。对于阈值范围为2(n-1)/3 < t