基于混淆布鲁姆过滤器的云外包隐私集合比较协议

doi:10.11772/j.issn.1001-9081.2016.10.2723

计算机应用 ›› 2016, Vol. 36 ›› Issue (10): 2723-2727.DOI: 10.11772/j.issn.1001-9081.2016.10.2723

基于混淆布鲁姆过滤器的云外包隐私集合比较协议

张恩^1,2, 刘亚鹏^1,2

1. 河南师范大学计算机与信息工程学院, 河南新乡 453007;
2. 智慧商务与物联网技术河南省工程实验室, 河南新乡 453007

收稿日期:2016-04-15 修回日期:2016-06-12 出版日期:2016-10-10 发布日期:2016-10-10
通讯作者: 张恩,E-mail:zhangenzdrj@163.com
作者简介:张恩(1974—),男,河南新乡人,副教授,博士,CCF会员,主要研究方向:信息安全、密码学;刘亚鹏(1991—),男,河南新乡人,硕士研究生,主要研究方向:信息安全、密码学。
基金资助:
国家自然科学基金资助项目（U1204606，U1404601）；河南省教育厅科学技术研究重点项目（14A520032）。

Cloud outsourcing private set intersection protocol based on garbled Bloom filter

ZHANG En^1,2, LIU Yapeng^1,2

1. College of Computer and Information Engineering, Henan Normal University, Xinxiang Henan 453007, China;
2. Engineering Laboratory of Intelligence Bussiness and Internet of Things of Henan Province, Xinxiang Henan 453007, China

Received:2016-04-15 Revised:2016-06-12 Online:2016-10-10 Published:2016-10-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (U1204606, U1404601), the Key Project of Science and Technology Research of Henan Provincial Department of Education (14A520032).

摘要/Abstract

摘要： 针对基于混淆布鲁姆过滤器的隐私集合比较（PSI）协议中存在参与方信息获取不对等及协议不能有效应用于云环境等问题，将混淆布鲁姆过滤器算法与代理不经意传输协议相结合，提出了一种基于混淆布鲁姆过滤器和代理不经意传输的云外包隐私集合比较协议。首先，该算法通过引入混淆布鲁姆过滤器的概念，解决了传统标准布鲁姆过滤器产生误判的问题，进而达到高效存储和传输大数据的目的；其次，采用代理不经意传输协议，能够将复杂耗时的计算外包给云代理服务器，使得云租户不需实时在线、仅需进行少量计算；最后，在云外包隐私集合比较过程中，云租户间无需交互，能够公平地得到集合比较结果。理论分析和性能对比表明，该算法的通信复杂度和计算复杂度是线性的，并且协议是安全和有效的。

关键词: 隐私集合比较, 云外包, 布鲁姆过滤器, 代理不经意传输

Abstract: Focusing on the issues that information acquired by different participants are not equal in the Private Set Intersection (PSI) protocol based on Garbled Bloom Filter (GBF), which can not be effectively applied to the cloud environment, a cloud outsourcing PSI protocol combined the garbled Bloom filter algorithm with the proxy oblivious transfer protocol was proposed. Firstly, by introducing the garbled Bloom filter, the problem of false positive in the traditional standard Bloom filter was solved to achieve efficient storage and large data transmission. Secondly, the complex time-consuming computation could be outsourced to the cloud proxy server by using proxy oblivious transfer protocol, so that the cloud tenants did not need to be online in real-time and only needed a small amount of computation. Finally, in the processing of the cloud outsourcing privacy set intersection, the comparison results could be fairly obtained without the interaction among the cloud tenants. Theoretical analysis and performance comparison show that the communication and computation complexities of the proposed protocol are linear, and the proposed protocol is safe and effective.

Key words: Private Set Intersection (PSI), cloud outsourcing, Bloom filter, proxy oblivious transfer

中图分类号:

TP309.7

张恩, 刘亚鹏. 基于混淆布鲁姆过滤器的云外包隐私集合比较协议[J]. 计算机应用, 2016, 36(10): 2723-2727.

ZHANG En, LIU Yapeng. Cloud outsourcing private set intersection protocol based on garbled Bloom filter[J]. Journal of Computer Applications, 2016, 36(10): 2723-2727.

参考文献

