Abstract:
In this presentation, I will deal with the problem of privacy-preservingrange queries, in the storage outsourcing environment. Specifically,
I will give a constant-round scheme for privacy-preservingrange queries (whereas the previous best was logarithmic), ata cost of a logarithmic extra factor in the space complexityat the remote server. This is a worthwhile tradeoff in situations
where the remote server is much more powerful thanthe local client, and it is provably secure in the sense that the
remote server learns nothing about the data it stores or theclient\u2019s queries on that data (except the number of items that
satisfy the range query). In this presentation, I will introduce two noveltechniques: The use of a bi-chromatic version of the dataset,and the judicious use of replication; both techniques are crucialfor proving that the scheme does not leak information tothe server. I will also talk about a secure solution to thenearest-neighbor problem where the server learns neither thequery item nor the nearest neighbor answer to it. Our protocolsuse light-weight cryptographic primitives and do not requireany public key cryptography (hence no homomorphic encryption,no oblivious transfer, etc), so, background in cryptographyis not required.

Reference:
Man Lung Yiu, Gabriel Ghinita, Christian S. Jensen and PanosKalnis. Enabling Search Services on Outsourced Private SpatialData. In VLDB, 2010.