Manara - Qatar Research Repository
Browse

Supporting secure dynamic alert zones using searchable encryption and graph embedding

Download (1.84 MB)
journal contribution
submitted on 2023-12-28, 10:40 and posted on 2023-12-28, 10:43 authored by Sina Shaham, Gabriel Ghinita, Cyrus Shahabi

Location-based alerts have gained increasing popularity in recent years, whether in the context of healthcare (e.g., COVID-19 contact tracing), marketing (e.g., location-based advertising), or public safety. However, serious privacy concerns arise when location data are used in clear in the process. Several solutions employ searchable encryption (SE) to achieve secure alerts directly on encrypted locations. 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, 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 the optimal encoding is NP-hard, and we provide three heuristics that obtain significant performance gains: gray optimizer, multi-seed gray optimizer and scaled gray optimizer. Furthermore, we investigate the more challenging case of dynamic alert zones, where the area of interest changes over time. Our extensive experimental evaluation shows that our solutions can significantly improve computational overhead compared to existing baselines.

Other Information

Published in: The VLDB Journal
License: https://creativecommons.org/licenses/by/4.0
See article on publisher's website: https://dx.doi.org/10.1007/s00778-023-00803-2

Funding

Open Access funding provided by the Qatar National Library.

History

Language

  • English

Publisher

Springer Nature

Publication Year

  • 2023

License statement

This Item is licensed under the Creative Commons Attribution 4.0 International License.

Institution affiliated with

  • Hamad Bin Khalifa University
  • College of Science and Engineering - HBKU

Usage metrics

    College of Science and Engineering - HBKU

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC