HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Enhancing the Performance of Spatial Queries on Encrypted Data Through Graph Embedding

Abstract : Most online mobile services make use of location data to improve customer experience. Mobile users can locate points of interest near them, or can receive recommendations tailored to their whereabouts. However, serious privacy concerns arise when location data is revealed in clear to service providers. Several solutions employ Searchable Encryption (SE) to evaluate spatial predicates directly on location ciphertexts. While doing so preserves privacy, the performance overhead incurred is high. We focus on a prominent SE technique in the public-key setting – Hidden Vector Encryption (HVE), and propose a graph embedding technique to encode location data in a way that significantly boosts the performance of processing on ciphertexts. We show that finding the optimal encoding is NP-hard, and provide several heuristics that are fast and obtain significant performance gains. Our extensive experimental evaluation shows that our solutions can improve computational overhead by a factor of two compared to the baseline.
Document type :
Conference papers
Complete list of metadata

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, May 31, 2021 - 5:34:02 PM
Last modification on : Monday, May 31, 2021 - 6:09:11 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2023-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



Sina Shaham, Gabriel Ghinita, Cyrus Shahabi. Enhancing the Performance of Spatial Queries on Encrypted Data Through Graph Embedding. 34th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jun 2020, Regensburg, Germany. pp.289-309, ⟨10.1007/978-3-030-49669-2_17⟩. ⟨hal-03243626⟩



Record views