PRIVACY-PRESERVING K-NEAREST NEIGHBOUR INTERPOLATION METHOD IN AN OUTSOURCED ENVIRONMENT

Abstract

One of the most emerging computer technologies of this decade is cloud computing that allows data owners to outsource their storage and computing requirements. It enables data owners to avoid the costs of building and maintaining a private storage infrastructure. While outsourcing data to cloud promises significant benefits, it possesses substantial security and privacy concerns, especially when data stored in the cloud is sensitive and confidential, like a business plan. Encrypting the data before outsourcing can ensure privacy. However, it will be very difficult to process the cipher text created by the traditional encryption method. Considering this fact, we propose an efficient protocol that allows a query owner to retrieve the interpolation of the top k records from two different databases that are closest to a query point. Note that the databases are stored in two different cloud service providers in encrypted form. We also show that the proposed protocol ensures the privacy and the security of the data and the query point.

Keywords

• Spatial interpolation,k-NN,privacy – preserving,homomorphic encryption

References

1. M. Armbrust, et al., A view of cloud computing, Communications of the ACM, 53/4 (2010) 50-58.
2. T. Ermakova, B. Fabian, and R. Zarnekow, Security and privacy system requirements for adopting cloud computing in healthcare data sharing scenarios, Proceedings of the Nineteenth Americas Conference on Information Systems (2013).
3. K. Hashizume, et al., An analysis of security issues for cloud computing, Journal of Internet Services and Applications, 4/1 (2013).
4. J.J. Rodrigues, et al., Analysis of the security and privacy requirements of cloud-based electronic health records systems, Journal of Medical Internet Research, 15/8 (2013).
5. M.D. Ryan, Cloud computing security: The scientific challenge, and a survey of solutions, Journal of Systems and Software, 86/9 (2013) 2263-2268.
6. K. Ren, C. Wang, and Q. Wang, Security challenges for the public cloud, IEEE Internet Computing, 16/1 (2012) 69-73.
7. C. Shahabi, et al., Privacy-preserving inference of social relationships from location data: a vision paper, Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, 9 (2015) 1-4.
8. J. Daemen, and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Springer Berlin Heidelberg, (2013).

9. D.X. Song, D. Wagner, and A. Perrig, Practical techniques for searches on encrypted data, Proceeding 2000 IEEE Symposium on Security and Privacy, (2000) 44-55.
10. W.K. Wong, et al., Secure kNN computation on encrypted databases, Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, (2009) 139-152.
11. Y. Qi and M.J. Atallah, Efficient privacy-preserving k-nearest neighbor search, The 28th International Conference on Distributed Computing Systems. (2008) 311-319.
12. M.R. Kalideen, and B. Tugrul, Outsourcing of Secure k-Nearest Neighbours Interpolation Method, International Journal of Advanced Computer Science and Applications, 9/4 (2018) 319-323.
13. J. Peng, K. K. R. Choo, and H. Ashman, Bit-level n-gram based forensic authorship analysis on social media: Identifying individuals from linguistic profiles, Journal of Network and Computer Applications, 70 (2016) 171-182.
14. B. Hore, et al., Secure multidimensional range queries over outsourced data, The VLDB Journal, 21/3 (2012) 333-358.
15. B. Hore, S. Mehrotra, and G. Tsudik, A privacy-preserving index for range queries, Proceedings of the Thirtieth International Conference on Very Large Data Bases -Volume 30, (2004) 720-731.
16. H. Hacıgümüş, B. Iyer, and S. Mehrotra, Efficient execution of aggregation queries over encrypted relational databases, International Conference on Database Systems for Advanced Applications, (2004) 125-136.
17. E. Mykletun and G. Tsudik, Aggregation queries in the database-as-a-service model, IFIP Annual Conference on Data and Applications Security and Privacy, (2006) 89-103.
18. H. Hu, et al., Processing private queries over untrusted data cloud through privacy homomorphism, IEEE 27th International Conference on Data Engineering (ICDE), (2011) 601-612.
19. B. Yao, F. Li, and X. Xiao, Secure nearest neighbor revisited, IEEE 29th International Conference on Data Engineering (ICDE). (2013) 733-744.
20. Y. Zhu, R. Xu, and T. Takagi, Secure k-NN computation on encrypted cloud data without sharing key with query users, Proceedings of the 2013 International Workshop on Security in Cloud Computing. (2013) 55-60.
21. J. Domingo-Ferrer, A provably secure additive and multiplicative privacy homomorphism, International Conference on Information Security. (2002) 471-483.
22. M. Shaneck, Y. Kim, and V. Kumar, Privacy preserving nearest neighbor search, Machine Learning in Cyber Trust. (2009) 247-276.
23. J. Vaidya and C. Clifton, Privacy-preserving top-k queries, 21st International Conference on Data Engineering (ICDE'05), (2005) 545-546.
24. G. Ghinita, et al., Private Queries in Location Based Services: Anonymizers Are Not Necessary, Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, (2008) 121-132.
25. X. Yi, R. Paulet, and E. Bertino, Homomorphic Encryption and Applications, (2014) Springer.
26. Y. Elmehdwi, B.K. Samanthula, and W. Jiang, Secure k-nearest neighbor query over encrypted data in outsourced environments, 2014 IEEE 30th International Conference on Data Engineering (ICDE), (2014) 664-675.