Consistency optimization algorithm for differential privacy streaming data publication with non-uniform private budgets

SUN Lan; KANG Jian; WU Yingjie; ZHANG Liqun

doi:10.16511/j.cnki.qhdxxb.2018.26.045

PDF(1333 KB)

Journal of Tsinghua University(Science and Technology) ›› 2019, Vol. 59 ›› Issue (3) : 203-210. DOI: 10.16511/j.cnki.qhdxxb.2018.26.045

COMPUTER SCIENCE AND TECHNOLOGY

Consistency optimization algorithm for differential privacy streaming data publication with non-uniform private budgets

{{article.zuoZhe_EN}}

Author information +

History +

Abstract

Most existing methods for differential privacy streaming data statistical release based on tree structures cannot take advantage of the special probability distributions in statistical queries. This study presents an algorithm that further boosts the accuracy of the released streaming data for differential privacy streaming data publication with non-uniform private budgets using sliding windows. After constructing the differential privacy range tree for the streaming data within the sliding window, the algorithm calculates the coverage probability of the tree nodes according to the probability distribution of the statistical queries and then adds non-uniform noise to the tree nodes based on the adjusted privacy budget of the tree nodes and a tree structure parameter. Finally, several real-time adjustment policies are designed to ensure that the node values on any path from the root to the leaves satisfy a consistency constraint. Tests show that the algorithm guarantees better statistical query accuracy and has higher algorithm efficiency than traditional algorithms.

Key words

differential privacy / streaming data release / sliding window / non-uniform privacy budget / consistency constraint

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

SUN Lan, KANG Jian, WU Yingjie, ZHANG Liqun. 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 https://doi.org/10.16511/j.cnki.qhdxxb.2018.26.045

References

[1] FUNG B C M, WANG K, CHEN R, et al. Privacy-preserving data publishing:A survey of recent developments[J]. ACM Computing Surveys, 2010, 42(4):14.
[2] DWORK C, NAOR M, PITASSI T, et al. Differential privacy under continual observation[C]//Proceedings of the 42nd ACM Symposium on Theory of Computing. Cambridge, Massachusetts, New York, USA:ACM, 2010:715-724.
[3] CHAN T H H, SHI E, SONG D. Private and continual release of statistics[J]. ACM Transactions on Information and System Security, 2011, 14(3):1-24.
[4] CAO J N, XIAO Q, GHINITA G, et al. Efficient and accurate strategies for differentially-private sliding window queries[C]//Proceedings of the 16th International Conference on Extending Database Technology. Genoa, Italy:ACM, 2013:191-202.
[5] BOLOT J, FAWAZ N, MUTHUKRISHNAN S, et al. Private decayed predicate sums on streams[C]//Proceedings of the 16th International Conference on Database Theory. Genoa, Italy:ACM, 2013:284-295.
[6] 张啸剑, 孟小峰. 基于差分隐私的流式直方图发布方法[J]. 软件学报, 2016,27(2):381-393.ZHANG X J, MENG X F. Streaming histogram publication method with differential privacy[J]. Journal of Software, 2016, 27(2):381-393.(in Chinese)
[7] KELLARIS G, PAPADOPOULOS S, XIAO X K, et al. Differentially private event sequences over infinite streams[J]. Proceedings of the VLDB Endowment, 2014, 7(12):1155-1166.
[8] CHAN T H H, LI M F, SHI E, et al. Differentially private continual monitoring of heavy hitters from distributed streams[C]//Proceedings of the 12th International Symposium on Privacy Enhancing Technologies. Vigo, Spain:Springer, 2012:140-159.
[9] WANG J, ZHU R B, LIU S B. A differentially private unscented Kalman filter for streaming data in IoT[J]. IEEE Access, 2018, 6:6487-6495.
[10] CHEN Y, MACHANAVAJJHALA A, HAY M, et al. PeGaSus:Data-adaptive differentially private stream processing[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, Texas, USA:ACM, 2017:1375-1388.
[11] DWORK C. Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Venice, Italy:Springer, 2006:1-12.
[12] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3rd Theory of Cryptography Conference on Theory of Cryptography. New York, USA:Springer, 2006:265-284.
[13] 周水庚, 李丰, 陶宇飞, 等. 面向数据库应用的隐私保护研究综述[J]. 计算机学报, 2009, 32(5):847-861.ZHOU S G, LI F, TAO Y F, et al. Privacy preservation in database application:A survey[J]. Chinese Journal of Computers, 2009, 32(5):847-861.(in Chinese)
[14] 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.
[15] 康健, 吴英杰, 黄泗勇, 等. 异方差加噪下的差分隐私直方图发布算法[J]. 计算机科学与探索, 2016, 10(6):786-798.KANG J, WU Y J, HUANG S Y, et al. Algorithm for differential privacy histogram publication with non-uniform private budget[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(6):786-798. (in Chinese)