集合交集问题的安全计算

A Secure Multiparty Intersection Computation

安全多方计算是隐私保护的核心技术,也是密码学研究的热点.由于生活中很多问题可转化为对集合的运算,因此集合是安全多方计算研究的重要内容.现有对集合的运算包括保密计算集合的交(并)集、保密计算集合的势、保密判定元素与集合的关系、保密判定集合包含等.本文主要利用保密替换、加密选择、密码系统的加法同态性研究了三个新问题,分别为集合交(并)集的势与阈值关系的保密判定、元素与集合交(并)集关系的保密判定、集合与集合交(并)集关系的保密判定.首先,在数据范围已知情况下,将数据转化为数组进行计算,在计算过程中不泄露集合的交(并)集,只得到最终结果.同时,利用lifted ElGamal门限密码系统设计出抗合谋的安全协议.最后,利用模拟范例对协议的安全性进行证明.

Secure multi-party computation is not only a core privacy preserving technology,it is also a hot issue in the international cryptographic community.Set operation is a significant problem of secure multi-party computation because many problems can be transformed to set operation problems.The existing secure set operation solutions include secure intersection(union)computation,secure intersection cardinality computation,secure determination of the relationship between an element and a set,secure set inclusion determination etc.This paper addresses three new problems by using private substitution,encryption selection and additive homomorphism of encryption system.These problems can be used to securely determine the relationship between a threshold and the cardinality of intersection(union)of private sets,securely determine the relationship between an element and the intersection(union)of private sets,and securely determine the relationship between a set and the intersection(union)of private sets.When the data range is known,the data is encoded to an array to perform secure computation without disclosing the intersection(union)of the private sets.Meanwhile,the threshold lifted ElGamal cryptosystem can be used to resist collusion attacks.It is proved that,by using the simulation paradigm,the designed protocols are secure in the semi-honest model.