%0 Journal Article %T Cryptographically Secure Bloom-Filters %A Ryo Nojima %A Youki Kadobayashi %J Transactions on Data Privacy %D 2009 %I IIIA-CSIC %X 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. %U http://www.tdp.cat/issues/tdp.a015a09.pdf