Privacy-Preserving Approximate k-Nearest-Neighbors Search that Hides Access, Query and Volume Patterns
Authors: Alexandra Boldyreva (Georgia Institute of Technology, USA), Tianxin Tang (Georgia Institute of Technology, USA)
Volume: 2021
Issue: 4
Pages: 549–574
DOI: https://doi.org/10.2478/popets-2021-0084
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: oblivious data structures, locality-sensitive hashing, approximate kNN, search on encrypted data.
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
