An Efficient and Secure Location-based Alert Protocol using Searchable Encryption and Huffman Codes
An Efficient and Secure Location-based Alert Protocol using Searchable Encryption and Huffman Codes
复制标题
DOI：
10.5441/002/edbt.2021.24
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Sina Shaham;G. Ghinita;C. Shahabi
中科院分区：
文献类型：
--
作者：
Sina Shaham;G. Ghinita;C. Shahabi
位置数据广泛用于移动的应用程序中，从基于位置的推荐到社交媒体和导航。一种特定类型的交互是基于位置的警报，其中移动的用户订阅服务提供商（SP），以便在附近发生某个事件时得到通知。例如，考虑到正在进行的COVID-19大流行，接触者追踪被选为控制病毒传播的有效手段。用户希望在接近受感染者时得到通知。然而，如果用户以明文与SP共享其位置历史，则会出现严重的隐私问题。为了解决隐私问题，最近的工作提出了几个协议，可以安全地实现基于位置的警报。用户将其加密位置上传到SP，位置谓词的评估直接在密文上完成。当某个个体被报告为感染时，找到所有匹配的密文（例如，根据诸如“在最近一周内被感染的患者访问的任何位置的10英尺附近”的谓词），并且通知相应的用户。然而，存在与现有协议相关联的显著性能问题。在密文上执行匹配所需的底层可搜索加密原语是昂贵的，并且如果没有对位置和搜索谓词进行适当的编码，性能可能会降低很多。本文提出了一种基于霍夫曼码的变长位置编码方法。通过控制表示加密位置和相应匹配谓词所需的长度，我们能够显著提高性能。我们提供了一个理论分析，通过使用霍夫曼码实现的增益，我们通过大量的实验表明，与固定长度的编码方法相比，改进是实质性的。© 2021版权归所有者/作者所有。
Location data are widely used in mobile apps, ranging from location-based recommendations, to social media and navigation. A specific type of interaction is that of location-based alerts, where mobile users subscribe to a service provider (SP) in order to be notified when a certain event occurs nearby. Consider, for instance, the ongoing COVID-19 pandemic, where contact tracing has been singled out as an effective means to control the virus spread. Users wish to be notified if they came in proximity to an infected individual. However, serious privacy concerns arise if the users share their location history with the SP in plaintext. To address privacy, recent work proposed several protocols that can securely implement location-based alerts. The users upload their encrypted locations to the SP, and the evaluation of location predicates is done directly on ciphertexts. When a certain individual is reported as infected, all matching ciphertexts are found (e.g., according to a predicate such as “10 feet proximity to any of the locations visited by the infected patient in the last week”), and the corresponding users notified. However, there are significant performance issues associated with existing protocols. The underlying searchable encryption primitives required to perform the matching on ciphertexts are expensive, and without a proper encoding of locations and search predicates, the performance can degrade a lot. In this paper, we propose a novel method for variable-length location encoding based on Huffman codes. By controlling the length required to represent encrypted locations and the corresponding matching predicates, we are able to significantly speed up performance. We provide a theoretical analysis of the gain achieved by using Huffman codes, and we show through extensive experiments that the improvement compared with fixed-length encoding methods is substantial. © 2021 Copyright held by the owner/author(s).