TY - JOUR
T1 - FastGeo
T2 - Efficient Geometric Range Queries on Encrypted Spatial Data
AU - Wang, Boyang
AU - Li, Ming
AU - Xiong, Li
N1 - Funding Information:
Dr. Ming Li was supported in part by the U.S. National Science Foundation through the Division of Computer and Network Systems under Grant CNS-1218085 and in part by Amazon Web Services, Inc. Dr. Li Xiong was supported in part by the U.S. National Science Foundation through the Division of Computer and Network Systems under Grant CNS-1618932 and in part by Air Force Office of Scientific Research (AFOSR) DDDAS program under grant FA9550-17-1-0006.
Publisher Copyright:
© 2004-2012 IEEE.
PY - 2019/3/1
Y1 - 2019/3/1
N2 - Spatial data have wide applications, e.g., location-based services, and geometric range queries (i.e., finding points inside geometric areas, e.g., circles or polygons) are one of the fundamental search functions over spatial data. The rising demand of outsourcing data is moving large-scale datasets, including large-scale spatial datasets, to public clouds. Meanwhile, due to the concern of insider attackers and hackers on public clouds, the privacy of spatial datasets should be cautiously preserved while querying them at the server side, especially for location-based and medical usage. In this paper, we formalize the concept of Geometrically Searchable Encryption, and propose an efficient scheme, named FastGeo, to protect the privacy of clients' spatial datasets stored and queried at a public server. With FastGeo, which is a novel two-level search for encrypted spatial data, an honest-but-curious server can efficiently perform geometric range queries, and correctly return data points that are inside a geometric range to a client without learning sensitive data points or this private query. FastGeo supports arbitrary geometric areas, achieves sublinear search time, and enables dynamic updates over encrypted spatial datasets. Our scheme is provably secure, and our experimental results on real-world spatial datasets in cloud platform demonstrate that FastGeo can boost search time over 100 times.
AB - Spatial data have wide applications, e.g., location-based services, and geometric range queries (i.e., finding points inside geometric areas, e.g., circles or polygons) are one of the fundamental search functions over spatial data. The rising demand of outsourcing data is moving large-scale datasets, including large-scale spatial datasets, to public clouds. Meanwhile, due to the concern of insider attackers and hackers on public clouds, the privacy of spatial datasets should be cautiously preserved while querying them at the server side, especially for location-based and medical usage. In this paper, we formalize the concept of Geometrically Searchable Encryption, and propose an efficient scheme, named FastGeo, to protect the privacy of clients' spatial datasets stored and queried at a public server. With FastGeo, which is a novel two-level search for encrypted spatial data, an honest-but-curious server can efficiently perform geometric range queries, and correctly return data points that are inside a geometric range to a client without learning sensitive data points or this private query. FastGeo supports arbitrary geometric areas, achieves sublinear search time, and enables dynamic updates over encrypted spatial datasets. Our scheme is provably secure, and our experimental results on real-world spatial datasets in cloud platform demonstrate that FastGeo can boost search time over 100 times.
KW - encrypted data
KW - geometric range queries
KW - privacy
KW - Spatial data
UR - http://www.scopus.com/inward/record.url?scp=85056064268&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056064268&partnerID=8YFLogxK
U2 - 10.1109/TDSC.2017.2684802
DO - 10.1109/TDSC.2017.2684802
M3 - Article
AN - SCOPUS:85056064268
VL - 16
SP - 245
EP - 258
JO - IEEE Transactions on Dependable and Secure Computing
JF - IEEE Transactions on Dependable and Secure Computing
SN - 1545-5971
IS - 2
M1 - 7882697
ER -