A Study of Privacy Preserving Queries with Bloom Filters

Abstract

This thesis focuses on the private membership test (PMT) problem and presents three single server protocols to resolve this problem. In the presented solutions, a client can perform an inclusion test for some record x in a server's database, without revealing his record. Moreover after executing the protocols, the contents of server's database remain secret.

In each of these solutions, a different cryptographic protocol is utilized to construct a privacy preserving variant of Bloom filter. The three suggested solutions are slightly different from each other, from privacy perspective and also from complexity point of view. Therefore, their use cases are different and it is impossible to choose one that is clearly the best between all three.

We present the software developments of the three protocols by utilizing various pseudocodes. The performance of our implementation is measured based on a real case scenario.

This thesis is a spin-off from the Academy of Finland research project "Cloud Security Services".