Paper 2021/816

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

Alexandra Boldyreva and Tianxin Tang


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.PETS 2021
oblivious data structureslocality-sensitive hashingapproximate kNNsearch on encrypted data
Contact author(s)
sasha @ gatech edu
ttang @ gatech edu
2021-06-16: received
Short URL
Creative Commons Attribution


      author = {Alexandra Boldyreva and Tianxin Tang},
      title = {Privacy-Preserving Approximate k-Nearest-Neighbors Search that Hides Access, Query and Volume Patterns},
      howpublished = {Cryptology ePrint Archive, Paper 2021/816},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.