Optimizing and Accelerating Privacy Protection Algorithm for Real-Time Location

Dong Kai; Wang Lifu; Ling Zhen

doi:10.7544/issn1000-1239.202330877

Journal of Computer Research and Development > 2024 > 61(9): 2156-2169. > DOI: 10.7544/issn1000-1239.202330877 CSTR: 32373.14.issn1000-1239.202330877

Dong Kai, Wang Lifu, Ling Zhen. Optimizing and Accelerating Privacy Protection Algorithm for Real-Time Location[J]. Journal of Computer Research and Development, 2024, 61(9): 2156-2169. DOI: 10.7544/issn1000-1239.202330877

Citation:

PDF (3160 KB)

Optimizing and Accelerating Privacy Protection Algorithm for Real-Time Location

School of Computer Science and Engineering, Southeast University, Nanjing 211189

Funds: This work was supported by the National Natural Science Foundation of China (62072098, 62022024, 62072103, 62072102, 62132009, 62061146001), the Jiangsu Key Research and Development Program (BE2022065-5, BE2022680), the Project of Jiangsu Provincial Key Laboratory of Network and Information Security (BM2003201), the Project of Key Laboratory of Computer Network and Information Integration of Ministry of Education of China (93K-9), and the Project of Collaborative Innovation Center of Novel Software Technology and Industrialization.

More Information

Author Bio:
Dong Kai: born in 1985. PhD, associate professor. His main research interests include privacy protection, AI security, and IoT

Wang Lifu: born in 2002. Bachelor. His main research interests include IoT and trigger action programming

Ling Zhen: born in 1982. PhD, professor. His main research interests include IoT, system security, privacy protection, and trusted computing
Received Date: October 30, 2023
Revised Date: May 19, 2024
Available Online: June 03, 2024

Graphical Abstract

Abstract

Abstract

Existing electric vehicle API platforms (e.g., SmartCar), use access control mechanisms to preserve users’ privacy. To preserve location privacy and meanwhile enable functionality of untrustworthy location-based services, a location privacy preserving mechanism (LPPM) can be used to generate a random pseudo-location as a reported location based on a user’s true location. Existing techniques solve an optimization problem on a discrete grid, to construct an optimal LPPM which achieves the highest privacy bounded by minimum tolerable utility, or vice versa. However, they cannot be applied to real-time electric vehicle scenarios since the running time required to generate an optimal LPPM is too long (which can be several days). Another problem deals with optimality of constructed LPPMs. We reveal unexpected cases (anomaly) when the optimal LPPM constructed on a fine grid with superior granularity is worse than that on a coarse one with inferior granularity. We introduce granularity independence as a formal treatment, and propose an optimal LPPM named Divide-and-Coin which can be performed on the fly. Divide-and-Coin improves the running time from at least O ( ${n}^{2.055}$ ) to O ( $\mathrm{l}\mathrm{o}\mathrm{g}\;n$ ), where n is the number of reported locations. Our experimental results show that Divide-and-Coin generates an optimal building-level reported location from a city-level area within one second.

FullText(HTML)

References (42)

References

