Xor-Trees for Efficient AnonymousMulticast and ReceptionSHLOMI DOLEVBen-Gurion University of the NegevandRAFAIL OSTROVSKYTelcordia TechnologiesWe examine the problem of efficient anonymous multicast and reception in general communi-cation networks. We present algorithms that achieve anonymous communication, are pro-tected against traffic analysis, and require O~1! amortized communication complexity on eachlink and low computational complexity. The algorithms support sender anonymity, receiver(s)anonymity, or sender-receiver anonymity.Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]: Gener-al—Security and protection (e.g., firewalls); F.2.2 [Analysis of Algorithms and ProblemComplexity]: Nonnumerical Algorithms and Problems—Routing and layoutGeneral Terms: Algorithms, SecurityAdditional Key Words and Phrases: Anonymous communication, anonymous multicast1. INTRODUCTIONOne of the primary objectives of an adversary is to locate and to destroycommand-and-control centers—that is, sites that send commands and datato various stations and agents. Hence, one of the crucial ingredients inalmost any network with command centers is to conceal from (and confuse)the adversary as to which stations issue the commands. This paper showshow to use standard off-the-shelf cyptographic tools in a novel way in orderAn extended abstract of this paper appears in the Proceedings of the 17th Annual IACR CryptoConference, CRYPTO 1997.This work was done while Shlomi Dolev was visiting Bellcore with the support of DIMACS,and was also supported in part by the Israeli Ministry of Science and Arts grant 6756195.Authors’ addresses: S. Dolev, Department of Computer Science, Ben-Gurion University of theNegev, Beer-Sheva, 84105, Israel; email: [email protected]; R. Ostrovsky, Telcordia Techno-logies, Morristown, NJ 07960–6438; email: [email protected] to make digital/hard copy of part or all of this work for personal or classroom useis granted without fee provided that the copies are not made or distributed for profit orcommercial advantage, the copyright notice, the title of the publication, and its date appear,and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, torepublish, to post on servers, or to redistribute to lists, requires prior specific permissionand/or a fee.© 2000 ACM 1094-9224/00/0500–0063 $5.00ACM Transactions on Information and System Security, Vol. 3, No. 2, May 2000, Pages 63–84.to conceal the command-and-control centers, while still assuring easycommunication between the centers and the recipients.Specifically, we show efficient solutions that hide the identities of thesender and the receiver (or both) of the message/directive in a variety ofanonymity requirements (e.g., the receiver knows the identity of thesender, or the receiver does not know the identity of the sender, etc.). Theproposed solutions are efficient in terms of communication overhead (i.e.,how much additional information must be transmitted in order to confusethe adversary), namely O~1! bits per link. The solutions are also efficientin terms of computation (i.e., how much computation must be performed forconcealment), namely,O~k! pseudorandom sequences are produced to copewith k-listening internal dynamic adversary. A k-listening internal dy-namic adversary can monitor all the communication lines between sitesand also monitor (the internal contents of) up to k , n/2 2 1 sites ofthe network. We note that a preprocessing seeds transmission procedure isexecuted before the actual transmission starts. The communication over-head of this preprocessing procedure is amortized in a long sequencetransmission. The preprocessing stage requires O~g z ~kn!2! bits transmis-sion per a link, whereg is a security parameter that is the seed size of thepseudorandom generator and n is the number of sites in the network.1.1 The ProblemModern cryptographic techniques are extremely good at hiding all thecontents of the data by encrypting the messages. However, hiding thecontents of a message does not hide the fact that some message was sentfrom or received by a particular site; in other words, it does not protectagainst traffic analysis. Thus, if some location (or network node) is sendingand/or receiving a lot of messages and if an adversary can monitor this fact,then even if an adversary does not understand what the messages are, justthe fact that there are a lot of outgoing (or incoming) messages reveals thatthis site (or a network node) is sufficiently active to make it a likely target.The objective of this paper is to address this problem—that is, how to hide,in an efficient manner, the site (i.e., command-and-control center) thattransmits (or receives) a lot of data to (or from, respectively) other sites inthe network. This problem has been addressed previously in the literature[Chaum 1981; 1988; Rackoff and Simon 1993]. We show an amortizedsolution for a general graph which, after a fixed preprocessing stage, cantransmit an arbitrary polynomial-size message in an anonymous fashionusing only O~1! bits over each link (of a spanning tree) for every data bittransmission across a link.1.2 General Setting and Threat ModelWe consider a network of processors/stations where each processor/stationhas a list of other stations with which it can communicate (we do notrestrict the means of communication here, i.e., the means could be computer64 • S. Dolev and R. OstrovskyACM Transactions on Information and System Security, Vol. 3, No. 2, May 2000.networks, radio/satellite connections, etc.) Moreover, we do not restrict thetopology of the network—our general methodology will work for an arbi-trary network topology. One (or several) of the network nodes is a com-mand-and-control center that wishes to send commands (i.e., messages) toother nodes in the network. The question we address in this paper is: Howcan we hide the site that is broadcasting (or multicasting) data to (a subsetof) other processors in the network? Before we explore this questionfurther, we must specify what kind of attack we are defending against.A simple attack to defend against is that of a restricted adversary (calledan outside adversary) who is allowed to monitor communication channelsonly, but is not allowed to infiltrate/monitor the internal contents of anyprocessor in the network. (Note that such a weak attack is very easy todefend against: all processors simply transmit either
View Full Document
Unlocking...