A Skyline Query Method Based on Differential Privacy Protection
-
摘要:
为了解决差分隐私保护机制中重复攻击会泄露用户隐私的问题,提出了一种基于动态页敏感度调节的skyline查询方法. 首先,提出了依据最优主导页的计算页敏感度方法,提高页敏感度计算的效率;其次,为了合理设置隐私预算值,提出了基于置信率的隐私预算值调节方法;最后,基于隐私预算值动态更新查询次数的上界,实现了基于差分隐私保护的skyline查询方法. 实验结果表明:所提出方法在隐私预算值设定小于0.8时,隐私数据的泄露数由787个降低到423个.
Abstract:In order to solve the problem that replay attacks in the differential privacy protection mechanism will leak user privacy, a skyline query method based on dynamic page sensitivity adjustment is proposed. First, in order to improve the efficiency of page sensitivity calculation, a method for calculating page sensitivity on the basis of the optimal dominant page is presented. Secondly, to reasonably set the privacy budget value, a privacy budget value adjustment method based on the confidence rate is developed. Finally, the upper bound of query times is dynamically updated based on the privacy budget value, and the skyline query method based on differential privacy protection is realized. The experimental results show that the proposed method reduces the number of leaked private data from 787 to 423 when the privacy budget value is set to be less than 0.8.
-
Key words:
- skyline query /
- page sensitivity /
- confidence rate /
- dynamic privacy budget /
- maximum range query
-
表 1 skyline分页查询结果
Table 1. Skyline paged query results
页 结果 1 {(P1, O1), (P1, O2), (P1, O3), (P1, O4), (P1, O5)} 2 {(P2, O1), (P2, O2), (P2,O3), (P2, O4), (P2, O5)} 3 {(P3, O1), (P3, O2), (P3, O3), (P3, O4)} 4 {(P4,O1), (P4, O2), (P4, O3)} -
[1] BORZSONY S, KOSSMANN D, STOCKER K. The skyline operator[C]//Proceedings 17th International Conference on Data Engineering. Heidelberg: IEEE, 2001: 421-430. [2] SOHAIL A, CHEEMA M A, TANIAR D. Social-aware spatial top-k and skyline queries[J]. The Computer Journal, 2018, 61(11): 1620-1638. doi: 10.1093/comjnl/bxy019 [3] SANTOSO B J, CONNERY T Y. Answering why-not questions on reverse skyline queries over incomplete data[J]. JUTI: Jurnal Ilmiah Teknologi Informasi, 2019, 17(1): 84-93. doi: 10.12962/j24068535.v17i1.a824 [4] FORT M, SELLARÈS J A, VALLADARES N. Nearest and farthest spatial skyline queries under multiplicative weighted Euclidean distances[J]. Knowledge-Based Systems, 2020, 192: 105-109. [5] 李松, 王冠群, 郝晓红, 等. 面向推荐系统的多目标决策优化算法. 西安交通大学学报, 2022, 56(8): 104-112.LI Song, WANG Guanqun, HAO Xiaohong, et al. A multi-objective decision optimization algorithm for recommendation system[J]. Journal of Xi’an Jiaotong University, 2022, 56(8): 104-112. [6] 李松,窦雅男,郝晓红,等. 道路网环境下K-支配空间Skyline查询方法[J]. 计算机研究与发展,2020,57(1): 227-239. doi: 10.7544/issn1000-1239.2020.20190026LI Song, DOU Yanan, HAO Xiaohong, et al. The method of the K-dominant space skyline query in road network[J]. Journal of Computer Research and Development, 2020, 57(1): 227-239. doi: 10.7544/issn1000-1239.2020.20190026 [7] 熊玲,彭代渊,彭图,等. 一种高效的移动云服务环境下隐私保护认证协议[J]. 西南交通大学学报,2019,54(1): 202-210.XIONG Ling, PENG Daiyuan, PENG Tu, et al. Efficient privacy-preserving authentication protocol for mobile cloud computing services[J]. Journal of Southwest Jiaotong University, 2019, 54(1): 202-210. [8] DWORK C. Differential privacy[M]//Automata, Languages and Programming. Berlin: Springer, 2006: 1-12. [9] MIRONOV I. Rényi differential privacy[C]//2017 IEEE 30th Computer Security Foundations Symposium. Santa Barbara: IEEE, 2017: 263-275. [10] CHAUDHURI K, IMOLA J, MACHANAVAJJHALA A. Capacity bounded differential privacy[J]. Advances in Neural Information Processing Systems, 2019: 3474-3483. [11] MCGREGOR A, MIRONOV I, PITASSI T, et al. The limits of two-party differential privacy[C]//2010 IEEE 51st Annual Symposium on Foundations of Computer Science. Las Vegas: IEEE, 2010: 81-90. [12] NISSIM K, RASKHODNIKOVA S, SMITH A. Smooth sensitivity and sampling in private data analysis[C]//Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. San Diego: ACM Press, 2007: 75-84. [13] MCSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//48th Annual IEEE Symposium on Foundations of Computer Science. [S.l.]: IEEE, 2007: 94-103. [14] HOMAYOUN S, DEHGHANTANHA A, AHMAD- ZADEH M, et al. Know abnormal, find evil:frequent pattern mining for ransomware threat hunting and intelligence[J]. IEEE Transactions on Emerging Topics in Computing, 2020, 8(2): 341-351. doi: 10.1109/TETC.2017.2756908 [15] DING X F, YANG W L, CHOO K K R, et al. Privacy preserving similarity joins using MapReduce[J]. Information Sciences, 2019, 493: 20-33. doi: 10.1016/j.ins.2019.03.035 [16] CHENG X, SU S, XU S Z, et al. DP-apriori:a differentially private frequent itemset mining algorithm based on transaction splitting[J]. Computers & Security, 2015, 50: 74-90. doi: 10.1016/j.cose.2014.12.005 [17] OU L, QIN Z, LIAO S L, et al. Singular spectrum analysis for local differential privacy of classifications in the smart grid[J]. IEEE Internet of Things Journal, 2020, 7(6): 5246-5255. doi: 10.1109/JIOT.2020.2977220 [18] ZHOU G Q, QIN S, ZHOU H F, et al. A differential privacy noise dynamic allocation algorithm for big multimedia data[J]. Multimedia Tools and Applications, 2019, 78(3): 3747-3765. doi: 10.1007/s11042-018-5776-0 [19] JUNG T, JUNG K, PARK S, et al. A noise parameter configuration technique to mitigate detour inference attack on differential privacy[C]//2017 IEEE International Conference on Big Data and Smart Computin. Jeju: IEEE, 2017: 186-192. [20] XU C G, REN J, ZHANG D Y, et al. GANobfuscator:mitigating information leakage under GAN via differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2019, 14(9): 2358-2371. doi: 10.1109/TIFS.2019.2897874 [21] YIN C Y, XI J W, SUN R X, et al. Location privacy protection based on differential privacy strategy for big data in industrial Internet of Things[J]. IEEE Transactions on Industrial Informatics, 2018, 14(8): 3628-3636. doi: 10.1109/TII.2017.2773646 [22] HSU J, GABOARDI M, HAEBERLEN A, et al. Differential privacy: an economic method for choosing epsilon[C]//2014 IEEE 27th Computer Security Foundations Symposium. Vienna: IEEE, 2014: 398-410. [23] ZHANG W J, LI M, TANDON R, et al. Online location trace privacy:an information theoretic approach[J]. IEEE Transactions on Information Forensics and Security, 2019, 14(1): 235-250. doi: 10.1109/TIFS.2018.2848659 [24] LI X G, LI H, ZHU H, et al. The optimal upper bound of the number of queries for Laplace mechanism under differential privacy[J]. Information Sciences, 2019, 503: 219-237. doi: 10.1016/j.ins.2019.07.001 [25] HUA J F, ZHU H, WANG F W, et al. CINEMA:efficient and privacy-preserving online medical primary diagnosis with skyline query[J]. IEEE Internet of Things Journal, 2019, 6(2): 1450-1461. doi: 10.1109/JIOT.2018.2834156