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

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

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 6

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

顾客	食物	消费数量/份	时间
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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 19

Related Articles 15

Metrics

Recommended 0

[1]	Shengxing YU, Zekai CHEN, Zhong CHEN, Ximeng LIU. DAGUARD: distributed backdoor attack defense scheme under federated learning [J]. Journal on Communications, 2023, 44(5): 110-122.
[2]	Tao FENG, Liqiu CHEN, Junli FANG, Jianming SHI. Blockchain data sharing scheme based on localized difference privacy and attribute-based searchable encryption [J]. Journal on Communications, 2023, 44(5): 224-233.
[3]	Cheng ZHONG, Hui SUN. Parallel algorithm for sensitive sequence recognition from long-read genome data with high error rate [J]. Journal on Communications, 2023, 44(2): 160-171.
[4]	Shufen ZHANG, Yanling DONG, Jingcheng XU, Haoshi WANG. AdaBoost algorithm based on target perturbation [J]. Journal on Communications, 2023, 44(2): 198-209.
[5]	Lingtao TANG, Di WANG, Shengyun LIU. Data augmentation scheme for federated learning with non-IID data [J]. Journal on Communications, 2023, 44(1): 164-176.
[6]	Chengsheng YUAN, Qiang GUO, Zhangjie FU. Copyright protection algorithm based on differential privacy deep fake fingerprint detection model [J]. Journal on Communications, 2022, 43(9): 181-193.
[7]	Hanyi WANG, Xiaoguang LI, Wenqing BI, Yahong CHEN, Fenghua LI, Ben NIU. Multi-level local differential privacy algorithm recommendation framework [J]. Journal on Communications, 2022, 43(8): 52-64.
[8]	Xin SONG, Shuyan NI, Zhe ZHANG, Yurong LIAO, Tuofeng LEI. Low error floor LT coding algorithm for unequal error protection [J]. Journal on Communications, 2022, 43(6): 85-97.
[9]	Yong ZHANG, Dandan LI, Lu HAN, Xiaohong HUANG. Privacy-protected crowd-sensed data trading algorithm [J]. Journal on Communications, 2022, 43(5): 1-13.
[10]	Chuanhuang LI, Yangting CHEN, Jingjing TANG, Jiali LOU, Renhua XIE, Chuntao FANG, Weiming WANG, Chao CHEN. QL-STCT: an intelligent routing convergence method for SDN link failure [J]. Journal on Communications, 2022, 43(2): 131-142.
[11]	Youliang TIAN, Yansen YUAN, Hongfeng GAO, Yang YANG, Jinbo XIONG. Equity decentralized consensus algorithm based on incentive compatibility [J]. Journal on Communications, 2022, 43(12): 101-112.
[12]	Qingmin JIA, Yujiao HU, Huayu ZHANG, Kailai PENG, Pingping CHEN, Renchao XIE, Tao HUANG. Research on deterministic computing power network [J]. Journal on Communications, 2022, 43(10): 55-64.
[13]	Haiyan KANG, Yuanrui JI. Research on federated learning approach based on local differential privacy [J]. Journal on Communications, 2022, 43(10): 94-105.
[14]	Yan YAN, Yiming CONG, Mahmood Adnan, Quanzheng SHENG. Statistics release and privacy protection method of location big data based on deep learning [J]. Journal on Communications, 2022, 43(1): 203-216.
[15]	Xin SONG, Naiping CHENG, Shuyan NI, Yurong LIAO, Tuofeng LEI. Low error floor LT coding algorithm by using fixed-length node classification window [J]. Journal on Communications, 2021, 42(9): 31-42.