Xor-trees for efficient anonymous multicast and reception.
We examine the problem of efficient anonymous multicast and reception in general communication networks. We present algorithms that achieve anonymous communication, are protected against traffic analysis, and require O(1) amortized communication complexity on each link and low computational comlexity. The algorithms support sender anonymity, receiver(s) anonymity, or sender-receiver anonymity.
Introduction
One of the primary objectives of an adversary is to locate and to destroy command-and-control
centers - that is, sites that send commands and data to various stations/agents. Hence, one
of the crucial ingredients in almost any network with command centers is to conceal and
to confuse the adversary regarding which stations issue the commands. This paper shows
how to use standard off-the-shelf cryptographic tools in a novel way in order to conceal the
command-and-control centers, while still assuring easy communication between the centers and
the recipients.
Specifically, we show efficient solutions that hide who is the sender and the receiver (or
both) of the message/directive in a variety of threat models. The proposed solutions are
efficient in terms of communication overhead (i.e., how much additional information must be
transmitted in order to confuse the adversary) and in terms of computation efficiency (i.e.,
how much computation must be performed for concealment). Moreover, we establish rigorous
guarantees about the proposed solutions.
1.1 The problem considered
Modern cryptographic techniques are extremely good in hiding all the contents of data, by
means of encrypting the messages. However, hiding the contents of the message does not hide
the fact that some message was sent from or received by a particular site. Thus, if some
location (or network node) is sending and/or receiving a lot of messages, and if an adversary
can monitor this fact, then even if an adversary does not understand what these messages
are, just the fact that there are a lot of outgoing (or incoming) messages reveals that this
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, the problem of how to hide, in an efficient
manner, which site (i.e. command-and-control center) transmits (or receives) a lot of data to
(or from, respectively) other sites in the network. This question was addressed previously in
the literature [Ch81, RS93] at the price of polynomial communication overhead for each bit
of transmission per edge. We show an amortized solution which after a fixed pre-processing
stage, can transmit an arbitrary polynomial-size message in an anonymous fashion using only
bits over each link (of a spanning tree) for every data bit transmission across a link.
1.2 General setting and threat model
We consider a network of processors/stations where each processor/station has a list of other
stations with which it can communicate (we do not restrict here the means of communication,
i.e. it could be computer networks, radio/satellite connections, etc.) Moreover, we do not
restrict the topology of the network - our general methodology will work for an arbitrary
network topology. One (or several) of the network nodes is a command-and-control center
that wishes to send commands (i.e. messages) to other nodes in the network. To reiterate,
the question we are addressing in this paper is how we can hide which site is broadcasting (or
multicasting) data to (a subset of) other processors in the network. Before we explore this
question further, we must specify what kind of attack we are defending against.
A simple attack to defend against is of a restricted adversary (called outside adversary) who
is allowed only to monitor communication channels, but is not allowed to infiltrate/monitor
the internal contents of any processor of the network. (As a side remark, such weak attack
is very easy to defend against: all processors simply transmit either noise or encrypted messages
on each communication channel - if noise is indistinguishable from encrypted traffic this
completely hides a communication pattern.) Of course, a more realistic adversary, (and the
one that we are considering in this paper) is the (internal) adversary that can monitor all the
communication between stations and which in addition is also trying to infiltrate the internal
nodes of the network.
That is, we consider the adversary that may mount a more sophisticated attack, where he
manages to compromise the security of one or several internal nodes of the network, whereby
he is now not only capable of monitoring the external traffic pattern but is also capable of
examining every message and all the data which passes through (or stored at) this infiltrated
node. Thus, we define an internal k-listening adversary, an adversary that can monitor all the
communication lines between sites and also manages to monitor (the internal contents of) up
to k sites of the network. (This, and similar definitions were considered before in the literature,
see, for example [RS93, CKOR97] and references therein). We remark, though, that in this
paper we restrict out attention only to listening adversary, that only monitors traffic, but does
not try to sabotage it, similar to [FGY93, KMO94], but with different objectives.
1.3 Comparison with Previous Work
One of the first works (if not the first one) to consider the problem of hiding the communication
pattern in the network is the work of Chaum [Ch81] where he introduced the concept of a mix:
A single processor in the network, called a mix, serves as a relay. A processor P that wants
to send a message m to a processor Q encrypts m using Q's public key to obtain m 0 . Then
P encrypts the pair (m using the public key of the mix. The double encrypted message is
sent to the mix. The mix decrypts the message (to get the pair (m 0 ; q)) and forwards m 0 to
q. Further work in this direction appear in [Pf85, PPW91, SGR97]. The single mix processor
is not secure when this single processor is cooperating with the (outside) adversary; If the
processor that serves as a mix is compromised, it can inform the adversary where the messages
are forwarded to. Hence, as Chaum pointed out, a sequence of "mixes" must be employed
at the price of additional communication and computation. Moreover, the single mix scheme
operates under some statistic assumption on the pattern of communication. In case a single
message is sent to the mix then an adversary that monitors the communication channels can
observe the sender and the receiver of the particular message.
An extension of the mix scheme is presented by Rackoff and Simon [RS93] who embedded
an n-element sorting network of depth polynomial in log(n) that mixes incoming messages
and requires only polynomially many (in log(n)) synchronous steps. In each such step every
message is sent from one site of the network to another site of the network. Thus, the message
delay may be proportional to log(n) times the diameter of the network. The statistic
assumptions on the pattern of communication is somewhat relaxed in [RS93] by introducing
dummy communication: Every processor sends a message simultaneously. However, the
number of (real and dummy) messages arriving to each destination is available to the traffic
analyzer. Rackoff and Simon also presented in [RS93] a scheme that copes with passive internal
adversaries by the use of randomly chosen committees and multi-party computation (e.g.,
[GMW87, BGW88, CCD88, CFGN96, CKOR97].)
More generally, secure multi-party computation can be used to hide the communication
pattern in the network (see, for example, [GMW87, Ch88, WP90, BGW88, CCD88, CFGN96,
CKOR97]) via secure function valuation. However, anonymous communication is a very restricted
form of hiding participants' input and hence may benefit from less sophisticated and
more efficient algorithms.
In particular, Chaum suggested in [Ch88] to use the dc-net approach in order to achieve
anonymous communication. Our approach is similar to the dining cryptographers solution in
[Ch88], where a graph characterization of the random bits distribution is given. We present a
specific choice (an efficient instance that satisfies Chaum's graph characterization) of selecting
(a small number of) keys for each processor, and a procedure to securely distribute the keys and
use O(1) amortized communication complexity on each link. Our algorithm is proven correct
by a new argument proving that each bit communicated has an equal probability to be 0 and
to be 1 for a particular adversary. In [Ch88] the case of anonymous sender is considered, in this
work we suggest schemes also for the cases in which the receiver is (receivers are, respectively)
anonymous, and in which both the sender and the receiver are anonymous to each other.
In [Ch88] it is assumed that the underlying communication networks is a ring or that a
back-off mechanism is repeatedly used to send data. In this work we consider the problem
of anonymous communication on a spanning tree of a general graph communication network.
We note that solutions for star and tree networks are briefly mentioned in [Pf85, PW87], with
no details for the way communication starts and terminates for this specific networks. Our
contributions is a detailed design for a (spanning) tree communication network. The details
include: a new scheme for seeds selection that ensures anonymity in the presence of an outside
adversary and k-listening internal dynamic adversary. Schemes for anonymous receiver, as well
as anonymous sender and receiver. We specify the initialization (including seed distribution),
the communication and the termination procedures that preserve anonymity for the case of
a (spanning) tree communication network. In addition, we use an extra random sequence
(that is produced by a pseudo random generator) shared by the sender (and the receiver(s)) to
encrypt (decrypt, respectively) the message, avoiding the use of additional different scheme for
encryption and decryption during the transmission of the (long) messages. This new approach
fits transmission of a very long sequence of bits, such as video information to several recipient.
Thus, it can be used for anonymous multicast such as multicast by cable TV.
Our initialization scheme is designed to cope with the problem of the information revealed
by the back-off mechanism (see [BB89]) by using a predefined ordered of transmission.
We note that in this work we do not concern ourselves with active adversary that can
corrupt the program or forge messages on the links as assumed in [Wa89]. The extensions
suggested in [Wa89] is a design of a fail-stop broadcast instead of assuming reliable broadcast.
In a network of n processors our algorithm (after a pre-processing stage) sends O(1) bits
on each tree link in order to transmit a clear-text bit of data and each processor computes
pseudo-random bits for the transmission of a clear-text bit. Multiple anonymous transmission
is possible by executing in parallel several instances of our algorithm. Each instance
uses part of the bandwidth of the communication links. Our algorithm is secure for both
outside adversary and k-listening internal dynamic adversary. (We remark, though, that we
are only considering eavesdropping "listening" adversary, similar to [FGY93, KMO94], and do
not consider a Byzantine adversary which tries to actively disrupt the communication, as in
[GMW87].)
1.4 A simple example
In this subsection, we examine a very simple special case, in order to illustrate the issues being
considered and a solution to this special case. We stress, though, that we develop a general
framework that works for the general case (e.g. the case of general communication graph,
unknown receiver, etc.) as well.
Suppose we are dealing with a network having 9 nodes:
P1 \Gamma! P2 \Gamma! P3 \Gamma! P4 \Gamma! P5 \Gamma! P6 \Gamma! P7 \Gamma! P8 \Gamma! R
where R is the "receiver" node and one of the P i is the command-and-control center which
must broadcast commands to R. The other P j 's for j 6= i are ``decoys'' which are used for
transmission purposes from P i to R and also are used to "hide" which particular P i is the real
command and control center. That is, in this simplified example, we only wish to hide from an
adversary which of the P i is the real command and control center which sends messages to R.
Before we explain our solution, we examine several inefficient, but natural to consider simple
strategies and then explain what are their drawbacks.
Communication-inefficient solution: One simple (but inefficient!) way to hide which P i is
the command-and-control center is for every P i to broadcast an (encrypted) stream of messages
to R. Thus, R receives 8 different streams of messages, ignores all the messages except those
from the real command-and-control center, and decrypts that one. Every processor P i forwards
messages of all the smaller-numbered processors and in addition sends its own message. Clearly,
an adversary who is monitoring all the communication channels and which can also monitor the
internal memory of one of the P i 's (which is not the actual command-and-control center) does
not know which P j is broadcasting the actual message. Drawback: Notice that instead of one
incoming message, R must receive 8 messages, thus the throughput of how much information
the real command-and-control center can send to R is only 1of the total capacity! As the
network becomes larger this solution becomes even more costly. Note that this solution enables
the receiver to identify the sender.
Computation-inefficient solution: In the previous example, the drawback was that the
messages from decoy command-and-control nodes were taking up the bandwidth of the channel.
In the following solution, we show how this difficulty can be avoided. In order to explain this
solution, we shall use pseudo-random generators 1 [BM84, Ha90, ILL89]. We first pick 8 seeds
for the pseudo-random generator, and give to processor P i seed s i . Processor P 1
stretches its seed s 1 into long pseudo-random sequence, and sends, at each time step the next
bit of its sequence to processor P 2 . Processor P 2 takes the bit it got from processor P 1 and
"xors" it with its own next bit from its pseudo-random sequence G(s 2 ) and sends it to P 3 and
so forth. The processor P j which is the real command-and-control center additionally "xors"
into each bit it sends out a bit of the actual message m i . Processor R is given all the 8 seeds
so it can take the incoming message, (which is the message from command-and-
control center "xored" with 8 different pseudo-random sequences.) Hence, R can compute all
the 8 pseudo-random sequences, subtract (i.e. xor) the incoming message with all the 8 pseudo-random
sequences and get the original command-and-control message m. The advantage of
this solution is that any P j which is not a command-and-control center (and not R), clearly
can not deduce which other processor is the real center. Moreover, the entire bandwidth
of the channel between command-and-control processor and the receiver is used to send the
messages from the center to the receiver. Drawback: The receiver must compute 8 different
pseudo-random sequences in order to recover the actual message. As the network size grows,
this becomes prohibitively expensive in terms of the computation that the receiver needs to
perform in order to compute the actual message m.
Our solution for this simple example: Here, we present a solution that is both computation-
efficient and communication-efficient and is secure against an adversary that can monitor all
the communication lines and additionally can learn internal memory contents of any one of
the intermediate processors. The seed distribution (for a particular communication session) is
as follows:
Pick 9 random seeds for pseudo-random generator s
ffl Give to the real command-and-control processor seed s 0 .
ffl Additionally, give to processor P 1 seed fs
processor P 3 two seeds fs 3 ; s 4 g, and so on. That is, we give to each processor P i for
the seeds fs g.
initial "seed" of truly random bits, and deterministically
expands it into a long sequence of pseudo-random bits. There are many such commercially available
pseudo-random generators, and any such "off-the-shelf " generator that is sufficiently secure and efficient will
suffice.
ffl give to receiver, R, one seed s 0
Suppose processor P 4 is the real command-and-control center. Then the distribution of seeds
is as follows:
Now, the transmission of the message is performed in the same fashion as in the previous
solution - that is, each processor receives a bit-stream from its predecessor, "xors" a single
bit from each pseudo-random sequence that it has, and sends it to the next processor. The
command-and-control center "xors" bits of the message into each bit that it sends out.
Notice, that adjacent processors "cancel" one of the pseudo-random sequences, by xoring
it twice, but introduce a new sequence. For example, processor P 2 cancels s 2 , but "introduces"
s 3 . Moreover, each processor must now only compute the output of at most three seeds. Yet,
it can be easily verified that if the adversary monitors all the communication lines and in
addition can learn seeds of any single processor P i which is not a command and control center,
then it can not gain any information as to which other P i is the real command and control
center, even after learning the two seeds that belong to processor P i .
Of course, the simplified example that we presented works only provided that the adversary
cannot monitor both the actual command-and-control center and can not monitor the memory
contents of the receiver. (We note that these and other restrictions can be resolved - we address
this further in the paper.) Moreover, it should be stressed that the restricted solution presented
above does not work if the adversary is allowed to monitor more than one decoy processor.
Note that our solution requires that the command-and-control and the receiver have a special
common seed s 0 , one obvious extension is to ensure that every two processors have a distinct
additional seed that is used for communication between themselves. We should point out that
in the rest of the paper we show how the above scheme can be extended to one that is robust
against adversaries that can monitor up-to k stations, where in our solution every processor
is required to compute the number of different pseudo-random sequences proportional to k
only (in particular, at most 2k 1). Moreover, we also show how to generalize the method
to arbitrary-topology networks/infrastructures. Additionally, we show how initial distribution
of seeds can be done without revealing the command-and-control center and how the actual
location of the command-and-control center can be hidden from the recipients of the messages
as well. At last, we show how communication from stations back to the command-and-control
center could be achieved without the stations knowing at which node of the network the center
is located and how totally anonymous communication can be achieved.
solutions vs. Public-key solutions
The above simple solution is a private-key solution, that is, we assume that before the protocol
begins, a set of seeds for pseudo-random function must be distributed in a private and
anonymous manner. Thus, we combine this solution with a preprocessing stage in which we
distribute these seeds using a public-key solution, that is, a solution where we assume that all
users/nodes only have corresponding public and private keys and do not share any information
a-priori. Thus, our overall solution is a public-key solution, where before communication
begins, we do not assume that users share any private data. As usual in many of such cryptographic
setting, our overall efficiency comes from the fact that we switch from public-key to
private key solution and then show how to (1) make an efficient private-key implement and
(2) how to set up private keys in a pre-processing stage by using public keys in an anonymous
and private manner.
The rest of the paper is organized as follows. The problem statement appears in Section
2. The anonymous communication (our Xor-Tree Algorithm) which is the heart of our scheme
appears in 3. Section 4 and 5 sketch the anonymous seeds transmission and the initialization
and termination schemes, respectively. Extensions and concluding remarks appear in Section
6.
Problem Statement
A communication network is described by a communication graph E). The nodes,
processors of the network. The edges of the graph represent
bidirectional communication channels between the processors. Let us first define the assumptions
and requirements used starting with the adversary models. The adversary is a passive
listening adversary that does not intervene in the computation, in particular it does neither
forge messages on the links, nor corrupt the program of the processors.
ffl An outside adversary is an adversary that can monitor all the communication links but
not the contents of the processors memory.
ffl An internal dynamic k-listening adversary (inside adversary, in short) is an adversary
that can choose to "bug" (i.e., listen to) the memory of up to k processors. The targeted
processors are called corrupted, compromised, or colluding processors. Corrupted processors
reveal all the information they know to the adversary, however they still behave
according to the protocol. The adversary does not have to choose the k faulty processors
in advance. While the adversary corrupts less than k processors the adversary can
choose the next processor to be corrupted using the information the adversary gained so
far from the processors that are already corrupted.
The following assumptions are used in the first phase of our algorithm which is responsible
for the seeds distribution. Each of the n processors has a public-key/private-key pair. The
public key of a processor, P , is known to all the processors while the private key of P is known
only to P .
The anonymity of the communicating parties can be categorized into four cases:
ffl Anonymous to the non participating processors: A processor P wishes to send a message
to processor Q without revealing to the rest of the processors and to the inside and
outside adversary the fact that P is communicating with Q.
ffl Anonymous to the sender and the non participating processors: P wishes to receive a
message from Q without revealing its identity to any processor including Q as well as to
an inside and outside adversary.
ffl Anonymous to the receiver(s) and the non participating processors: P wishes to send
(or multicast) a message without revealing its identity to any processor as well as to an
inside and an outside adversary.
ffl Anonymous to the sender, to the receiver, and the non participating processors: A processor
P wishes to communicate with some other processor, without knowing the identity
of the processor, and without revealing its identity to any processor including the one it
is communicating with, as well as to an inside and outside adversary. (This is similar to
the "chat-room" world-wide-web applications, where two processors wish to communicate
with one another totally anonymously, without revealing to each other or anybody
else their identity.)
The efficiency of a solution is measured by the communication overhead which is the number
of bits sent over each link in order to send a bit of clear-text data. The efficiency is also
measured by the computation overhead which is the maximal number of computation steps
performed by each processor in order to transfer a bit of clear-text data.
The algorithm is a combination of anonymous seeds transmission, initialization, communication
and termination. In the anonymous seeds transmission phase, processors that would like
to transmit, anonymously send seeds for a pseudo-random sequence generators to the rest of
the processors. The anonymous seeds transmission phase also resolves conflicts of multiple requests
for transmission by an anonymous back-off mechanism. Once the seeds are distributed
the communication can be started. Careful communication initialization (and termination)
procedure that hide the identity of the sender must be performed.
We first describe the core of our algorithm which is the communication phase. During
the communication phase seeds are used for the production of pseudo-random sequences. The
anonymous seeds distribution is presented following the description of the anonymous communication
phase.
3 Anonymous Communication
3.1 Computation-inefficient O(n) solution
The communication algorithm is designed for a spanning tree T of a general communication
graph, where the relation parent child is naturally defined by the election of a root. We start
with a simple but inefficient algorithm which requires O(n) computation steps of a processor.
(This algorithm is similar to the computation-inefficient solution presented in Section 1, but for
the general-topology graph. We then show how to make it computation-efficient as well.) In
this (computation-inefficient) solution the sender will chose a distinct seed for each processor.
Then the sender can encrypt each bit of information using the seeds of all the processors
including its own seeds. Each such seed is used for producing a pseudo-random sequence. The
details of the algorithm appear in Figure 1. The symbol \Phi is used to denote the binary xor
operation.
Note that the i'th bit produced by the root is a result of xoring twice every of the i'th bits
of the pseudo-random sequences except the senders' sequence: once by the sender and then
during the communication upwards. Each encrypted bit of data will be xored by the receiver(s)
using the senders' seed to reveal the clear-text. Note that the scheme is resilient to any number
of colluding processors as long as the sender and the receiver(s) are non-faulty. This simple
scheme requires a single node (the sender) to compute O(n) pseudo-random bits for each bit
of data. (We remark that in contrast, our Xor-Tree Algorithm, requires the computation of
only O(k) pseudo-random bits to cope with an outside adversary and an internal dynamic k-
listening adversary.) The next Lemma state the communication and computation complexities
of the algorithm presented in Figure 1.
Lemma 3.1 The next two assertions hold for every bit of data to be transmitted over each
edge of the spanning tree:
ffl The communication overhead of the algorithm is O(1) per edge.
ffl The computation overhead of our algorithm is O(n) pseudo-random bits to be computed
by each processor per each bit of data.
Proof: In each time unit two bits are sent in each link: one upwards and the other downwards.
Since a bit of data is sent every time unit (possibly except the first and last h time units, where
is the depth of the tree) the number of bits sent over a link to transmit a bit of data
is O(1). The second assertion follows from the fact that the sender computes the greatest
number of pseudo random bits in every time unit, namely O(n) pseudo-random bits in every
time units.
Seeds Distribution -
ffl Assign (anonymously) a distinct seed s i to each processor P i .
ffl Assign to the sender all the seeds s of all the processors and an
additional seed s 0 .
ffl Assign the receiver(s) with an additional seed, the seed s 0 .
Upwards Communication :
P is the sender -
ffl Let d i be the i'th bit of data.
l be the i'th bits received from the children (if any) of P .
0 be the i'th bit of the pseudo random sequence obtained from the
additional seed s 0 of P j .
n be the i'th bits of the pseudo random sequence obtained
from the seeds s
ffl The i'th bit P j sends to its parent (if any) is d i \Phi b 0
n .
P is not the sender -
l be the i'th bits received from the children (if any) of P j .
j be the i'th bit of the pseudo random sequence obtained from the seed
ffl The i'th bit that P communicants to its parent (if any) is
.
Downwards Communication -
ffl The root processor calculates an output as if it has a parent and sends the result
to every of its children.
Every processor which is not the root, sends to its children every bit received
from its parent.
ffl The receiver(s) decrypts the downward communication by xoring the i'th bit
that arrives from the parent with the i'th bit in the pseudo random sequence
obtained from s 0 .

Figure

1: O(n) Computation Steps Algorithm, for a processor P j .
3.2 Towards our O(k) solution: The choice of seeds
For the realization of the communication phase of our O(k) solution we use n(k
seeds where k is less than bn=2 \Gamma 1c. Each processor receives seeds. To describe the
seeds distribution decisions of the sender we use k each consists of two layers of
seeds. We order the processors by their (arbitrary assigned) indices we use the
relation follows in a straight forward manner.
The first level - Let L
n be the seeds that the sender (randomly)
chooses for the first level. The sender uses the sequence of seeds L 1
for the first layer of the first level and L 1
1 for the second layer. Note
that L 1
2 is obtained by rotating
seeds s 1
1 .
The l'th level - Similarly, for the l'th level 1 - l -
distinct seeds for this level L
n to be the seeds of the l'th level and
uses two sequences L l= L l and L l= s l
l
lis obtained by
rotating L l l times. receives the seeds s l
i+l and P
receives the seeds s l
Thus, at the end of this procedure every processor is assigned by 2k+2 distinct seeds.

Figure

2: The choice of seeds.
The seeds distribution procedure appears in Figure 2. An example for the choice of seeds
for the processors appears in Figure 3.
Seeds of
9 s 00
Figure

3: An example for the distribution of seeds, where 2.
The choice of seeds made by the sender has the following properties:
ffl Each seed is shared by exactly two processors.
ffl For every processor P , P shares a (distinct) seed with every of the k+1 processors that
immediately follow P , (if there are at least such k+1 processors), or with the rest of the
processors including P n , otherwise.
3.3 The Xor-Tree Algorithm
Here, we present out main algorithm, the Xor-Tree Algorithm. The Xor-Tree Algorithm appears
in Figure 4.
3.4 An abstract game
In this subsection we describe an abstract game that will serve us in analyzing and proving
the correctness of the Xor-Tree Algorithm presented in the previous subsection.
The adversary get to see the outputs of all the players. The adversary can pick k out of
the players and see their seeds. We claim, and later prove, that when the adversary does not
pick the sender then every one of the remaining (n \Gamma processors that are not picked by the
adversary is equally likely to be the sender for any poly-bounded adversary 2 .
We proceed by showing that the above assignment of seeds yields a special seed ds P for
each processor P . We choose ds P out of the seeds assigned to each non-faulty processor P .
We order the processors by their index in a cyclic fashion such that the processor that follows
the i'th processor, i 6= n, is the processor with the index and the processor that follows
the n'th processor is the first processor. Then we assign a new index for each processor such
that the sender has the index one, the processor that follows the sender has the index two and
so on and so forth. These new indices are used for the interpretation of next, follows, prior
and last in the description of the choice of special seeds that appears in Figure 6. Recall that
with overwhelming probability every two processors share at most one seed.
Note that by our special seeds selection, described in Figure 6, the special seeds are not
known to the k faulty processors.
Theorem 3.2 In the abstract game any of the (n \Gamma non-faulty processors is equally likely
to be the sender for any poly-bounded internal k-listening adversary.
Proof: We prove that the i'th bit produced by any non-faulty processors is equally likely
to be 0 or 1 (for any poly-bounded adversary). Let P be the first non-faulty processor that
follows the sender (P is among the first k processors that follow the sender). Let ds P 1
be
the special seed of the sender that is shared only with (the non-faulty processor) P . The i'th
bit that the sender outputs is a result of a xor operation with the i'th bit of the pseudo-random
2 If the adversary can predict who is the sender then we can use this adversary to break a pseudo-random
generator.
Seeds Distribution -
ffl Assign seeds to the processors as described in Figure 2.
ffl Assign the sender with one additional seed, s 0 .
ffl Assign the receiver(s) with an additional seed, the seed f the sender s 0 .
Upwards Communication :
is the sender -
ffl Let d i be the i'th bit of data.
l be the i'th bits received from the children (if any) of P j .
2k+2 be the i'th bits of the pseudo-random sequences obtained
from the seeds of P j .
be the i'th bit of the pseudo-random sequence obtained from the
additional seed s 0 of P j .
ffl The i'th bit P j sends to its parent (if any) is d
2k+3 .
is not the sender -
ffl The i'th bit that P j communicants to its parent (if any) is
Downwards Communication -
ffl The root processor calculates an output as if it has a parent and sends the result
to every of its children.
ffl Every non root processor send to its children every bit received from its parent.
ffl The receiver(s) decrypts the downward communication by xoring the i'th bit
that arrives from the parent with the i'th bit in the pseudo random sequence
obtained from s 0 .

Figure

4: The Xor-Tree Algorithm, for a processor P j .
Seeds Assignment - Assign seeds to the processors as described in Figure 2. Assign
the sender with one additional seed.
Computation - Each processor, P , uses its seeds to compute pseudo-random sequences.
At the i'th time unit the sender S computes the i'th bit of every of its pseudo-random
sequences, xors these bits and the i'th bit of data and outputs the result. At the same
time unit every other processor P computes the i'th bit of every of its pseudo-random
sequences xors these bits and outputs the result.

Figure

5: The Abstract Game.
The sender P 1 - Each of the k+1 processors that immediately follows the sender shares
exactly one seed with the sender. Since there are at most k colluding processors, one of
these k+1 processors must be non-faulty. Pick, P , the first such non-faulty processor.
Assign ds P 1
, the special seed of the sender, to be the seed that the sender shares with
processors P that is not among the k last processors - If P is not among
the last processors then P is assigned by 2k seeds of these seeds
are from the first layers of the k+1 seed levels. These k+1 seeds are new - they do not
appear in any processor prior to P . Since there are at most k colluding processors,
one of the next k processors is non-faulty. Let Q be the first such non-faulty
processor and assign ds P by the seed that P shares with Q. Repeat the procedure
until you reach a non-faulty processor that is among the last k processors.
A processors Q that is among the k last processors - Note that Q does not
new seeds since some of its seeds are assigned to the first processors
(at least the one in the k + 1'th level). Fortunately, Q shares a single new seed
with every of the last processors. This fact allows us to continue the special seed
selection procedure, by choosing the seed shared with the next non-faulty processor.

Figure

Choice of special seeds.
sequence (among other pseudo-random sequences) obtained from ds P 1
. Since only P (that is
a non-faulty processor) shares ds P 1
with the sender, it holds that the i'th bit output by the
sender is equally likely to be 0 or 1 (for any poly-bounded internal k-listening adversary). A
similar argument hold for the output of P , since there exists a special seed shared with the
next non-faulty processor Q. In general it holds for the output of every non-faulty processor.
The same argument holds if any of the non-faulty processors is the sender. Thus, for
any polynomially-bounded k-internal and external adversary, the distribution of the output is
indistinguishable of the identity of the sender.
The fact that the adversary can be a dynamic adversary is implied by the Corollary 3.3.
The proof of the corollary is similar to the proof of Theorem 3.2.
Corollary 3.3 For any k 0 - k after the adversary chooses k 0 faulty processors any of the
processors is equally likely to be the sender for any poly-bounded internal
k'-listening adversary.
3.5 Reduction to the abstract game
In this subsection we prove that if there is an algorithm that reveals information on the identity
of the sender in the tree then there exists an algorithm that reveals information on the identity
of the sender in the abstract game. The above reduction together with Theorem 3.2 yields the
proof of correctness for the Xor-Tree algorithm.
Assume that the adversary reveals information on the sender in a tree T of n processors.
Then an abstract game of n nodes is mapped to the tree as follows:
1. Each processor of the abstract game is assigned to a node of the tree T .
2. The output of every processor to its parent is computed as follows: Let the hight of
a processor P in T be the number of edges in the longest path P from P to a leaf
such that P does not traverse the root. We start with the processors that are in hight
i.e. the leaves. The output of the processors that were assigned to the leaves of
the tree is not changed i.e. it is identical to their output in the abstract game. Once
we computed the output of processors in hight h we use these computed outputs to
compute the outputs of processors in hight h+ 1. Let Q be a processor in hight h+ 1,
l be the i'th computed bits that are output by the children of Q, and
let b Q be the original i'th output bit of Q in the abstract game. The computed output
of Q is b 1 \Phi b 2 \Phi

Figure

7: The Reduction.
Theorem 3.4 In the Xor-Tree Algorithm any of the (n \Gamma non-faulty processors is equally
likely to be the sender for any poly-bounded internal k-listening adversary.
Proof: If there exists an adversary A that reveals information on the identity of the sender
in a tree T then there exists an abstract game with the same number of processors and the
same seeds distribution, such that the application of the reduction in Figure 7 yields the
communication pattern on T and reveals information on the sender identity in the abstract
game. This contradicts Theorem 3.2 and thus contradicts the existence of A.
The next Lemma states the communication and computation overheads of the anonymous
communication algorithm.
Lemma 3.5 The next two assertions hold for every bit of data to be transmitted over each
edge of the spanning tree:
ffl The communication overhead of the algorithm is O(1) per edge.
ffl The computation overhead of our algorithm is O(k) pseudo-random bits to be computed
by each processor per each bit of data.
Proof: In each time unit two bits are sent in each link: one upwards and the other downwards.
Since a bit of data is sent every time unit (possibly except the first and last h time units, where
is the depth of the tree) the number of bits send over each link to transmit a bit of
data is O(1). The second assertion follows from the fact that in each time unit each processor
generates at most 2k
Anonymous Seeds Transmission
We first outline the main ideas in the seeds transmission scheme and then give full details.
Every processor has a public-key encryption, known to all other processors. A virtual ring
defined by the Euler tour on the tree is used for the seeds transmission. Note that the indices
of the processor used in this description are related to their location on the virtual ring. First
all processors send messages to P 1 over the (virtual) ring. Those processors that wish to
broadcast send a collection of seeds, and those processors that do not wish to broadcast, send
dummy messages of equal length. To do so in an anonymous fashion (so that P 1 does not know
which message is from which processor), k + 1 of Chaum's mixes [Ch81] are used, where k
(real) processors just before P 1 in the Euler tour are used as mixes. Hence, P 1 can identify
the number of non-dummy arriving messages but not their origin. In case more than one non-dummy
message reaches P 1 , a standard back-off algorithm is initiated by P 1 . Once exactly
one message (containing a collection of seeds) arrives to P 1 the seed distribution procedure
described above (for sending a collection of seeds to P 1 ) is used to send the seeds to P 2 and
so on. (At this point processors know that only one processor wishes to broadcast.) This
procedure is repeated n times in order to allow the anonymous sender to transmit a collection
of seeds to every processor. Notice that this process is quadratic in the size of the ring, the
number of colluding processors k, and the length of the security parameter, (i.e., let g be a
security parameter and k as before, then we send O((gkn) 2 ) bits per edge.) Thus, as long the
message size p to be broadcasted is greater than O((gkn) 2 ) we achieve O(1) overall amortized
cost per edge, and otherwise we get O((gkn) 2 =p) amortized cost.
The details follow. The seeds transmission procedure uses a virtual ring R defined by an
Euler tour of the tree T . Note that each edge of T appears exactly twice in R and therefore
the number of edges and nodes in R is 2. The seeds transmission procedure starts with
the transmission of seeds to the first processor P 1 . Let L be the list of
processors in R in clockwise order starting with P 1 ; the indices 2 to 2n \Gamma 2 are implied by the
Euler tour and not by the indices of the processors in T . Note that a single processor of T
may appear more than once in L 1 . We use the term instance for each such appearance. Define
the reduced list RL 1 to be a list of processors that is obtained from L 1 by removing all but
the first instance of each processor. Thus, in RL 1 every processor of T appears exactly once.
The communication of seeds uses the anti-clockwise direction. Define the last l real processors
to be the first l processors in RL 1 . When transmitting seeds to P i , L i , RL i and the last l
processors, are defined analogously.
In the first stage every processor that wants to communicate with another processor sends
an encrypted message with the seeds to be used by P 1 . Note that P 1 can be a faulty processor,
thus a careful transmission must be carried on. Let L be the list of
processors in R in anti-clockwise order i.e. L 1 in reversed order. Again L 1 includes more than
one instance of each processor P of T . Define the active instance of a processor P of T in L 1
to be the last appearance of P in L 1 . Define an active message to be a message that arrives
to an active instance of a processor. The details of the anonymous seeds transmission to P 1
appears in Figure 8.
As we prove in the sequel no information concerning the identity of the requesting processors
is revealed during the anonymous seeds transmission to P 1 except the information that can
be concluded by the value of n t - the number of processors that would like to transmit.
Once processors starts sending messages to P 2 in a fashion similar to the one
used to send seeds to P 1 . Then processors sends seeds to P 3 and so on and so forth, till the
processors send messages to P n . Note that when n there is exactly one sender for the
next communication session and at the end of the seeds distribution procedure every processor
holds the seeds distributed by the sender.
Lemma 4.1 A coalition of k colluding processors cannot reveal the identity of the seeds distributors

Proof: We prove the lemma for the transmission of the seeds from the sender to P 1 . Note that
one of the last k+1 real processors must be non-faulty. If P 1 is non-faulty then no information
starts - The first processor to send a message m n to P 1 is P n . If P n wants to transmit
data then m n contains seeds to be used by P 1 , otherwise m n is an empty message
i.e. a message that can be identified by P 1 as a null message. P n uses the public
of the last k processors
m n in a nested fashion; First encrypting m n with pu 1 then encrypting the resulting
message with pu 2 and so on. P n sends the k 1-nested encrypted message m k+1
n to
the processor that is next to the active instance of P n in L 1 .
Non active message - When a processor P i receives a non active message it forwards
the message to the next processor according to L 1 .
Active message - We now proceed by describing the actions taken by a processor upon
the arrival of an active message.
ffl We first describe the action taken by a processor P i that is not among the last k+1
real processors. When an active message with fm k+1
arrives
(to the active instance of) P
its own k 1-encrypted message
(again, containing seeds to be used by P 1 or null message) to the message received
and sends the message to the next processor according to L 1 .
ffl We now turn to consider a processor P i that is among the last k
processors. When an active message with fm i
arrives to
using its private key
to obtain fm
g. its message to P 1 by the
public keys of the last processors. P i randomly orders the set
fm
and sends the reordered set to the processor that
is next according to L 1 (Note that following the first such reordering the j'th
index of m
j is not necessarily the index of the sender of m
Arrival to receives an active message with fm 1
every message and finds out the number n t of the processors that would like
to transmit. If n t 6= 1 then P 1 sends a message with the value of n t that traverses the
virtual ring. Upon receiving such a message each processor that wants to transmit,
randomly chooses a waiting time in the range of say, 1 to 2n t . The procedure of
sending seeds to P 1 is repeated until n

Figure

8: Anonymous Seeds Transmission to P 1 .
concerning the identity of the seeds distributors is revealed to the adversary. Otherwise,
when P 1 is faulty then let P i be the non faulty processor that is the last to reorder the set
fm
upon the arrival of fm i
g. Since every arriving m i is
encrypted with P i 's public key no set of k-faulty processors can decrypt m
originated by a faulty processor). P i randomly order the set fm
holds that a coalition of k processors cannot reveal the identity of the sender of any m i\Gamma1 in
fm
g.
5 Initialization and Termination
When the seed distribution procedure is over, then the transmission of data may start. P n
broadcasts a signal on the tree that notifies the leaves that they can start transmitting data.
The leaves start sending data in a way that ensures that every non-leaf processor receives
the i'th bit from its children simultaneously. Thus, the delay in starting transmission of a
particular leaf l is proportional to the difference between the longest path from a leaf to the
root and the distance of l from the root. Each non leaf processor waits for receiving the i'th
bit from each of its children, uses these bits and its seeds to compute its own i'th bit and
sends the output to its parent. Note that buffers can be used in case the processors are not
completely synchronized.
The sender can terminate the session by sending a termination message that is not encrypted
by its additional seed. This message will be decrypted by the root that will broadcast
it to the rest of the processors to notify the beginning of a new anonymous seeds transmission.
6 Extensions and Concluding Remarks
Our treatment so far considered the anonymous sender case, which is also anonymous to
the non participating processors. A simple modification of the algorithm can support the
anonymous receiver case: The receiver plays a role of a sender of the previous solution in order
to communicate in an anonymous fashion an additional seed to the sender. Then the sender
uses the same scheme for the anonymous sender case with the seed the sender got from the
receiver.
To achieve anonymous communication in which both the sender and the receiver are anony-
mous, do the following: The two participants, P and Q, that would like to communicate (each)
send anonymously distinct seeds to P . It is possible that more than two participants
will send anonymously distinct seeds to P 1 . In such a case, P 1 will broadcast the processors
that more than two processors tried to anonymously chat and a back-off mechanism will be
used until exactly two participants, P and Q, send seeds to P 1 . Then, P 1 will encrypt and
broadcast the two seeds it got, each seed encrypted (using distinct intervals of the pseudo-random
expansions of the two seeds) by the other seed. Hence, each of the two processors will
use its seed to reveal the seed of the other processor. At this stage P and Q will continue
and anonymously send seeds to P . The same procedure continues for
Now P has a set of k seeds that are used for encryption of messages sent to Q and
used for encryption messages sent to P . They both act as senders using the
bit resulting from xoring the bits produced by the set of the k seeds as the bit of special
seed known to the receiver in our anonymous sender scheme. The back-off mechanism ensures
that one of P and Q starts the communication and then the other can replay (when the first
allows him to, i.e., stops transmitting data). We remark that it is possible to have more than
two participants by a similar scheme.
The security of the above algorithm is derived from the fact that there must be a non-faulty
processor among the processor therefore the adversary does not know at
least one key used to encrypt and decrypt messages by the sender and the receiver.

Acknowledgment

We thank Oded Goldreich, Ron Rivest and the anonymous referees for
helpful remarks.



--R

"Detection of disrupters in the DC protocol"
"An efficient probabilistic public-key encryption scheme which hides all partial information"
"How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits"
"Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation"
"Adaptively Secure Multi-Party Computation"
"Randomness vs. Fault- Tolerance"
"Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms"
"Multiparty Unconditionally Secure Pro- tocols"
"The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability"
"Achieving Electronic Privacy"
"Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems,"
"How To Play Any Mental Game"
"Pseudo-Random Generators under Uniform Assumptions"
"Pseudo-Random Generation from One-Way Functions,"
"Reducibility and Completeness in Multi-Party Private Computations"
"How to Implement ISDNs Without User Observability - Some Re- marks"
"Network without User Observability,"
"ISDN-MIXes - Untraceable Communication with Very Small Bandwidth Overhead,"
"Anonymous Connections and Onion Routing"
"Unconditional Sender and Recipient Untraceability in spite of active attacks"

"Cryptographic Defense Against Traffic Analysis"
--TR
How to generate cryptographically strong sequences of pseudo-random bits
Networks without user observability
How to play ANY mental game
The dining cryptographers problem: <italic>unconditional sender and recipient untraceability</>
Completeness theorems for non-cryptographic fault-tolerant distributed computation
Multiparty unconditionally secure protocols
Unconditional sender and recipient untraceability in spite of active attacks
Detection of disrupters in the DC protocol
The dining cryptographers in the disco
Cryptographic defense against traffic analysis
Adaptively secure multi-party computation
Randomness vs. fault-tolerance
The art of computer programming, volume 1 (3rd ed.)
A Pseudorandom Generator from any One-way Function
Untraceable electronic mail, return addresses, and digital pseudonyms
ISDN-MIXes
Anonymous Connections and Onion Routing

--CTR
Chin-Chen Chang , Chi-Yien Chung, An efficient protocol for anonymous multicast and reception, Information Processing Letters, v.85 n.2, p.99-103, 31 January
Nicholas Hopper , Eugene Y. Vasserman, On the effectiveness of k;-anonymity against traffic analysis and surveillance, Proceedings of the 5th ACM workshop on Privacy in electronic society, October 30-30, 2006, Alexandria, Virginia, USA
Steven S. Seiden , Peter P. Chen , R. F. Lax , J. Chen , Guoli Ding, New bounds for randomized busing, Theoretical Computer Science, v.332 n.1-3, p.63-81, 28 February 2005
Jiejun Kong , Dapeng Wu , Xiaoyan Hong , Mario Gerla, Mobile traffic sensor network versus motion-MIX: tracing and protecting mobile wireless nodes, Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks, November 07-07, 2005, Alexandria, VA, USA
anonymous communication;anonymous multicast