Tianxin Tang - Provably-Secure Approximate k-NN Search Protocol

This talk examines 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 man. The construction provides very strong security guarantees, not only hiding the information about the data, but also the access, query, and volume patterns.