[1] YAO A C. Protocols for secure computations[C]//SFCS 1982: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 1982: 160-164.
[2] GOLDREICH O, MICALI S, WIGDERSON A. How to play any mental game[C]//Proceedings of the 19th Annual ACM Conference on Theory of Computing. New York: ACM, 1987:218-229.
[3] GOLDREICH O. Foundations of Cryptography: Basic Applications [M]. London: Cambridge University Press, 2004:693-747.
[4] 张恩, 蔡永泉. 理性的安全两方计算协议[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.)
[5] GKOULALAS-DIVANIS A, LOUKIDES G, SUN J. Publishing data from electronic health records while preserving privacy: a survey of algorithms[J]. Journal of Biomedical Informatics, 2014, 50: 4-19.
[6] ZHENG Q, XU S. Verifiable delegated set intersection operations on outsourced encrypted data[C]//Proceedings of the 2015 IEEE International Conference on Cloud Engineering. Washington, DC: IEEE Computer Society, 2015:175-184.
[7] 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. Piscataway, NJ: IEEE, 2015: 276-279.
[8] SARPONG S, XU C, ZHANG X. PPAM: privacy-preserving attributes matchmaking protocol for mobile social networks secure against malicious users[J]. International Journal of Network Security, 2016, 18(4): 625-632.
[9] GASTI P, RASMUSSEN K B. Privacy-preserving user matching[C]//Proceedings of the 14th ACM Workshop on Privacy in the Electronic Society. New York: ACM, 2015: 111-120.
[10] EMILIANO D C, KIM J. Linear-complexity private set intersection protocols secure in malicious model[C]//ASIACRYPT 2010: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2010: 213-231.
[11] DONG C, CHEN L, CAMENISCH J, et al. Fair private set intersection with a semi-trusted arbiter[C]//Proceedings of the 27th Annual IFIP WG 11.3 Conference on Data and Applications Security and Privacy XXVII. Berlin: Springer, 2013: 128-144.
[12] 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. Berlin: Springer, 2004:1-19.
[13] NIU B, ZHU X, LIU J, et al. Weight-aware private matching scheme for proximity-based mobile social networks[C]//Proceedings of the 2013 IEEE Global Communications Conference. Piscataway, NJ: IEEE, 2013: 3170-3175.
[14] AGRAWAL R, EVFIMIEVSKI A, SRIKANT R. Information sharing across private databases[C]//SIGMOD 2003: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2003: 86-97.
[15] STANISLAW J, LIU X. Fast secure computation of set intersection[C]//SCN 2010: Proceedings of the 7th International Conference on Security and Cryptography for Networks, LNCS 6280. Berlin: Springer, 2010, 6280:418-435.
[16] HAZAYC, LINDELLY. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries[C]//TCC 2008: Proceedings of the Fifth Theory of Cryptography Conference on Theory of Cryptography, LNCS 4948. Berlin: Springer, 2008: 155-175.
[17] JARECKI S, LIU X. Efficient oblivious pseudorandom function with applications to adaptive ot and secure computation of set intersection[C]//TCC 2009: Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography, LNCS 5444. Berlin: Springer, 2009: 577-594.
[18] KAMARA S, MOHASSEL P, RAYKOVA M, et al. Scaling private set intersection to billion-element sets[C]//FC 2014: Proceedings of the 18th International Conference on Financial Cryptography and Data Security, LNCS 8437. Berlin: Springer, 2014:195-215.
[19] KERSCHBAUM F. Outsourced private set intersection using homomorphic encryption [C]//Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security. New York: ACM, 2012: 85-86.
[20] BLOOM B H. Space/time trade-offs in Hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7):422-426.
[21] DONG C, CHEN L, WEN Z. When private set intersection meets big data: an efficient and scalable protocol[C]//Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. New York: ACM, 2013: 789-800.
[22] CHOI S G, KATZ J, KUMARESAN R, et al. Multi-client non-interactive verifiable computation[C]//TCC 2013: Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography. Berlin: Springer, 2013: 499-518.
[23] NAOR M, PINKAS B. Efficient oblivious transfer protocols [C]//SODA 2001: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM, 2001: 448-457.
[24] CRISTOFARO E D, TSUDIK G. Practical private set intersection protocols with linear complexity[C]//FC 2010: 14th International Conference on Financial Cryptography and Data Security, LNCS 6052. Berlin: Springer, 2010:143-159.
[25] HUANG Y, EVANS D, KATZ J. Private set intersection: are garbled circuits better than custom protocols?[EB/OL]. [2015-10-10]. http://www.cs.virginia.edu/~evans/pubs/ndss2012/psi.pdf.

基于混淆布鲁姆过滤器的云外包隐私集合比较协议

Cloud outsourcing private set intersection protocol based on garbled Bloom filter

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

[1]	张恩, 李会敏, 常键. 可验证的隐私保护k-means聚类方案[J]. 计算机应用, 2021, 41(2): 413-421.
[2]	张恩, 金刚刚. 基于同态加密和Bloom过滤器的云外包多方隐私集合比较协议[J]. 计算机应用, 2018, 38(8): 2256-2260.
[3]	唐铭史长琼周恺卿张大方. 倒插入分段哈希算法[J]. 计算机应用, 2011, 31(02): 514-516.
[4]	潘登张大方谢鲲张继. 一种基于折半层次搜索的包分类算法[J]. 计算机应用, 2009, 29(2): 500-502.
[5]	王景中杜飞. 矩阵型布鲁姆过滤器在病毒过滤防火墙中的研究[J]. 计算机应用, 2009, 29(11): 2939-2941.