TY - GEN
T1 - Enhancing the performance of spatial queries on encrypted data through graph embedding
AU - Shaham, Sina
AU - Ghinita, Gabriel
AU - Shahabi, Cyrus
N1 - Publisher Copyright:
© IFIP International Federation for Information Processing 2020.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Graph embedding
KW - Hidden Vector Encryption
UR - http://www.scopus.com/inward/record.url?scp=85087528630&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-49669-2_17
DO - 10.1007/978-3-030-49669-2_17
M3 - Conference contribution
AN - SCOPUS:85087528630
SN - 9783030496685
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 289
EP - 309
BT - Data and Applications Security and Privacy - 34th Annual IFIP WG 11.3 Conference, DBSec 2020, Proceedings
A2 - Singhal, Anoop
A2 - Vaidya, Jaideep
PB - Springer
T2 - 34th Annual IFIP WG11.3 Conference on Data and Applications Security and Privacy, DBSec 2020
Y2 - 25 June 2020 through 26 June 2020
ER -