集合相交问题的双方保密计算

Secure Two-Party Computation for Set Intersection Problem

用公开密钥加密算法解决了集合相交的多方保密计算问题,并提出了3种解决方案,它们均基于参与保密比较的双方都是半诚实的.所提方案既可以使双方知道集合的交集,也可以使双方只知道交集的势,而不知道具体的交集,同时运用模拟范例证明了解决方案的保密性.该方案适用于不暴露交集的元素、向一方暴露交集的元素、向双方暴露交集的元素等3种场合,且计算复杂度较低,可以容易地推广到保密计算的多个集合相交的问题,在网络隐私保护方面具有重要的应用价值.

Applying public key cryptography to the secure multi-party computation for set intersection problem, three solutions are proposed based on the assumption that both parties partici- pating the secure multi-party computation are semi-honest. By these solutions, both parties are able to know the intersection set or the cardinality of it without knowing the concrete intersection set. The privacy preserving property of these solutions is proved by simulation paradigm. These solutions are suitable for the cases in which the elements of the intersection set are kept secret, exposed to one party, or to both parties. The proposed methods have lower computational complexity and can easily be generalized to the multi-set intersection problem. They are significant in Internet privacy preserving.