1. bookVolume 2021 (2021): Issue 4 (October 2021)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Privacy-Preserving Approximate k-Nearest-Neighbors Search that Hides Access, Query and Volume Patterns

Published Online: 23 Jul 2021
Page range: 549 - 574
Received: 28 Feb 2021
Accepted: 16 Jun 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

We study the problem of privacy-preserving approximate kNN search in an outsourced environment — the client sends the encrypted data to an untrusted server and later can perform secure approximate kNN search and updates. We design a security model and propose a generic construction based on locality-sensitive hashing, symmetric encryption, and an oblivious map. The construction provides very strong security guarantees, not only hiding the information about the data, but also the access, query, and volume patterns. We implement, evaluate efficiency, and compare the performance of two concrete schemes based on an oblivious AVL tree and an oblivious BSkiplist.

Keywords

[1] G. Asharov, I. Komargodski, W.-K. Lin, K. Nayak, E. Peserico, and E. Shi. OptORAMa: Optimal Oblivious RAM. In A. Canteaut and Y. Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Lecture Notes in Computer Science, pages 403–432. Springer International Publishing, 2020. Search in Google Scholar

[2] E. Bernhardsson. Benchmarking Nearest Neighbors. https://github.com/erikbern/ann-benchmarks. Search in Google Scholar

[3] A. Boldyreva and N. Chenette. Efficient Fuzzy Search on Encrypted Data. In C. Cid and C. Rechberger, editors, Fast Software Encryption, Lecture Notes in Computer Science, pages 613–633. Springer, 2015. Search in Google Scholar

[4] A. Boldyreva and T. Tang. Privacy-Preserving Approximate k-Nearest-Neighbors Search that Hides Access, Query and Volume Patterns. Full version of this paper. IACR Cryptology ePrint Archive, 2021. Search in Google Scholar

[5] X. Cheng, S. Su, Y. Teng, and K. Xiao. Enabling Secure and Efficient kNN Query Processing over Encrypted Spatial Data in the Cloud. Security and Communication Networks, 8, 03 2015. Search in Google Scholar

[6] R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. In Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS ’06, pages 79–88. Association for Computing Machinery, 2006. Search in Google Scholar

[7] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG ’04, pages 253–262, New York, NY, USA, June 2004. Association for Computing Machinery. Search in Google Scholar

[8] W. Dong. LSHKIT: A C++ Locality Sensitive Hashing Library. http://lshkit.sourceforge.net. Search in Google Scholar

[9] Y. Elmehdwi, B. K. Samanthula, and W. Jiang. Secure k-Nearest Neighbor Query over Encrypted Data in Outsourced Environments. In 2014 IEEE 30th International Conference on Data Engineering, pages 664–675, March 2014. Search in Google Scholar

[10] C. Gentry, K. A. Goldman, S. Halevi, C. Julta, M. Raykova, and D. Wichs. Optimizing ORAM and Using It Efficiently for Secure Computation. In E. De Cristofaro and M. Wright, editors, Privacy Enhancing Technologies, Lecture Notes in Computer Science, pages 1–18. Springer, 2013. Search in Google Scholar

[11] A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, editors, VLDB’99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK, pages 518–529. Morgan Kauf-mann, 1999. Search in Google Scholar

[12] P. Grubbs, M.-S. Lacharite, B. Minaud, and K. G. Paterson. Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS ’18, pages 315–331. Association for Computing Machinery, 2018. Search in Google Scholar

[13] P. Grubbs, M.-S. Lacharité, B. Minaud, and K. G. Paterson. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks. In 2019 IEEE Symposium on Security and Privacy (SP), pages 1067–1083, 2019. Search in Google Scholar

[14] S. Har-Peled, P. Indyk, and R. Motwani. Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. Theory of computing, 8(1):321–350, 2012. Search in Google Scholar

[15] P. Indyk and R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, pages 604–613. Association for Computing Machinery, 1998. Search in Google Scholar

[16] S. Kamara and T. Moataz. Computationally Volume-Hiding Structured Encryption. In Y. Ishai and V. Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Lecture Notes in Computer Science, pages 183–213. Springer International Publishing, 2019. Search in Google Scholar

[17] S. Kamara, T. Moataz, and O. Ohrimenko. Structured Encryption and Leakage Suppression. In H. Shacham and A. Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Lecture Notes in Computer Science, pages 339–370. Springer International Publishing, 2018. Search in Google Scholar

[18] E. M. Kornaropoulos, C. Papamanthou, and R. Tamassia. Data Recovery on Encrypted Databases with k-Nearest Neighbor Query Leakage. In 2019 IEEE Symposium on Security and Privacy (SP), pages 1033–1050, 2019. Search in Google Scholar

[19] E. M. Kornaropoulos, C. Papamanthou, and R. Tamassia. The State of the Uniform: Attacks on Encrypted Databases Beyond the Uniform Query Distribution. In 2020 IEEE Symposium on Security and Privacy (SP), pages 1223–1240, 2020. Search in Google Scholar

[20] D. Micciancio. Oblivious Data Structures: Applications to Cryptography. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 456–464. Association for Computing Machinery, 1997. Search in Google Scholar

[21] P. Mishra, R. Poddar, J. Chen, A. Chiesa, and R. A. Popa. Oblix: An Efficient Oblivious Search Index. In 2018 IEEE Symposium on Security and Privacy (SP), pages 279–296, San Francisco, CA, May 2018. IEEE. Search in Google Scholar

[22] M. Naveed. The Fallacy of Composition of Oblivious RAM and Searchable Encryption. IACR Cryptology ePrint Archive, 2015:668, 2015. Search in Google Scholar

[23] Y. Peng, H. Li, J. Cui, J. Ma, and Y. Liu. Towards Secure Approximate k-Nearest Neighbor Query over Encrypted High-dimensional Data. IEEE Access, PP:1–1, 04 2018. Search in Google Scholar

[24] D. S. Roche, A. Aviv, and S. G. Choi. A Practical Oblivious Map Data Structure with Secure Deletion and History Independence. In 2016 IEEE Symposium on Security and Privacy (SP), pages 178–197, May 2016. Search in Google Scholar

[25] B. K. Samanthula, Y. Elmehdwi, and W. Jiang. k-Nearest Neighbor Classification over Semantically Secure Encrypted Relational Data. IEEE transactions on Knowledge and data engineering, 27(5):1261–1273, 2015. Search in Google Scholar

[26] G. Shakhnarovich, T. Darrell, and P. Indyk. Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing). The MIT press, 2006. Search in Google Scholar

[27] E. Stefanov, M. van Dijk, E. Shi, C. Fletcher, L. Ren, X. Yu, and S. Devadas. Path ORAM: An Extremely Simple Oblivious RAM Protocol. In Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, CCS ’13, pages 299–310. Association for Computing Machinery, 2013. Search in Google Scholar

[28] X. S. Wang, K. Nayak, C. Liu, T.-H. H. Chan, E. Shi, E. Stefanov, and Y. Huang. Oblivious Data Structures. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS ’14, pages 215–226. Association for Computing Machinery, 2014. Search in Google Scholar

[29] W. K. Wong, D. W.-l. Cheung, B. Kao, and N. Mamoulis. Secure kNN Computation on Encrypted Databases. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 139–152. ACM, 2009. Search in Google Scholar

[30] B. Yao, F. Li, and X. Xiao. Secure Nearest Neighbor Revisited. In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 733–744. IEEE, 2013. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo