差分隐私下多重一致性约束问题的逼近方法

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

通信学报 ›› 2021, Vol. 42 ›› Issue (6): 107-117.doi: 10.11959/j.issn.1000-436x.2021122

差分隐私下多重一致性约束问题的逼近方法

蔡剑平¹, 刘西蒙¹, 熊金波², 应作斌³, 吴英杰¹

¹ 福州大学数学与计算机科学学院，福建福州 350108
² 福建师范大学数学与信息学院，福建福州 350117
³ 新加坡南洋理工大学电气与电子工程学院，新加坡 639798

修回日期:2021-04-03 出版日期:2021-06-25 发布日期:2021-06-01
作者简介:蔡剑平（1990− ），男，福建漳州人，福州大学博士生，主要研究方向为差分隐私、矩阵分析及理论、最优化理论、大数据技术及理论等
刘西蒙（1988− ），男，陕西西安人，博士，福州大学研究员、福建省“闽江学者”特聘教授，主要研究方向为隐私计算、密文数据挖掘、大数据隐私保护、可搜索加密等
熊金波（1981− ），男，湖南益阳人，博士，福建师范大学教授，主要研究方向为安全深度学习、移动群智感知、隐私保护技术等
应作斌（1982− ），男，安徽芜湖人，博士，新加坡南洋理工大学在站博士后，主要研究方向为基于属性的加密、区块链及隐私保护机器学习
吴英杰（1979− ），男，福建泉州人，博士，福州大学教授、博士生导师，主要研究方向为数据安全隐私保护、工业大数据分析、智能医疗
基金资助:
国家自然科学基金资助项目(62072109);国家自然科学基金资助项目(U1804263);国家自然科学基金资助项目(61702105);国家自然科学基金资助项目(62002062)

Approximation method of multiple consistency constraint under differential privacy

Jianping CAI¹, Ximeng LIU¹, Jinbo XIONG², Zuobin YING³, Yingjie WU¹

¹ College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
² College of Mathematics and Informatics, Fujian Normal University, Fuzhou 350117, China
³ School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore 639798, Singapore

Revised:2021-04-03 Online:2021-06-25 Published:2021-06-01
Supported by:
The National Natural Science Foundation of China(62072109);The National Natural Science Foundation of China(U1804263);The National Natural Science Foundation of China(61702105);The National Natural Science Foundation of China(62002062)

摘要/Abstract

摘要：

为了解决差分隐私下多重一致性约束的最优发布问题，通过分析最优一致性发布原理提出了多重一致性约束问题的逼近方法。所提方法的主要思想是将一致性约束问题划分为多个一致性约束子问题，通过反复独立地求解各一致性约束子问题实现原问题的最优一致性发布。其优势在于一致性约束问题划分之后，子问题往往更容易求解或者实现子问题最优一致性发布的技术已相当成熟，从而能够解决更加复杂的差分隐私最优发布问题。分析论证了逼近方法的收敛性，保证任意一致性约束子问题的划分均能实现原问题的最优一致性发布。并且，以销量直方图发布为例，基于多重一致性约束问题的逼近方法设计了差分隐私餐馆销量直方图一致性并行发布算法。实验表明，该算法相比通用解法可提升效率高达400倍，并且具备处理百万级大规模数据的能力。

关键词: 差分隐私, 一致性约束, 逼近方法, 收敛性, 并行计算

Abstract:

Under differential privacy, to solve the optimal publishing problem with multiple consistency constraints, an approximation method of multiple consistency constraints was proposed by the theoretical analysis of the principle of optimal consistency release.The main idea was to divide the consistency constraint problem into several consistency constraint sub-problems and then achieve the original problem's optimal consistency release by solving each consistency constraint sub-problem repeatedly and independently.The advantage was that after the consistency constraint problem divided, the sub-problems were often easier to solve, or the technology to achieve optimal and consistent release of sub-problems is quite mature.Therefore more complex differential privacy optimal release problem could be solved.After analysis, the approximation method's convergence was fully demonstrated, ensuring that any partition of consistency constrained sub-problems can always achieve the optimal consistency release of the original problem.Furthermore, taking the sales histogram publishing as an example, based on the approximation method of multiple consistency constraints, a parallel algorithm was designed with optimal consistency release under differential privacy.The experimental results show that the algorithm's efficiency is 400 times higher than that of the general solution, and the algorithm can process millions of large-scale data.

Key words: differential privacy, consistency constraint, approximation method, convergence, parallel computing

中图分类号:

TP309

蔡剑平, 刘西蒙, 熊金波, 应作斌, 吴英杰. 差分隐私下多重一致性约束问题的逼近方法[J]. 通信学报, 2021, 42(6): 107-117.

Jianping CAI, Ximeng LIU, Jinbo XIONG, Zuobin YING, Yingjie WU. Approximation method of multiple consistency constraint under differential privacy[J]. Journal on Communications, 2021, 42(6): 107-117.

图/表 6

表1

表2

图1

图2

图3

图4

参考文献 19

[1]	DWORK C , . Differential privacy[C]// The 33rd International Conference on Automata,Languages and Programming - Volume Part II. Berlin:Springer, 2006: 1-12.
[2]	HAY M , RASTOGI V , MIKLAU G ,et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment, 2010,3(1/2): 1021-1032.
[3]	吴英杰, 陈鸿, 王一蕾 ,等. 面向任意区间树结构的差分隐私直方图发布算法[J]. 模式识别与人工智能, 2015,28(12): 1084-1092.
	WU Y J , CHEN H , WANG Y L ,et al. A differentially private histogram publication algorithm for arbitrary range tree structure[J]. Pattern Recognition and Artificial Intelligence, 2015,28(12): 1084-1092.
[4]	孙岚, 康健, 吴英杰 ,等. 异方差加噪下差分隐私流数据发布一致性优化算法[J]. 清华大学学报(自然科学版), 2019,59(3): 203-210.
	SUN L , KANG J , WU Y J ,et al. Consistency optimization algorithm for differential privacy streaming data publication with non-uniform private budgets[J]. Journal of Tsinghua University (Science and Technology), 2019,59(3): 203-210.
[5]	贾俊杰, 陈慧, 马慧芳 ,等. 差分隐私的查询一致性约束研究[J]. 计算机工程与科学, 2020,42(1): 71-79.
	JIA J J , CHEN H , MA H F ,et al. Query consistency constraints of differential privacy[J]. Computer Engineering ＆ Science, 2020,42(1): 71-79.
[6]	LEE J , WANG Y , KIFER D . Maximum likelihood postprocessing for differential privacy under consistency constraints[C]// The 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2015: 635-644.
[7]	张双越, 蔡剑平, 田丰 ,等. 差分隐私下满足一致性的轨迹流量发布方法[J]. 计算机科学与探索, 2018,12(12): 1903-1913.
	ZHANG S Y , CAI J P , TIAN F ,et al. Trajectory flow releasing method with consistency constraint under differential privacy[J]. Journal of Frontiers of Computer Science and Technology, 2018,12(12): 1903-1913.
