Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (8): 2256-2260.DOI: 10.11772/j.issn.1001-9081.2018010075

Previous Articles     Next Articles

Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter

ZHANG En, JIN Ganggang   

  1. College of Computer and Information Engineering, Henan Normal University, Xinxiang Henan 453007, China
  • Received:2018-01-10 Revised:2018-03-21 Online:2018-08-10 Published:2018-08-11
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (U1604156, 61772176,61602158), the Science and Technology Research Project of Henan Province (172102210045).


张恩, 金刚刚   

  1. 河南师范大学 计算机与信息工程学院, 河南 新乡 453007
  • 通讯作者: 张恩
  • 作者简介:张恩(1974-),男,河南新乡人,副教授,博士,CCF会员,主要研究方向:信息安全、密码学;金刚刚(1992-),男,河南洛阳人,硕士研究生,主要研究方向:信息安全、密码学。
  • 基金资助:

Abstract: Considering the low computing efficiency of current multiparty Private Set Intersection (PSI) protocol and the leakage of user private information when it is applied in the cloud environment, a cloud outsourcing multiparty PSI protocol based on Bloom Filter (BF) and homomorphic encryption was proposed. Firstly, the NTRU Cryptosystems-based proxy re-encryption algorithm was used in the protocol to convert ciphertexts encrypted with different public keys into ciphertexts encrypted with the same public keys, and a large amount of complicated computing was outsourced to a cloud server. Secondly, Bloom filter, characterized by its low computing complexity, high space utilization rate and great query efficiency, was used to improve the efficiency of information encrypting, decrypting and querying when the protocol was operated. The user only needs a small amount of computing during the operation of the protocol instead of taking interactions and staying online in real time. Theoretical analysis and experimental results show that the proposed protocol has linear computation and communication complexity, it can work out intersection results without leaking user private information, which meets the requirement of practical application.

Key words: Private Set Intersection (PSI), homomorphic encryption, proxy re-encryption, cloud outsourcing, Bloom Filter (BF)

摘要: 针对目前多方隐私集合比较(PSI)协议计算效率低下以及应用于云环境中会造成用户隐私信息泄露的问题,提出一种基于布隆过滤器(BF)和同态加密的云外包多方隐私集合比较协议。首先,协议中使用基于NTRU Cryptosystems的代理重加密算法将不同公钥加密的密文转换成相同公钥加密的密文,并将大量复杂的计算外包给云服务器;其次,借助BF计算复杂度低、空间利用率高和查询效率高的优点,提高协议运行过程中对信息加密、解密和查询的效率,在协议运行过程中用户仅需进行少量计算,无需交互且不必实时在线。理论分析及实验结果表明,新协议的计算复杂度和通信复杂度是线性的,可以在不泄露用户隐私信息的前提下计算出比较结果,满足现实应用的需求。

关键词: 隐私集合比较, 同态加密, 代理重加密, 云外包, 布隆过滤器

CLC Number: