Spam is one of the major problems of today email systems. While many solutions have been proposed to automatically detect and filter spam, spammers are getting more and more technically sophisticated and aware of internal workings of anti-spam systems, finding ways to disguise their emails to get around the different controls that can be enforced.

In this paper, we propose a decentralized privacy-preserving approach to spam filtering. Our solution exploits robust digests to identify messages that are a slight variation of one another and a structured peer-to-peer architecture between mail servers to collaboratively share knowledge about spam.