抗恶意敌手的线性门限隐私集合交集协议

Linear threshold private set intersection against malicious adversaries

门限隐私集合交集(TPSI)是安全多方计算中的一种特例,其在机器学习、共享拼车、指纹识别等多个领域有广泛的应用。然而,目前存在的方案均基于计算复杂度较高的算法,并且仅在半诚实模型下实现,导致协议计算开销较大且无法抵抗恶意敌手的攻击。为了解决以上问题,首先提出了一个向量不经意匹配测试(VOMT)协议,并基于VOMT和布谷鸟哈希设计了一个高效的半诚实TPSI协议。此外,结合VOMT与对称密钥加密方案构造出向量不经意解密匹配测试(VODMT)协议,并基于VODMT与不经意伪随机函数设计了一个可以抵抗恶意敌手的TPSI协议。随后,分别在半诚实模型和恶意模型下证明了协议的安全性,并分析得出两个协议的计算复杂度和通信复杂度均为线性。在集合大小为4096时,提出的两个协议的在线运行时间分别为0.81 s和1.81 s,而先前的工作则需要5627 s,所以两个协议均是高效的。

Threshold private set intersection(TPSI)is a special case of secure multi-party computation,which is widely used in many fields such as machine learning,ride-sharing,and fingerprint recognition.However,currently existing solutions are all based on algorithms with high computational complexity and are only implemented under a semi-honest model,resulting in high computational overhead and inability to resist attacks by malicious adversaries.In order to solve the above problems,this paper first proposed a vector oblivious match test(VOMT)protocol and designed an efficient semi-honest TPSI protocol based on VOMT and cuckoo hashing.In addition,it combined VOMT and symmetric key encryption schemes to construct the vector oblivious decryption matching test(VODMT)protocol and designed a TPSI protocol based on VODMT and oblivious pseudo-random functions that could resist malicious adversaries.Subsequently,it proved the security of the protocol under the semi-honest model and the malicious model respectively,and analyzed that the computational complexity and communication complexity of the two protocols were linear.When the set size is 4096,the online running time of the two proposed protocols is 0.81 s and 1.81 s respectively,while the previous work required 5627 s,so both protocols are efficient.