International Association
for Cryptologic Research

AnoNotify is a service for private, timely and low-cost on-line notifications. We present the design and security arguments behind AnoNotify, as well as an evaluation of its cost. AnoNotify is based on mix-networks, Bloom filters and shards. We present a security definition and security proofs for AnoNotify. We then discuss a number of applications, including notifications for incoming messages in anonymous communications, updates to private cached web and Domain Name Service (DNS) queries and finally, a private presence mechanism.