[1]	Monta. The charging platform built to EV bettry [EB/OL]. [2022-07-20]. https://monta.com
[2]	EvDotEnergy. Plug into bettey [EB/OL]. [2022-07-20]. https://ev.energy
[3]	Hyundai Motor Company. BlueLink live services [EB/OL]. [2022-07-20].https://www.hyundai.com/eu/driving-hyundai/owning-a-hyundai/bluelink-connectivity/live-services.html
[4]	EasyPark. Making cities more livable [EB/OL]. [2022-07-20]. https://easyparkgroup.com
[5]	Freetrailer. Rent a trailer for free with freetrailer [EB/OL]. [2022-07-20]. https://freetrailer.com
[6]	SmartCar. Easiest way to integrate apps cars [EB/OL]. [2022-07-20]. https://smartcar.com
[7]	Jiang Hongbo, Li Jie, Zhao Ping, et al. Location privacy-preserving mechanisms in location-based services: A comprehensive survey[J]. ACM Computing Surveys, 2021, 54(1): 1−36
[8]	Zhang Yinghui, Zou Jian, Guo Rui. Efficient privacy-preserving authentication for V2G networks[J]. Peer-to-Peer Networking and Applications, 2021, 14(3): 1−13
[9]	Bordenabe N, Chatzikokolakis K, Palamidessi C. Optimal geo-indistinguishable mechanisms for location privacy[C]//Proc of the 2014 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2014: 251–262
[10]	Shokri R, Theodorakopoulos G, Troncoso C, et al. Protecting location privacy: Optimal strategy against localization attacks[C]//Proc of the 2012 ACM Conf on Computer and Communications Security. New York: ACM, 2012: 617–627
[11]	Chatzikokolakis K, ElSalamouny E, Palamidessi C. Efficient utility improvement for location privacy[J]. Privacy Enhancing Technologies, 2017, 2017(4): 308−328
[12]	Shokri R. Privacy games: Optimal user-centric data obfuscation[J]. arXiv preprint, arXiv:1402.3426, 2014
[13]	Oya S, Troncoso C, Pérez-González F. Back to the drawing board: Revisiting the design of optimal location privacy-preserving mechanisms[C]//Proc of the 2017 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2017: 1959−1972
[14]	崔杰,陈学峰,张静,等. 基于公交车缓存的车联网位置隐私保护方案[J]. 通信学报,2021,42(7):150−161 doi: 10.11959/j.issn.1000-436x.2021132 Cui Jie, Chen Xuefeng, Zhang Jing, et al. Bus cache-based location privacy protection scheme in the Internet of vehicles[J]. Journal on Communications, 2021, 42(7): 150−161 (in Chinese) doi: 10.11959/j.issn.1000-436x.2021132
[15]	李洪涛,任晓宇,王洁,等. 基于差分隐私的连续位置隐私保护机制[J]. 通信学报,2021,42(8):164−175 doi: 10.11959/j.issn.1000-436x.2021123 Li Hongtao, Ren Xiaoyu, Wang Jie, et al. Continuous location privacy protection mechanism based on differential privacy[J]. Journal on Communications, 2021, 42(8): 164−175 (in Chinese) doi: 10.11959/j.issn.1000-436x.2021123
[16]	Shokri R, Theodorakopoulos G, Le Boudec J Y, et al. Quantifying location privacy[C]//Proc of the 2011 IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2011: 247−262
[17]	Andrés M E, Bordenabe N E, Chatzikokolakis K, et al. Geo-indistinguishability: Differential privacy for location-based systems[C]//Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 901−914
[18]	王斌,张磊,张国印. 敏感渐进不可区分的位置隐私保护[J]. 计算机研究与发展,2020,57(3):616−630 doi: 10.7544/issn1000-1239.2020.20190086 Wang Bin, Zhang Lei, Zhang Guoyin. A gradual sensitive indistinguishable based location privacy protection scheme[J]. Journal of Computer Research and Development, 2020, 57(3): 616−630 (in Chinese) doi: 10.7544/issn1000-1239.2020.20190086
[19]	Kim J W, Edemacu K, Jang B. Privacy-preserving mechanisms for location privacy in mobile crowdsensing: A survey[J]. Journal of Network and Computer Applications, 2022, 200: 103315
[20]	Zhao Dapeng, Jin Yuanyuan, Zhang Kai, et al. EPLA: Efficient personal location anonymity[J]. GeoInformatica, 2018, 22(1): 29−47 doi: 10.1007/s10707-017-0303-4
[21]	Niu Ben, Li Qinghua, Zhu Xiaoyan, et al. Achieving k-anonymity in privacy-aware location-based services[C]//Proc of the 2014 IEEE Conf on Computer Communications. Piscataway, NJ: IEEE , 2014: 754−762
[22]	Sweeney L. K-anonymity: A model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557−570 doi: 10.1142/S0218488502001648
[23]	Wang Leye, Yang Dingqi, Han Xiao, et al. Location privacy-preserving task allocation for mobile crowdsensing with differential geo-obfuscation[C]//Proc of the 26th Int Conf on World Wide Web. New York: ACM, 2017: 627–636
[24]	To H, Shahabi C, Li Xiong. Privacy-preserving online task assignment in spatial crowdsourcing with untrusted server[C]//Proc of IEEE 34th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2018: 833−844
[25]	Hua Jingyu, Tong Wei, Xu Fengyuan, et al. A geo-indistinguishable location perturbation mechanism for location-based services supporting frequent queries[J]. IEEE Transactions on Information Forensics and Security, 2017, 13(5): 1155−1168
[26]	Yu Lei, Liu Ling, Pu C. Dynamic differential location privacy with personalized error bounds[C/OL]//Proc of NDSS. 2017 [2022-07-20].https://www.eecis.udel.edu/~ruizhang/CISC859/S17/Paper/p28.pdf
[27]	Dong Kai, Guo Taolin, Ye Haibo, et al. On the limitations of existing notions of location privacy[J]. Future Generation Computer Systems, 2018, 86: 1513−1522 doi: 10.1016/j.future.2017.05.045
[28]	Jiang Shunhua, Song Zhao, Weinstein O, et al. Faster dynamic matrix inverse for faster LPS[J]. arXiv preprint, arXiv:2004.07470, 2020
[29]	Zheng Yu, Xie Xing, Ma Weiying. Geolife: A collaborative social networking service among user, location and trajectory[J]. IEEE Data Engineering Bulletin, 2010, 33(2): 32−39
[30]	Mendes R, Cunha M, Vilela J P. Impact of frequency of location reports on the privacy level of geo-indistinguishability[J]. Proceedings on Privacy Enhancing Technologies, 2020, 2020(2): 379−396
[31]	Zhang Wenjing, Li Ming, Tandon R, et al. Online location trace privacy: An information theoretic approach[J]. IEEE Transactions on Information Forensics and Security, 2018, 14(1): 235−250
[32]	He Xiaofan, Jin Richeng, Dai Huaiyu. Leveraging spatial diversity for privacy-aware location-based services in mobile networks[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(6): 1524−1534 doi: 10.1109/TIFS.2018.2797023
[33]	Gursoy M E, Liu Ling, Truex S, et al. Utility-aware synthesis of differentially private and attack-resilient location traces[C]//Proc of the 2018 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2018: 196−211
[34]	Terrovitis M, Poulis G, Mamoulis N, et al. Local suppression and splitting techniques for privacy preserving publication of trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(7): 1466−1479 doi: 10.1109/TKDE.2017.2675420
[35]	Oya S, Troncoso C, Pérez-González F. Rethinking location privacy for unknown mobility behaviors[C]//Proc of the 2019 IEEE European Symp on Security and Privacy (EuroS&P). Piscataway, NJ: IEEE, 2019: 416−431
[36]	Dwork C. Differential privacy[C/OL]//Proc of the Int Colloquium on Automata, Languages and Programming. Berlin: Springer, 2006 [2022-07-20].https://link.springer.com/chapter/10.1007/11787006_1
[37]	Chatzikokolakis K, Andrés M E, Bordenabe N E, et al. Broadening the scope of differential privacy using metrics[C]//Proc of the 13th Privacy Enhancing Technologies. Berlin: Springer, 2013: 82–102
[38]	Oya S, Troncoso C, Pérez-González F. Is geo-indistinguishability what you are looking for[C]//Proc of the 2017 Workshop on Privacy in the Electronic Society. New York: ACM, 2017: 137−140
[39]	Wang Weina, Ying Lei, Zhang Junshan. On the relation between identifiability, differential privacy, and mutual-information privacy[J]. IEEE Transactions on Information Theory, 2016, 62(9): 5018−5029 doi: 10.1109/TIT.2016.2584610
[40]	Campolo C, Iera A, Molinaro A, et al. Smartcar: An integrated smartphone-based platform to support traffic management applications[C/OL]//Proc of the 1st Int Workshop on Vehicular Traffic Management for Smart Cities. Piscataway, NJ: IEEE, 2012 [2022-07-20]. https://ieeexplore.ieee.org/abstract/document/6398700
[41]	Gao Feng, Zhu Leihuang, Shen Meng, et al. A blockchainbased privacy-preserving payment mechanism for vehicle-to-grid networks[J]. IEEE Network, 2018, 32(6): 184−192 doi: 10.1109/MNET.2018.1700269
[42]	Pazos-Revilla M, Alsharif A, Gunukula S, et al. Secure and privacy-preserving physical-layer-assisted scheme for ev dynamic charging system[J]. IEEE Transactions on Vehicular Technology, 2018, 67(4): 3304−3318 doi: 10.1109/TVT.2017.2780179

[1]	Shen Zhengchen, Zhang Qianli, Zhang Chaofan, Tang Xiangyu, Wang Jilong. Location Privacy Attack Based on Deep Learning[J]. Journal of Computer Research and Development, 2022, 59(2): 390-402. DOI: 10.7544/issn1000-1239.20200843
[2]	Feng Jingyu, Yang Jinwen, Zhang Ruitong, Zhang Wenbo. A Spectrum Sharing Incentive Scheme Against Location Privacy Leakage in IoT Networks[J]. Journal of Computer Research and Development, 2020, 57(10): 2209-2220. DOI: 10.7544/issn1000-1239.2020.20200453
[3]	Wang Ziye, Miao Duoqian, Zhao Cairong, Luo Sheng, Wei Zhihua. A Pedestrian Tracking Algorithm Based on Multi-Granularity Feature[J]. Journal of Computer Research and Development, 2020, 57(5): 996-1002. DOI: 10.7544/issn1000-1239.2020.20190280
[4]	Wang Bin, Zhang Lei, Zhang Guoyin. A Gradual Sensitive Indistinguishable Based Location Privacy Protection Scheme[J]. Journal of Computer Research and Development, 2020, 57(3): 616-630. DOI: 10.7544/issn1000-1239.2020.20190086
[5]	Pan Xiao, Chen Weizhang, Sun Yige, Wu Lei. Continuous Queries Privacy Protection Algorithm Based on Spatial-Temporal Similarity Over Road Networks[J]. Journal of Computer Research and Development, 2017, 54(9): 2092-2101. DOI: 10.7544/issn1000-1239.2017.20160551
[6]	Gu Shenming, Gu Jinyan, Wu Weizhi, Li Tongjun, Chen Chaojun. Local Optimal Granularity Selections in Incomplete Multi-Granular Decision Systems[J]. Journal of Computer Research and Development, 2017, 54(7): 1500-1509. DOI: 10.7544/issn1000-1239.2017.20160349
[7]	Zhou Changli, Ma Chunguang, Yang Songtao. Location Privacy-Preserving Method for LBS Continuous KNN Query in Road Networks[J]. Journal of Computer Research and Development, 2015, 52(11): 2628-2644. DOI: 10.7544/issn1000-1239.2015.20140532
[8]	Zhu Huaijie, Wang Jiaying, Wang Bin, and Yang Xiaochun. Location Privacy Preserving Obstructed Nearest Neighbor Queries[J]. Journal of Computer Research and Development, 2014, 51(1): 115-125.
[9]	Pan Xiao, Hao Xing, and Meng Xiaofeng. Privacy Preserving Towards Continuous Query in Location-Based Services[J]. Journal of Computer Research and Development, 2010, 47(1): 121-129.
[10]	Tang Huanling, Lin Zhengkui, Lu Mingyu, Wu Jun. An Advanced Co-Training Algorithm Based on Mutual Independence and Diversity Measures[J]. Journal of Computer Research and Development, 2008, 45(11): 1874-1881.