基于多项式表示的集合问题安全计算协议

针对集合问题安全计算方案在实际应用中的低效率及存在安全漏洞等问题，利用多项式表示技术将集合问题转化为多项式求值问题，结合离散对数问题提出了集合成员关系以及集合交集问题的安全两方计算协议。首先，从最近一个高效的集合成员关系计算协议的安全缺陷出发，分析存在的安全漏洞是在一定条件下可以通过穷举攻击获得参与方输入的元素信息，导致参与方的隐私信息得不到保障。为克服该安全漏洞，将集合表示为多项式，并对多项式进行随机化，以确保参与方交互过程中不会发生任何泄漏；然后，结合离散对数问题，提出了安全的集合成员关系计算协议。该协议能够快速判断输入的元素是否属于一个集合，并且除了集合的势，没有泄露参与双方的任何其他信息。接着，将完善后的集合成员关系计算协议进一步扩展，提出了能够解决集合交集问题的安全两方计算协议。利用该协议，互不信任的参与方能有效计算集合的交集，而不泄露自身的隐私信息。最后，在半诚实模型下，结合概率多项式时间模拟器，给出了两个协议的安全性证明，证明了模拟器视图与原协议执行视图在计算上无法区分；详细分析了本文协议的性能，结果表明提出的集合成员关系计算协议及集合交集安全计算协议比其他相关协议效率更高，具有较小的通信复杂度及计算复杂度。

Secure Computation Protocols for Set Operations Based on Polynomial Representation of Sets

In order to improve efficiency and solve the security vulnerabilities of the secure set computation protocols in practical applications, two secure two-party protocols for set membership and set intersection were proposed based on discrete logarithm problem and the polynomial representation of sets with which the set operation problem could be transformed into a polynomial evaluation problem. Firstly, a latest efficient secure set membership protocol was analyzed, and a security vulnerability of leaking the privacy of the participants by obtaining the element of participants on the brute attack was found. To overcome the security vulnerability, a new method was introduced by representing sets by polynomials and randomizing the polynomials, which could ensure the security of the participants without any leakage of interactions. Based on the discrete logarithm problem and the new method, a new secure set membership protocol was presented. The protocol could judge set-element membership with high-efficiency, and did not leak any other information about the participants besides the size of the set. Further, a secure set intersection protocol was showed according to the same technique. The security proofs of both protocols were given under the semi-honest model by using the probability polynomial time simulator, which indicated that the simulator views were computationally indistinguishable from the original protocols'' execution views. Finally, the detailed analysis about the protocols'' performance was presented, showing that both protocols were more efficient than other protocols since their communication complexity and computational complexity were smaller.