The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Secure k-nearest neighbor query over encrypted data in outsourced environments
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Paillier, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_16 · Cited by 7,250
How to generate and exchange secrets
Yao, A. C.-C. (1986) · 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) · doi:10.1109/sfcs.1986.25 · Cited by 3,733
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Protocols for secure computations
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.88 · Cited by 2,661
Goldreich, O. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511721656 · Cited by 1,805
Order preserving encryption for numeric data
Agrawal, R., Kiernan, J., Srikant, R., & Xu, Y. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007632 · Cited by 1,206
Secure kNN computation on encrypted databases
Wong, W. K., Cheung, D. W.-L., Kao, B., & Mamoulis, N. (2009) · Proceedings of the 2009 ACM SIGMOD International Conference on Management of data · doi:10.1145/1559845.1559862 · Cited by 901
Private queries in location based services: anonymizers are not necessary
Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C., & Tan, K.-L. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376631 · Cited by 758
Multi-Dimensional Range Query over Encrypted Data
Shi, E., Bethencourt, J., Chan, T.-H. H., Song, D., & Perrig, A. (2007) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2007.29 · Cited by 552
Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation.
Islam, M. S., Kuzu, M., & Kantarcıoğlu, M. (2012) · Cited by 491
Data Management in the Cloud: Limitations and Opportunities.
Abadi, D. J. (2009) · IEEE Data(base) Engineering Bulletin · Cited by 456
A Provably Secure Additive and Multiplicative Privacy Homomorphism*
Domingo-Ferrer, J. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45811-5_37 · Cited by 281
Secure nearest neighbor revisited
Yao, B., Fei-Fei, L., & Xiao, X. (2013) · Proceedings - International Conference on Data Engineering · doi:10.1109/icde.2013.6544870 · Cited by 232
Secure multidimensional range queries over outsourced data
Hore, B., Mehrotra, S., Canim, M., & Kantarcioglu, M. (2012) · The VLDB Journal · doi:10.1007/s00778-011-0245-7 · Cited by 231
Building castles out of mud: practical access pattern privacy and correctness on untrusted storage
Williams, P., Sion, R., & Carbunar, B. (2008) · Proceedings of the 15th ACM conference on Computer and communications security · doi:10.1145/1455770.1455790 · Cited by 230
Efficient Privacy-Preserving k-Nearest Neighbor Search
Qi, Y., & Atallah, M. J. (2008) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2008.79 · Cited by 110
Aggregation Queries in the Database-As-a-Service Model
Mykletun, E., & Tsudik, G. (2006) · Lecture notes in computer science · doi:10.1007/11805588_7 · Cited by 99
Managing and accessing data in the cloud: Privacy risks and approaches
di Vimercati, S. D. C., Foresti, S., & Samarati, P. (2012) · International Conference on Risks and Security of Internet and Systems (CRiSIS) · doi:10.1109/crisis.2012.6378956 · Cited by 79
Secure k-NN computation on encrypted cloud data without sharing key with query users
Zhu, Y., Xu, R., & Takagi, T. (2013) · International Workshop on Security in Cloud Computing (SCC) · doi:10.1145/2484402.2484415 · Cited by 74
Privacy Preserving Nearest Neighbor Search
Shaneck, M., Kim, Y., & Kumar, V. (2006) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2006.133 · Cited by 66
An efficient and probabilistic secure bit-decomposition
Samanthula, B. K., Hu, C., & Jiang, W. (2013) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/2484313.2484386 · Cited by 54
Self-citationPrivacy Preserving Nearest Neighbor Search
Shaneck, M., Kim, Y., & Kumar, V. (2009) · Springer eBooks · doi:10.1007/978-0-387-88735-7_10 · Cited by 31
Cited by
Zhang, M., Chen, Y., & Lin, J. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3051060 · Cited by 120
FREED: An Efficient Privacy-Preserving Solution for Person Re-IDentification
Zhao, B., Li, Y., Liu, X., Pang, H. H., & Deng, R. H. (2022) · 2022 IEEE Conference on Dependable and Secure Computing (DSC) · doi:10.1109/dsc54232.2022.9888863 · Cited by 23
Metadata
- Authors
- Elmehdwi, Y., Samanthula, B. K., & Jiang, W.
- Venue
- 2014 IEEE 30th International Conference on Data Engineering
- Publisher
- IEEE
- Published
- 2014-03
- Pages
- 664-675
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2074356711
- Cited by
- 386
- References
- 22
- FWCI
- 28.78
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.