复数域上的隐私保护集合交集势计算

安全多方计算是密码学领域的研究热点，集合交集问题是其重要研究方向之一。由于现实中众多应用场景可以抽象成数学上的集合关系计算，故集合保密计算具有重要的实际意义。整数环上的集合交集保密计算目前已存在较多研究成果，但针对复数域上集合交集保密计算的研究却很少。本文主要研究复数域上的集合保密计算问题。由于复数上的集合交集计算与整数上的集合交集计算存在差异，故本文引入代数计算中的结式来解决该问题。首先使用牛顿公式来构造复数域上的多项式，再将保护隐私的两方求解集合交集势问题转化为安全两方求解结式中参变元最低次数问题。最后，利用随机哈希和西尔维斯特结式的性质降低计算开销。

安全多方计算(Secure Multi-Party Computation, SMC)指的是在不泄露各方私有数据的前提下， 正确完成需要各方合作计算的函数值。安全多方计算问题是由姚期智在1982 年提出的[1]。后来，Goldreich 对该问题进行了研究[2] [3]，证明一般的安全多方计算问题是可解的，并给出了解决方案。但是同时，他也指出这些具有一般性的理论在很多情况下由于效率低下无法应用在实际中，而应该根据研究问题的不同设计不同的解决方案。

隐私保护集合交集(Private Set Intersection, PSI)计算是安全多方计算领域的一个重要研究方向。它指的是各自拥有集合的多方协议参与者希望保密计算出这些集合之间的关系，如集合交集、交集势[4]-[10]和并集、并集势[11] [12] [13]等计算问题。

随着社会的发展， 人们对个人数据安全越来越重视， 隐私保护集合交集计算也随之受到更多的关注、被应用在更多的现实场景中。如：在商业应用场景中，APP 想要通过用户手机通讯录中的联系人信息了解到这些人中曾经多少人下载并使用过本APP， 这需要计算通讯录联系人与APP 服务器数据库中用户信息的交集势。为了保护用户隐私，APP 不可以将用户手机通讯录中的联系人信息进行上传，故需要寻求一种能够在不泄露用户联系人信息的情况下，计算出该交集势的方法。

由于隐私保护集合交集计算受到越来越多的关注，一些学者也提出了自己的解决方案。这些方案大致可以分为以下几类。

第一类是基于公钥加密体系的PSI。2002 年，Clifton 等人在文献[14]中使用可交换加密算法Pohlig-Hellman [15]对协议双方集合元素均加密两次， 将问题转化为集合元素匹配问题。

2004 年， Freedman等人在文献[6] [16]利用插值法将原集合元素作为根构造出多项式，将集合交集问题转化为对方集合元素是否为多项式的根的问题，在此基础上，利用Paillier [17]或El Gamal [18]同态加密算法对多项式系数加密，从而求解集合的交、集合交集势等问题。2005 年，Kissner 等人在文献[19]中根据集合元素构造多项式，使用门限同态加密方法求解集合交集、并集势和集合包含问题，但由于使用门限解密，导致计算量