Secure k-nearest neighbor query over encrypted data in outsourced environments

Yousef Elmehdwi, Bharath Kumar Samanthula, Wei Jiang

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

135 Citations (Scopus)

Abstract

For the past decade, query processing on relational data has been studied extensively, and many theoretical and practical solutions to query processing have been proposed under various scenarios. With the recent popularity of cloud computing, users now have the opportunity to outsource their data as well as the data management tasks to the cloud. However, due to the rise of various privacy issues, sensitive data (e.g., medical records) need to be encrypted before outsourcing to the cloud. In addition, query processing tasks should be handled by the cloud; otherwise, there would be no point to outsource the data at the first place. To process queries over encrypted data without the cloud ever decrypting the data is a very challenging task. In this paper, we focus on solving the k-nearest neighbor (kNN) query problem over encrypted database outsourced to a cloud: a user issues an encrypted query record to the cloud, and the cloud returns the k closest records to the user. We first present a basic scheme and demonstrate that such a naive solution is not secure. To provide better security, we propose a secure kNN protocol that protects the confidentiality of the data, user's input query, and data access patterns. Also, we empirically analyze the efficiency of our protocols through various experiments. These results indicate that our secure protocol is very efficient on the user end, and this lightweight scheme allows a user to use any mobile device to perform the kNN query.

Original languageEnglish
Title of host publication2014 IEEE 30th International Conference on Data Engineering, ICDE 2014
PublisherIEEE Computer Society
Pages664-675
Number of pages12
ISBN (Print)9781479925544
DOIs
StatePublished - 1 Jan 2014
Event30th IEEE International Conference on Data Engineering, ICDE 2014 - Chicago, IL, United States
Duration: 31 Mar 20144 Apr 2014

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Other

Other30th IEEE International Conference on Data Engineering, ICDE 2014
CountryUnited States
CityChicago, IL
Period31/03/144/04/14

Fingerprint

Query processing
Outsourcing
Cloud computing
Mobile devices
Information management
Experiments

Cite this

Elmehdwi, Y., Samanthula, B. K., & Jiang, W. (2014). Secure k-nearest neighbor query over encrypted data in outsourced environments. In 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014 (pp. 664-675). [6816690] (Proceedings - International Conference on Data Engineering). IEEE Computer Society. https://doi.org/10.1109/ICDE.2014.6816690
Elmehdwi, Yousef ; Samanthula, Bharath Kumar ; Jiang, Wei. / Secure k-nearest neighbor query over encrypted data in outsourced environments. 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014. IEEE Computer Society, 2014. pp. 664-675 (Proceedings - International Conference on Data Engineering).
@inproceedings{e009c3b7eda14c1184dffde1557c6ffd,
title = "Secure k-nearest neighbor query over encrypted data in outsourced environments",
abstract = "For the past decade, query processing on relational data has been studied extensively, and many theoretical and practical solutions to query processing have been proposed under various scenarios. With the recent popularity of cloud computing, users now have the opportunity to outsource their data as well as the data management tasks to the cloud. However, due to the rise of various privacy issues, sensitive data (e.g., medical records) need to be encrypted before outsourcing to the cloud. In addition, query processing tasks should be handled by the cloud; otherwise, there would be no point to outsource the data at the first place. To process queries over encrypted data without the cloud ever decrypting the data is a very challenging task. In this paper, we focus on solving the k-nearest neighbor (kNN) query problem over encrypted database outsourced to a cloud: a user issues an encrypted query record to the cloud, and the cloud returns the k closest records to the user. We first present a basic scheme and demonstrate that such a naive solution is not secure. To provide better security, we propose a secure kNN protocol that protects the confidentiality of the data, user's input query, and data access patterns. Also, we empirically analyze the efficiency of our protocols through various experiments. These results indicate that our secure protocol is very efficient on the user end, and this lightweight scheme allows a user to use any mobile device to perform the kNN query.",
author = "Yousef Elmehdwi and Samanthula, {Bharath Kumar} and Wei Jiang",
year = "2014",
month = "1",
day = "1",
doi = "10.1109/ICDE.2014.6816690",
language = "English",
isbn = "9781479925544",
series = "Proceedings - International Conference on Data Engineering",
publisher = "IEEE Computer Society",
pages = "664--675",
booktitle = "2014 IEEE 30th International Conference on Data Engineering, ICDE 2014",

}

