基于布隆过滤器的轻量级隐私信息匹配方案

doi:10.11959/j.issn.1000-436x.2015324

通信学报 ›› 2015, Vol. 36 ›› Issue (12): 151-162.doi: 10.11959/j.issn.1000-436x.2015324

基于布隆过滤器的轻量级隐私信息匹配方案

万盛¹,何媛媛²,李凤华^2,³,牛犇²,李晖¹,王新宇²

¹ 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071
² 中国科学院信息工程研究所信息安全国家重点实验室，北京 100195
³ 北京电子科技学院信息安全系，北京 100070

出版日期:2015-12-25 发布日期:2017-07-17
基金资助:
国家自然科学基金-广东联合基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目;教育部重点基金资助项目

Bloom filter-based lightweight private matching scheme

Sheng WAN¹,Yuan-yuan HE²,Feng-hua LI^2,³,Ben NIU²,Hui LI¹,Xin-yu WANG²

¹ State Key Laboratory of Integrated Services Networks,Xidian University,Xi’an 710071,China
² State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100195,China
³ Department of Information Security,Beijing Electronic Science and Technology Institute,Beijing 100070,China

Online:2015-12-25 Published:2017-07-17
Supported by:
The National Natural Science Foundation of China –Guangdong Union Foundation;The National High Technology Research and Development Program of China (863 Program);The Key Program of Scientific and Technology Research of Ministry of Education

摘要/Abstract

摘要：

针对智能终端用户私有数据匹配中的隐私保护问题，基于布隆过滤器和二元向量内积协议，提出一种新的综合考虑用户属性及其偏好的轻量级隐私信息匹配方案，包括建立基于 Dice 相似性系数的二维向量相似度函数、设置参数、生成布隆过滤器、计算二元向量内积、计算相似度和确定匹配对象6个部分。该方案采用基于布隆过滤器的相似度估计和基于混淆方法的二元向量内积协议，在不依赖于可信第三方的前提下，大幅度降低计算开销，且能够有效抵御蛮力攻击和无限制输入攻击。实验结果表明，该方案与典型代表方案相比，计算效率得到明显提升。

关键词: 隐私信息匹配, Dice相似性系数, 布隆过滤器, 二元向量内积协议

Abstract:

With rapid developments of mobile devices and online social networks,users of proximity-based mobile social networks (PMSN) could easily discover and make new social interactions with others,but they enjoyed this kind of conveniences at the cost of user privacy and system overhead,etc.To address this problem,a third party free and lightweight scheme to privately match the similarity with potential friends in vicinity was proposed.Unlike most existing work,proposed scheme considered both the number of common attributes and the corresponding priorities on each of them individually.The Bloom filter-based common-attributes estimation and the lightweight confusion binary vector scalar product protocol reduce the system overhead significantly,and can resist against brute force attack and unlimited input attack.The correctness,security and performance of overhead of proposed scheme are then thoroughly analyzed and evaluated via detailed simulations.

Key words: privacy matching, Dice similarity coefficient, Bloom filter, confusion binary vector scalar product protocol

万盛,何媛媛,李凤华,牛犇,李晖,王新宇. 基于布隆过滤器的轻量级隐私信息匹配方案[J]. 通信学报, 2015, 36(12): 151-162.

Sheng WAN,Yuan-yuan HE,Feng-hua LI,Ben NIU,Hui LI,Xin-yu WANG. Bloom filter-based lightweight private matching scheme[J]. Journal on Communications, 2015, 36(12): 151-162.

图/表 5

图1

表1

表2

图2

图3

参考文献 27

