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

doi:10.11772/j.issn.1001-9081.2018010075

Abstract

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:

TP309.7

ZHANG En, JIN Ganggang. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter[J]. Journal of Computer Applications, 2018, 38(8): 2256-2260.

张恩, 金刚刚. 基于同态加密和Bloom过滤器的云外包多方隐私集合比较协议[J]. 计算机应用, 2018, 38(8): 2256-2260.

References

[1] 罗小双,杨晓元,王绪安.适用于社交网络的隐私保护兴趣度匹配方案[J].计算机应用,2016,36(12):3322-3327. (LUO X S,YANG X Y,WANG X A. Privacy preserving interest matching scheme for social network[J]. Journal of Computer Applications, 2016, 36(12):3322-3327.)
[2] PATSAKIS C, ZIGOMITROS A, SOLANAS A. Privacy-aware genome mining:server-assisted protocols for private set intersection and pattern matching[C]//Proceedings of the 2015 IEEE 28th International Symposium on Computer-Based Medical Systems. Washington, DC:IEEE Computer Society, 2015:276-279.
[3] ABADI A, TERZIS S, DONG C. O-PSI:delegated private set intersection on outsourced datasets[C]//SEC 2015:Proceedings of the 2015 International Information Security Conference on ICT Systems Security and Privacy Protection, IFIPAICT 455. Cham:Springer, 2015:3-17.
[4] DACHMAN-SOLED D, MALKIN T, RAYKOVA M, et al. Efficient robust private set intersection[C]//ACNS 2009:Proceedings of the 2006 International Conference on Applied Cryptography and Network Security, LNCS 5536. Berlin:Springer, 2006:125-142.
[5] HAZAY C. Oblivious polynomial evaluation and secure set intersection from algebraic PRFs[C]//TCC 2015:Proceedings of the 2015 Theory of Cryptography Conference, LNCS 9015. Berlin:Springer, 2015:90-120.
[6] FREEDMAN M J, NISSIM K, PINKAS B. Efficient private matching and set intersection[C]//EUROCRYPT 2004:Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 3027. Berlin:Springer, 2004:1-19.
[7] KISSNER L, SONG D. Privacy-preserving set operations[C]//CRYPTO'05:Proceedings of the 25th Annual International Conference on Advances in Cryptology, LNCS 3621. Berlin:Springer, 2005:241-257.
[8] 李顺东,周素芳,郭奕旻,等.云环境下集合隐私计算[J].软件学报,2016,27(6):1549-1565. (LI S D, ZHOU S F, GUO Y M, et al. Secure set computing on cloud computing[J]. Journal of Software, 2016, 27(6):1549-1565.)
[9] de CRISTOFARO E, TSUDIK G. Practical private set intersection protocols with linear complexity[C]//FC 2010:Proceedings of the 2010 International Conference on Financial Cryptography and Data Security, LNCS 6052. Berlin:Springer, 2010:143-159.
[10] 张恩,蔡永泉.理性的安全两方计算协议[J].计算机研究与发展,2013,50(7):1409-1417. (ZHANG E, CAI Y Q. Rational secure two-party computation protocol[J]. Journal of Computer Research and Development, 2013, 50(7):1409-1417.)
[11] ZHANG E, LI F, NIU B, et al. Server-aided private set intersection based on reputation[J]. Information Sciences, 2017, 387:180-194.
[12] DONG C, CHEN L, WEN Z. When private set intersection meets big data:an efficient and scalable protocol[C]//CCS'13:Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM, 2013:789-800.
[13] KAMARA S, MOHASSEL P, RAYKOVA M, et al. Scaling private set intersection to billion-element sets[C]//FC 2014:Proceedings of the 2014 International Conference on Financial Cryptography and Data Security, LNCS 8437. Berlin:Springer, 2014:195-215.
[14] CHEN H, LAINE K, RINDAL P. Fast private set intersection from homomorphic encryption[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM, 2017:1243-1255.
[15] RINDAL P, ROSULEK M. Improved private set intersection against malicious adversaries[C]//EUROCRYPT 2017:Proceedings of the 2017 Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 10210. Cham:Springer, 2017:235-259.
[16] DONG C, CHEN L, WEN Z. When private set intersection meets big data:an efficient and scalable protocol[C]//CCS'13:Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM, 2013:789-800.
[17] KERSCHBAUM F. Outsourced private set intersection using homomorphic encryption[C]//ASIACCS'12:Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security. New York:ACM, 2012:85-86.
[18] BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7):422-426.
[19] BOSE P, GUO H, KRANAKIS E, et al. On the false-positive rate of Bloom filters[J]. Information Processing Letters, 2008, 108(4):210-213.
[20] PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[C]//EUROCRYPT 1999:Proceedings of the 1999 International Conference on Theory and Application of Cryptographic Techniques, LNCS 1592. Berlin:Springer, 1999:223-238.
[21] BLAZE M, BLEUMER G, STRAUSS M. Divertible protocols and atomic proxy cryptography[C]//EUROCRYPT 1998:Proceedings of the 1998 International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 1403. Berlin:Springer, 1998:127-144.
[22] NUÑEZ D, AGUDO I, LOPEZ J. NTRU ReEncrypt:an efficient proxy re-encryption scheme based on NTRU[C]//ASIA CCS'15:Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security. New York:ACM, 2015:179-189.
[23] GOLDREICH O. Foundations of Cryptography:Volume 2, Basic Applications[M]. New York:Cambridge University Press, 2009:620-625.