基于同态加密的DBSCAN聚类隐私保护方案

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

通信学报 ›› 2021, Vol. 42 ›› Issue (2): 1-11.doi: 10.11959/j.issn.1000-436x.2021026

• 学术论文 • 下一篇

基于同态加密的DBSCAN聚类隐私保护方案

贾春福¹^,², 李瑞琪¹^,², 王雅飞¹^,²

¹ 南开大学网络空间安全学院，天津 300350
² 天津市网络与数据安全技术重点实验室，天津 300350

修回日期:2020-12-27 出版日期:2021-02-25 发布日期:2021-02-01
作者简介:贾春福（1967- ），男，河北文安人，博士，南开大学教授、博士生导师，主要研究方向为网络与系统安全、可信计算、恶意代码分析、密码技术应用等。
李瑞琪（1993- ），男，黑龙江尚志人，南开大学博士生，主要研究方向为同态加密、格密码学等。
王雅飞（1995- ），女，天津人，南开大学硕士生，主要研究方向为同态加密应用、隐私保护等。
基金资助:
国家重点研发计划基金资助项目(2018YFA0704703);国家自然科学基金资助项目(61972215);国家自然科学基金资助项目(61702399);国家自然科学基金资助项目(61972073);天津市自然科学基金资助项目(20JCZDJC00640)

Privacy protection scheme of DBSCAN clustering based on homomorphic encryption

Chunfu JIA¹^,², Ruiqi LI¹^,², Yafei WANG¹^,²

¹ College of Cyber Science, Nankai University, Tianjin 300350, China
² Tianjin Key Laboratory of Network and Data Security Technology, Tianjin 300350, China

Revised:2020-12-27 Online:2021-02-25 Published:2021-02-01
Supported by:
The National Key Research and Development Program of China(2018YFA0704703);The National Natural Science Foundation of China(61972215);The National Natural Science Foundation of China(61702399);The National Natural Science Foundation of China(61972073);The Natural Science Foundation of Tianjin(20JCZDJC00640)

摘要/Abstract

摘要：

为了降低数据外包聚类运算过程中存在的隐私泄露风险，提出了一个基于同态加密的 DBSCAN 聚类隐私保护方案。为了加密实际场景中的浮点型数据，给出了针对不同数据精度的3种数据预处理方式，并提出了一种基于数据特点且综合考虑数据精度和计算开销等方面的数据预处理方式的选择策略。由于同态加密不支持密文比较运算，设计了一个用户端与云服务器之间的协议实现密文比较功能。理论分析和实验结果表明，所提方案能够保证数据隐私安全，并且具有较高的聚类准确率和较低的时间开销。

关键词: 隐私保护, 密度聚类, 同态加密, 数据预处理, 密文比较

Abstract:

In order to reduce the risk of data privacy leakage in the process of outsourced clustering, a privacy protection scheme of DBSCAN clustering based on homomorphic encryption was proposed.In order to encrypt the float data in the actual scene, three data preprocessing methods for different data accuracy were given, and a policy for choosing a proper data preprocessing method based on data characteristics, accuracy and computational cost was also proposed.For the ciphertext comparison operation that was not supported by homomorphic encryption, a protocol between the client and the cloud server was designed to realize the function of ciphertext comparison.Theoretical analysis and experimental results show that the proposed scheme can ensure the security of data privacy, and has a higher clustering accuracy rate and lower time overhead.

Key words: privacy protection, density clustering, homomorphic encryption, data pre-processing, comparison on en-crypted data

中图分类号:

TP309.2

贾春福, 李瑞琪, 王雅飞. 基于同态加密的DBSCAN聚类隐私保护方案[J]. 通信学报, 2021, 42(2): 1-11.

Chunfu JIA, Ruiqi LI, Yafei WANG. Privacy protection scheme of DBSCAN clustering based on homomorphic encryption[J]. Journal on Communications, 2021, 42(2): 1-11.

图/表 15

图1

图2

图3

图4

图5

图6

表1

图7

图8

图9

图10

图11

图12

表2

表3

参考文献 20