Elmehdwi, Y, Samanthula, BK & Jiang, W 2014, Secure k-nearest neighbor query over encrypted data in outsourced environments. in 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014., 6816690, Proceedings - International Conference on Data Engineering, IEEE Computer Society, pp. 664-675, 30th IEEE International Conference on Data Engineering, ICDE 2014, Chicago, IL, United States, 31/03/14. https://doi.org/10.1109/ICDE.2014.6816690

Secure k-nearest neighbor query over encrypted data in outsourced environments. / Elmehdwi, Yousef; Samanthula, Bharath Kumar; Jiang, Wei.

2014 IEEE 30th International Conference on Data Engineering, ICDE 2014. IEEE Computer Society, 2014. p. 664-675 6816690 (Proceedings - International Conference on Data Engineering).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - Secure k-nearest neighbor query over encrypted data in outsourced environments

AU - Elmehdwi, Yousef

AU - Samanthula, Bharath Kumar

AU - Jiang, Wei

PY - 2014/1/1

Y1 - 2014/1/1

N2 - For the past decade, query processing on relational data has been studied extensively, and many theoretical and practical solutions to query processing have been proposed under various scenarios. With the recent popularity of cloud computing, users now have the opportunity to outsource their data as well as the data management tasks to the cloud. However, due to the rise of various privacy issues, sensitive data (e.g., medical records) need to be encrypted before outsourcing to the cloud. In addition, query processing tasks should be handled by the cloud; otherwise, there would be no point to outsource the data at the first place. To process queries over encrypted data without the cloud ever decrypting the data is a very challenging task. In this paper, we focus on solving the k-nearest neighbor (kNN) query problem over encrypted database outsourced to a cloud: a user issues an encrypted query record to the cloud, and the cloud returns the k closest records to the user. We first present a basic scheme and demonstrate that such a naive solution is not secure. To provide better security, we propose a secure kNN protocol that protects the confidentiality of the data, user's input query, and data access patterns. Also, we empirically analyze the efficiency of our protocols through various experiments. These results indicate that our secure protocol is very efficient on the user end, and this lightweight scheme allows a user to use any mobile device to perform the kNN query.

AB - For the past decade, query processing on relational data has been studied extensively, and many theoretical and practical solutions to query processing have been proposed under various scenarios. With the recent popularity of cloud computing, users now have the opportunity to outsource their data as well as the data management tasks to the cloud. However, due to the rise of various privacy issues, sensitive data (e.g., medical records) need to be encrypted before outsourcing to the cloud. In addition, query processing tasks should be handled by the cloud; otherwise, there would be no point to outsource the data at the first place. To process queries over encrypted data without the cloud ever decrypting the data is a very challenging task. In this paper, we focus on solving the k-nearest neighbor (kNN) query problem over encrypted database outsourced to a cloud: a user issues an encrypted query record to the cloud, and the cloud returns the k closest records to the user. We first present a basic scheme and demonstrate that such a naive solution is not secure. To provide better security, we propose a secure kNN protocol that protects the confidentiality of the data, user's input query, and data access patterns. Also, we empirically analyze the efficiency of our protocols through various experiments. These results indicate that our secure protocol is very efficient on the user end, and this lightweight scheme allows a user to use any mobile device to perform the kNN query.

UR - http://www.scopus.com/inward/record.url?scp=84901750940&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2014.6816690

DO - 10.1109/ICDE.2014.6816690

M3 - Conference contribution

SN - 9781479925544

T3 - Proceedings - International Conference on Data Engineering

SP - 664

EP - 675

BT - 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014

PB - IEEE Computer Society

ER -

Elmehdwi Y, Samanthula BK, Jiang W. Secure k-nearest neighbor query over encrypted data in outsourced environments. In 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014. IEEE Computer Society. 2014. p. 664-675. 6816690. (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2014.6816690