Publish-subscribe is a scheme for distributing information based on interests. While security mechanisms have been added to publish-subscribe, privacy, in particular anonymous communication is hardly considered. We summarize security and privacy requirements for such systems, including an adversary model for privacy. We introduce a construction for publish-subscribe overlays that fulfills the requirements. Contrary to previous approaches, it does neither presume an online trusted third party, nor expensive cryptographic operations performed by brokers. Further, we informally discuss how our requirements are met.