In this presentation, I will deal with the problem of privacy-preserving range queries, in the storage outsourcing environment. Specifically,
I will give a constant-round scheme for privacy-preserving range queries (whereas the previous best was logarithmic), at a cost of a logarithmic extra factor in the space complexity at the remote server. This is a worthwhile tradeoff in situations
where the remote server is much more powerful than the local client, and it is provably secure in the sense that the
remote server learns nothing about the data it stores or the client’s queries on that data (except the number of items that
satisfy the range query). In this presentation, I will introduce two novel techniques: The use of a bi-chromatic version of the dataset, and the judicious use of replication; both techniques are crucial for proving that the scheme does not leak information to the server. I will also talk about a secure solution to the nearest-neighbor problem where the server learns neither the query item nor the nearest neighbor answer to it. Our protocols use light-weight cryptographic primitives and do not require any public key cryptography (hence no homomorphic encryption, no oblivious transfer, etc), so, background in cryptography is not required.
Man Lung Yiu, Gabriel Ghinita, Christian S. Jensen and Panos Kalnis. Enabling Search Services on Outsourced Private Spatial Data. In VLDB, 2010.