[1]	LU R , LIN X , LIANG X ,et al. A secure handshake scheme with symptoms-matching for healthcare social network[J]. Mobile Networks ＆ Applications—Special Issue on Wireless ＆ Personal Comm, 2011,16(6): 683-694.
[2]	SUN J , ZHANG R , ZHANG Y . Privacy-preserving spatiotemporal matching[A]. Proceedings of the 32nd IEEE International Conference on Computer Communications[C]. Turin,Italy, 2013. 800-808.
[3]	LI M , CAO N , YU S ,et al. FindU:privacy-preserving personal profile matching in mobile social networks[A]. Proceedings of the 30th IEEE International Conference on Computer Communications[C]. Shanghai,China, 2011. 2435-2443.
[4]	YANG Z , ZHANG B , DAI J ,et al. E-SmallTalker:a distributed mobile system for social networking in physical proximity[A]. Proceedings of the IEEE 30th International Conference on Distributed Computing Systems[C]. Genoa,Italy, 2010. 468-477.
[5]	BLOOM B H . Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970,13(7): 422-426.
[6]	LU R , LIU X , SHEN X . SPOC:a secure and privacy-preserving opportunistic computing framework for mobile-healthcare emergency[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,24(3): 614-624.
[7]	FREEDMAN M J , NISSIM K , PINKAS B . Efficient private matching and set intersection[A]. Advances in Cryptology - EUROCRYPT 2004[C]. Springer Berlin Heidelberg, 2004. 1-19.
[8]	KISSNER L , SONG D . Privacy-preserving set operations[A]. Advances in Cryptology – CRYPTO 2005[C]. Springer Berlin Heidelberg, 2005. 241-257.
[9]	DONG C , CHEN L , WEN Z . When private set intersection meets big data:an efficient and scalable protocol[A]. Proceedings of the 21st ACM Conference on Computer and Communications Security[C]. Scottsdale,USA, 2013. 789-800.
[10]	HAZAY C , NISSIM K . Efficient set operations in the presence of malicious adversaries[A]. Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography[C]. Paris,France, 2010. 383-433.
[11]	JARECKI S , LIU X . Fast secure computation of set intersection[A]. Proceedings of the 7th International Conference on Security and Cryptography for Networks[C]. Amalfi,Italy, 2010. 418-435.
[12]	CRISTOFARO E D , TSUDIK G . Practical private set intersection protocols with linear complexity[A]. Proceedings of the 14th International Conference on Financial Cryptography and Data Security[C]. Tenerife,Spain, 2010. 143-159.
[13]	CRISTOFARO E D , KIM G , TSUDIK G . Linear-complexity private set intersection protocols secure in malicious model[A]. Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security[C]. Singapore,Singapore, 2010. 213-231.
[14]	KERSCHBAUM F . Outsourced private set intersection using homomorphicencryption[A]. Proceedings of the Proceedings of the 7th ACM Symposium on Information,Computer and Communications Security[C]. Seoul,Korea, 2012. 85-86.
[15]	AGRAWAL R , EVFIMIEVSKI A , SRIKANT R . Information sharing across private databases[A]. Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data[C]. San Diego,USA, 2003. 86-97.
[16]	VAIDYA J , CLIFTON C . Secure set intersection cardinality with application to association rule mining[J]. Journal of Computer Security, 2002,1(13): 593-622.
[17]	VON M,BADER A M , KUHN M , WATTENHOFER R . Veneta:serverless friend-of-friend detection in mobile social networking[A]. Proceedings of the 2008 IEEE International Conference on Wireless ＆Mobile Computing,Networking ＆ Communication[C]. Avignon,France, 2008. 184-189.
[18]	ZHANG R , ZHANG Y , SUN J ,et al. Fine-grained private matching for proximity-based mobile social networking[A]. Proceedings of the 31st IEEE International Conference on Computer Communications[C]. Orlando,USA, 2012. 1969-1977.
[19]	NIU B , LI X , ZHU X ,et al. Are you really my friend? Exactly spatiotemporal matching scheme in privacy-aware mobile social networks[A]. Proceedings of the 10th International Conference on Security and Privacy in Communication Networks[C]. Beijing,China, 2014.
[20]	NIU B,HE Y , LI F H , LI H . Achieving secure friend discovery in social strength-aware PMSNs[A]. Proceedings of the the 34th Anniversary of the Premier International Conference for Military Communications[C]. Florida,USA, 2015.
[21]	NIU B , ZHU X , LIU J ,et al. Weight-aware private matching scheme for Proximity-based mobile social networks[A]. Proceedings of the IEEE 2003 Global Communications Conference[C]. Atlanta,USA, 2013. 3170-3175.
[22]	FU Y , WANG Y . BCE:a privacy-preserving common-friend estimation method for distributed online social networks without cryptography[A]. Proceedings of the 7th International Conference on Communications and Networking in China[C]. Kunming,China, 2012. 212-217.
[23]	MANY D , BURKHART M , DIMITROPOULOS X . Fast private set Operations with SEPIA[EB/OL]. .
[24]	POSE P , GUO H,KRANAKISE . On the false-positive rate of bloom filters[J]. Information Processing Letters, 2008,108(4): 210-213.
[25]	NIUB , ZHU X , ZHANG T . P-match:priority-aware friend discovery for proximity-based mobile social networks[A]. Proceedings of the10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems[C]. Hangzhou,China, 2013. 351-355.
[26]	CHEN Z , ZHU B . Some formal analysis of rocchio’s similarity-based relevance feedback algorithm[J]. Algorithms and Computation, 2000,19(69): 108-119.
[27]	PAPAPERTROU W , SIBERSKI W . Cardinality estimation and dynamic length adaptation for bloom filters[J]. Distributed ＆ Parallel Databases, 2010,28(2-3): 119-156(38).

方案	参与方	离线计算开销	在线计算开销	通信量/bit
Cristofaro方案	发起方	(2m+2m²)exp,(2m)h	(m+m²)exp,(m)h	3m·1 024
	响应方	(m+m²)exp,(2m)h	(2m)exp	4m·1 024
Zhang方案	发起方	—	(km)h	—
	响应方	(km)h	—	w
本文方案	发起方	(km)h,(2w)mul,(4w)add/sub	—	256w
	响应方	(km)h	(2w)mul,(4w)add/sub	320

运算	平均值	最大值	最小值	中位数	标准差
h	6.75	14	6	7	13.81
exp(×10³)	11.21	15.57	10.59	10.82	0.76
mul	1.599	1.760	1.493	1.644	0.081
add/sub	0.205 5	0.345 2	0.180 6	0.193 8	0.022

基于布隆过滤器的轻量级隐私信息匹配方案

Bloom filter-based lightweight private matching scheme

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 27

相关文章 2

Metrics

推荐阅读 0

[1]	杨冬梅, 陈越, 魏江宏, 胡学先. 基于身份的可穿刺签名方案[J]. 通信学报, 2021, 42(12): 17-26.
[2]	黄琼,熊文柱,阳小龙,徐杰,隆克平. 分层次的无状态单分组IP溯源技术[J]. 通信学报, 2011, 32(3): 150-157.