Repetitive, Oblivious, and Unlinkable SkNN Over Encrypted-and-Updated Data on Cloud

Repetitive, Oblivious, and Unlinkable SkNN Over Encrypted-and-Updated Data on Cloud

Li, Meng (Hefei University of Technology)
Zhang, Mingwei (Hefei University of Technology)
Gao, Jianbo (Hefei University of Technology)
Lal, C. (TU Delft Cyber Security)
Conti, M. (TU Delft Cyber Security; Università degli Studi di Padova)
Alazab, Mamoun (Charles Darwin University)

Alcaraz, Cristina (editor)
Chen, Liqun (editor)
Li, Shujun (editor)
Samarati, Pierangela (editor)

2022

Location-Based Services (LBSs) depend on a Service Provider (SP) to store data owners’ geospatial data and to process data users’ queries. For example, a Yelp user queries the SP to retrieve the k nearest Starbucks by submitting her/his current location. It is well-acknowledged that location privacy is vital to users and several prominent Secure k Nearest Neighbor (SkNN) query processing schemes are proposed. We observe that no prior work addresses the requirement of repetitive query after index update and its privacy issue, i.e., how to match a data item from the cloud repetitively in an oblivious and unlinkable manner. Meanwhile, a malicious SP may skip some data items and recommend others due to unfair competition. In this work, we formally define the repetitive query and its privacy objectives and present an Repetitive, Oblivious, and Unlinkable SkNN scheme ROU. Specifically, we design a multi-level structure to organize locations to further improve search efficiency. Second, we integrate data item identity into the framework of existing SkNN query processing. Data owners encrypt their data item identity and location information into a secure index, and data users encrypt a customized identity range of a previously retrieved data item and location information into a token. Next, the SP uses the token to query the secure index to find the specific data item via privacy-preserving range querying. We formally prove the privacy of ROU in the random oracle model. We build a prototype based on a server to evaluate the performance with a real-world dataset. Experimental results show that ROU is efficient and practical in terms of computational cost, communication overhead, and result verification.

Cloud computing
Privacy
Repetitive query
SkNN

https://doi.org/10.4233/uuid:c1df60a5-07da-4513-a5d4-f57cc7dd05ce

https://doi.org/10.1007/978-3-031-15777-6_15

Springer

9783031157769

Information and Communications Security - 24th International Conference, ICICS 2022, Proceedings

24th International Conference on Information and Communications Security, ICICS 2022, 2022-09-05 → 2022-09-08, Canterbury, United Kingdom

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 0302-9743, 13407 LNCS

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

conference paper

© 2022 Meng Li, Mingwei Zhang, Jianbo Gao, C. Lal, M. Conti, Mamoun Alazab