Cryptographically Secure Bloom-Filters

In this paper, we propose a privacy-preserving variant of Bloom-filters. The Bloom-filter has many applications such as hash-based IP-traceback systems and Web cache sharing. In some of those applications, equipping the Bloom-filter with the privacy-preserving mechanism is crucial for the deployment. In this paper, we propose a cryptographically secure privacy-preserving Bloom-filter protocol. We propose such two protocols based on blind signatures and oblivious pseudorandom functions, respectively. To show that the proposed protocols are secure, we provide a reasonable security definition and prove the security.