安全多方计算(Secure Multi-party Computation,SMC)是密码学领域中的热点研究内容,它为隐私保护的分布式合作计算提供了通用解决方案。作为SMC领域中的一个具体实例,隐私保护的集合交集(Private Set Intersection,PSI)计算能保证用户在不泄露自身私有集合信息的前提下获得用户间集合交集。随着云计算的兴起,越来越多用户把其集合信息保存在云服务器上,然后在云辅助下完成交集计算。但是,目前云环境下的很多PSI协议仍存在着:效率低下、存在安全隐患、无法提供自然安全的数据存储等问题。本文利用集合表示技术将集合运算问题转换成数学问题,然后结合伪随机函数和同态密码体制等密码学基础工具提出了适用于云环境的高效的隐私保护集合交集计算协议。首先,我们基于集合的多项式、点值对表示方式,将集合交集计算转换成多项式求解问题:将集合元素表示成多项式的根,计算其点值对向量,随机化点值对向量,然后将隐藏后的点值对向量发给云服务器。之后,结合伪随机函数、同态密码体制等密码学工具,设计了一个云环境下隐私保护的两方集合交集计算协议,同时在半诚实模型下给出协议严格的形式化安全性证明。接着,我们进一步结合哈希映射技术将两方协议优化,设计了优化方案,使两方协议运行时间减少数十倍,效率大幅度提升,同时在半诚实模型下给出哈希优化协议严格的形式化安全性证明。最后,我们利用GMP、NTL等C++库实现了这两个协议和类似协议,并进行性能和安全性分析对比。分析结果表明新协议具有以下优点:(a)提供了自然安全的数据存储;(b)无需安全信道,普通信道满足协议要求;(c)与其他类似协议相比,通信和计算复杂度均有较大改善,协议高效实用;(d)提供了详细且形式化的基于标准仿真模拟器的安全性证明。最后,为使协议适用范围更广泛,我们设计了一个云环境下隐私保护的多方集合交集计算协议,同时在半诚实模型下给出严格的形式化安全性证明,并在C++环境下实现了此协议和类似协议,然后进行性能和安全性分析对比,结果表明多方协议同样具有两方协议的优势,同时还具以下优点:协议拓展性更好因为集合交集计算更多的委托给服务器、更适合对大规模集合求交集。