[1]	ACAR A , AKSU H , ULUAGAC S ,et al. A survey on homomorphic encryption schemes:theory and implementation[J]. arXiv Preprint,arXiv:1704.03578, 2017.
[2]	BRAKERSKI Z , GENTRY C , VAIKUNTANATHAN V . (Leveled) fully homomorphic encryption without bootstrapping[C]// Innovations in Theoretical Computer Science. New York:ACM Press, 2012: 309-325.
[3]	BRAKERSKI Z , VAIKUNTANATHAN V . Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]// Proceedings of the 31st Annual Conference on Advances in Cryptology. Berlin:Springer, 2011: 505-524.
[4]	KIM J , KIM S , SEO J H . A new scale-invariant homomorphic encryption scheme[J]. Information Sciences, 2018,422: 177-187.
[5]	蒋林智, 许春香, 王晓芳 ,等. 同态加密在基于密文计算模型中的应用[J]. 密码学报, 2017,4(6): 596-610.
	JIANG L Z , XU C X , WANG X F ,et al. Application of homomorphic encryption for encrypted computing models[J]. Journal of Cryptologic Research, 2017,4(6): 596-610.
[6]	YANG H M , HE W C , LI J ,et al. Efficient and secure kNN classification over encrypted data using vector homomorphic encryption[C]// IEEE International Conference on Communications. Piscataway:IEEE Press, 2018: 1-7.
[7]	CHEON J H , JEONG J , KI D ,et al. Privacy protection K-means clustering with multiple data owners[J]. IACR Cryptology ePrint Archive, 2019(2019): 466.
[8]	ANGELA J , ARMKNECHT F . Unsupervised machine learning on encrypted data[C]// International Conference on Selected Areas in Cryptography. Berlin:Springer, 2018: 453-478.
[9]	HU S S , WANG Q , WANG J J ,et al. Securing SIFT:privacy protection outsourcing computation of feature extractions over encrypted image data[J]. IEEE Transactions on Image Processing, 2016,25(7): 3411-3425.
[10]	CHEN G M , CHEN Q , ZHU X Y ,et al. Encrypted image feature extraction by privacy protection MFS[C]// 2018 International Conference on Digital Home. Piscataway:IEEE Press, 2018: 42-45.
[11]	JIANG L Z , XU C X , WANG X F ,et al. Secure outsourcing SIFT:efficient and privacy protection image feature extraction in the encrypted domain[J]. IEEE Transactions on Dependable and Secure Computing, 2017,PP(99): 1.
[12]	JIANG L Z , XU C X , WANG X F ,et al. Statistical learning based fully homomorphic encryption on encrypted data[J]. Soft Computing, 2017,21(24): 7473-7483.
[13]	BACON D F , BENT G A , BERGAMASCHI F A ,et al. Performing efficient comparison operations on encrypted data:14952210[P].(2015-11-25)[2020-09-28].
[14]	JIANG L Q , CAO Y , YUAN C S ,et al. An effective comparison protocol over encrypted data in cloud computing[J]. Journal of Information Security and Applications, 2019,48: 102367.
[15]	贾春福, 王雅飞, 陈阳 ,等. 机器学习算法在同态加密数据集上的应用[J]. 清华大学学报(自然科学版), 2020,60(6): 456-463.
	JIA C F , WANG Y F , CHEN Y ,et al. Machine learning algorithms on homomorphic encrypted data set[J]. Journal of Tsinghua University (Science and Technology), 2020,60(6): 456-463.
