高效且恶意安全的三方小集合隐私交集计算协议

Efficient and Malicious Secure Three-Party Private Set Intersection Computation Protocols for Small Sets

隐私集合交集(private set intersection, PSI)允许持有私有集合的参与方安全地获得集合的交集,而不会泄露除交集之外任何元素的信息.现有的两方/多方PSI协议大多基于不经意传输(oblivious transfer, OT)协议,具有很高计算效率的同时,也带来了巨大通信开销.在很多场景中,扩展网络带宽是非常昂贵甚至不可行的,而目前不依赖于OT设计且计算高效的多方PSI协议仍然较少.基于一轮密钥协商构造了三方参与的PSI计算协议,分别在半诚实模型和恶意安全性模型下,证明了协议的安全性且允许任意两方的合谋攻击.通过实验仿真,在大集合场景,相比现有基于OT的多方PSI协议,所构造的协议具有最优的通信轮数且通信量降低了89%~98%;在小集合场景(500个元素或更少),相比适用弱通信网络的同类PSI协议,具有最优运行时间和通信负载,比依赖于同态加密的PSI协议快10~25倍.

Private set intersection(PSI) allows participants who hold private sets to securely obtain the set intersection without revealing information about any elements other than the intersection. Most of the existing two-party/multi-party PSI protocols are based on the oblivious transfer(OT) protocol, which not only has high efficiency, but also brings huge cost of communication. However, expanding network bandwidth is very expensive or even infeasible in many scenarios, and there are few computationally efficient multi-party PSI protocols that do not rely on OT protocols. In this paper, three-party private set intersection computing protocols are constructed based on one round key agreement. The protocols are proved secure assuming the collusion attack of any two parties in the semi-honest model and malicious model, respectively. Through experimental simulation, in the large set scenario, compared with the existing OT-based multi-party PSI protocol, the three-party private set intersection computation protocols have the optimal number of communication rounds, and the amounts of communication is reduced by 89%~98%. In small set scenarios(500 items or less), compared with similar PSI protocols for weak communication networks, the protocols in our paper have optimal runtime and communication load, especially, and they get 10~25 times faster than PSI protocol relying on homomorphic encryption.