DIMACS TR: 98-54

Xor-Trees for Efficient Anonymous Multicast and Reception

Authors: Shlomi Dolev and Rafail Ostrovsky


In this work we examine the problem of efficient anonymous broadcast and reception in general communication networks. We show an algorithm which achieves anonymous communication with O(1) amortized communication complexity on each link and low computational complexity. In contrast, all previous solutions require polynomial (in the size of the network and security parameter) amortized communication complexity.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-54.ps.gz
DIMACS Home Page