I found a couple of papers on anonymous protocols that I haven't seen mentioned here before. I'll list them for people who might be interested: Cryptographic Defense Against Traffic Analysis by Rackoff and Simon. http://pct.microsoft.com/papers/ta.ps gives a proof of security for a mix-net like protocol. A. Pfitzmann, B. Pfitzmann, M. Waidner: ISDN-MIXes - Untraceable Communication with Very Small Bandwidth Overhead; Proc. Kommunikation in verteilten Systemen, Feb. 1991, Mannheim, Informatik-Fachberichte 267, Springer-Verlag, Heidelberg 1991, 451-463. describes a protocol for anonymous telephone calls. Wei Dai