[8]	CORMODE G , PROCOPIUC C , SRIVASTAVA D ,et al. Differentially private spatial decompositions[J]. arXiv Preprint,arXiv:1103.5170, 2011.
[9]	DWORK C , KENTHAPADI K , MCSHERRY F ,et al. Our data,ourselves:privacy via distributed noise generation[C]// Advances in Cryptology - EUROCRYPT 2006. Berlin:Springer, 2006: 486-503.
[10]	DWORK C , MCSHERRY F , NISSIM K ,et al. Calibrating noise to sensitivity in private data analysis[C]// Theory of Cryptography Conference. Berlin:Springer, 2006: 265-284.
[11]	LI C , HAY M , RASTOGI V ,et al. Optimizing linear counting queries under differential privacy[C]// The 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems of Data. New York:ACM Press, 2010: 123-134.
[12]	LEE J , CLIFTON C W . Top-k frequent itemsets via differentially private FP-trees[C]// The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Pree, 2014: 931-940.
[13]	CORMODE G , PROCOPIUC C , SRIVASTAVA D ,et al. Differentially private spatial decompositions[C]// 2012 IEEE 28th International Conference on Data Engineering. Piscataway:IEEE Press, 2012: 20-31.
[14]	DWYER P S , RAO C R , MITRA S K . Generalized inverse of matrices and its applications[J]. Journal of the American Statistical Association, 1973,68(341): 239.
[15]	GRAYBILL F A , MEYER C D , PAINTER R J . Note on the computation of the generalized inverse of a matrix[J]. SIAM Review, 1966,8(4): 522-524.
[16]	PENROSE R . A generalized inverse for matrices[J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1955,51(3): 406-413.
[17]	TüRKMEN R , G?KBA? H . On the spectral norm of r-circulant matrices with the Pell and Pell-Lucas numbers[J]. Journal of Inequalities and Applications, 2016,2016(1): 1-7.
[18]	CHEN Y , MACHANAVAJJHALA A , HAY M ,et al. PeGaSus:dataadaptive differentially private stream processing[C]// The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2017: 1375-1388.
[19]	QARDAJI W , YANG W N , LI N H . Understanding hierarchical methods for differentially private histograms[J]. Proceedings of the VLDB Endowment, 2013,6(14): 1954-1965.

顾客	食物	消费数量/份	时间
Alice	可乐	1	Day 1
Bod	汉堡	1	Day 2
?
Tom	可乐	2	Day 25
?

食物	销量/份
食物	Day 1	Day 2	…	Day 25	…
可乐	35	25	…	31	…
汉堡	44	28	…	37	…
鸡翅	31	21	…	26	…
薯条	23	13		19	…
鸡块	24	16	…	21	…

差分隐私下多重一致性约束问题的逼近方法

Approximation method of multiple consistency constraint under differential privacy

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 19

相关文章 15

Metrics

推荐阅读 0

[1]	余晟兴, 陈泽凯, 陈钟, 刘西蒙. DAGUARD：联邦学习下的分布式后门攻击防御方案[J]. 通信学报, 2023, 44(5): 110-122.
[2]	冯涛, 陈李秋, 方君丽, 石建明. 基于本地化差分隐私和属性基可搜索加密的区块链数据共享方案[J]. 通信学报, 2023, 44(5): 224-233.
[3]	钟诚, 孙辉. 高错误率长序列基因组数据敏感序列识别并行算法[J]. 通信学报, 2023, 44(2): 160-171.
[4]	张淑芬, 董燕灵, 徐精诚, 王豪石. 基于目标扰动的AdaBoost算法[J]. 通信学报, 2023, 44(2): 198-209.
[5]	汤凌韬, 王迪, 刘盛云. 面向非独立同分布数据的联邦学习数据增强方案[J]. 通信学报, 2023, 44(1): 164-176.
[6]	袁程胜, 郭强, 付章杰. 基于差分隐私的深度伪造指纹检测模型版权保护算法[J]. 通信学报, 2022, 43(9): 181-193.
[7]	王瀚仪, 李效光, 毕文卿, 陈亚虹, 李凤华, 牛犇. 多级本地化差分隐私算法推荐框架[J]. 通信学报, 2022, 43(8): 52-64.
[8]	宋鑫, 倪淑燕, 张喆, 廖育荣, 雷拓峰. 面向不等差错保护的低误码平台LT编码算法[J]. 通信学报, 2022, 43(6): 85-97.
[9]	张勇, 李丹丹, 韩璐, 黄小红. 隐私保护的群体感知数据交易算法[J]. 通信学报, 2022, 43(5): 1-13.
[10]	康海燕, 冀源蕊. 基于本地化差分隐私的联邦学习方法研究[J]. 通信学报, 2022, 43(10): 94-105.
[11]	晏燕, 丛一鸣, Adnan Mahmood, 盛权政. 基于深度学习的位置大数据统计发布与隐私保护方法[J]. 通信学报, 2022, 43(1): 203-216.
[12]	宋鑫, 程乃平, 倪淑燕, 廖育荣, 雷拓峰. 采用定长节点分类窗口的低误码平台LT编码算法[J]. 通信学报, 2021, 42(9): 31-42.
[13]	陈思, 付安民, 苏铓, 孙怀江. 基于差分隐私的轨迹隐私保护方案[J]. 通信学报, 2021, 42(9): 54-64.
[14]	李洪涛, 任晓宇, 王洁, 马建峰. 基于差分隐私的连续位置隐私保护机制[J]. 通信学报, 2021, 42(8): 164-175.
[15]	陶梅霞, 王栋, 孙瑞, 张乃夫. 联邦学习中基于时分多址接入的用户调度策略[J]. 通信学报, 2021, 42(6): 1-29.