[16]	HALEVI S , SHOUP V . Bootstrapping for HElib[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2015: 641-670.
[17]	KRYSZKIEWICZ M , SKONIECZNY L . Faster clustering with DBSCAN[C]// 2005 Intelligent Information Processing and Web Mining.[S.n.:s.l.], 2005: 605-614.
[18]	CHEN Y W , TANG S Y , BOUGUILA N ,et al. A fast clustering algorithm based on pruning unnecessary distance computations in DBSCAN for high-dimensional data[C]// Pattern Recognition.[S.n.:s.l.], 2018: 375-387.
[19]	CHEON J H , KIM D , KIM D ,et al. Numerical method for comparison on homomorphically encrypted numbers[C]// 25th International Conference on the Theory and Application of Cryptology and Information Security.[S.n.:s.l.], 2019: 415-445.
[20]	谭作文, 张连福 . 机器学习隐私保护研究综述[J]. 软件学报, 2020,31(7): 2127-2156.
	TAN Z W , ZHANG L F . Survey on privacy preserving techniques for machine learning[J]. Journal of Software, 2020,31(7): 2127-2156.

数据集	整数对编码		移位舍入编码		多元处理编码
数据集	时间/s	准确率	时间/s	准确率	时间/s	准确率
A	298.45	99.81%	115.48	99.75%	302.45	100%
B	115.45	100%	45.28	99.74%	155.65	100%

数据集A	聚类簇数	噪声点数目	准确率
明文数据集	5	93	100%
加密数据集（3位小数）	4	90	80%
加密数据集（4位小数）	5	90	99.75%
加密数据集（5位小数）	5	90	99.75%

数据集B	聚类簇数	噪声点数目	准确率
明文数据集	7	8	100%
加密数据集	7	6	99.74%

基于同态加密的DBSCAN聚类隐私保护方案

Privacy protection scheme of DBSCAN clustering based on homomorphic encryption

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 20

相关文章 15

Metrics

推荐阅读 0

[1]	马鑫迪, 李清华, 姜奇, 马卓, 高胜, 田有亮, 马建峰. 面向Non-IID数据的拜占庭鲁棒联邦学习[J]. 通信学报, 2023, 44(6): 138-153.
[2]	冯涛, 陈李秋, 方君丽, 石建明. 基于本地化差分隐私和属性基可搜索加密的区块链数据共享方案[J]. 通信学报, 2023, 44(5): 224-233.
[3]	夏莹杰, 朱思雨, 刘雪娇. 区块链架构下具有条件隐私的车辆编队跨信任域高效群组认证研究[J]. 通信学报, 2023, 44(4): 111-123.
[4]	胡柏吉, 张晓娟, 李元诚, 赖荣鑫. 支持多功能的V2G网络隐私保护数据聚合方案[J]. 通信学报, 2023, 44(4): 187-200.
[5]	徐明, 张保俊, 伍益明, 应晨铎, 郑宁. 面向网络攻击和隐私保护的多智能体系统分布式共识算法[J]. 通信学报, 2023, 44(3): 117-127.
[6]	余晟兴, 陈钟. 基于同态加密的高效安全联邦学习聚合框架[J]. 通信学报, 2023, 44(1): 14-28.
[7]	杨亚涛, 刘德莉, 刘培鹤, 曾萍, 肖嵩. BFV-Blockchainvoting：支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9): 100-111.
[8]	张学旺, 黎志鸿, 林金朝. 基于公平盲签名和分级加密的联盟链隐私保护方案[J]. 通信学报, 2022, 43(8): 131-141.
[9]	王继锋, 王国峰. 边缘计算模式下密文搜索与共享技术研究[J]. 通信学报, 2022, 43(4): 227-238.
[10]	封化民, 史瑞, 袁峰, 李艳俊, 杨旸. 高效的强隐私保护和可转让的属性票据方案[J]. 通信学报, 2022, 43(3): 63-75.
[11]	于海宁, 张宏莉, 余翔湛, 曲家兴, 葛蒙蒙. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022, 43(11): 1-13.
[12]	彭滔, 钟文韬, 王国军, 罗恩韬, 熊金波, 刘忆宁, Hao Wang. 移动社交网络中面向隐私保护的精确好友匹配[J]. 通信学报, 2022, 43(11): 90-103.
[13]	史瑞, 封化民, 谢惠琴, 史国振, 刘飚, 杨旸. 基于带智能卡的移动终端实现的隐私保护的属性票据方案[J]. 通信学报, 2022, 43(10): 26-41.
[14]	熊金波, 周永洁, 毕仁万, 万良, 田有亮. 边缘协同的轻量级隐私保护分类框架[J]. 通信学报, 2022, 43(1): 127-137.
[15]	晏燕, 丛一鸣, Adnan Mahmood, 盛权政. 基于深度学习的位置大数据统计发布与隐私保护方法[J]. 通信学报, 2022, 43(1): 203-216.