On the Complexity of Anonymous Communication Through Public Networks

Problem setting

Before describing our results in detail, let us first define our problem setting. Let P def = {P 1 , P 2 , . . . , P N } denote the set of N parties, participating in an onion routing protocol. We assume that the protocol progresses in global rounds and that an onion sent at round r arrives at its destination prior to round r + 1. Moreover, the adversary is modelled with rushing, i.e., the adversary receives onions sent in round r instantaneously in round r. 1 We assume that the number N of participants and every other quantity in the protocol is polynomially bounded in the security parameter λ.

We define an onion routing protocol to be a protocol in which the honest parties form and process only message packets that are cryptographic onions. To do this, the honest parties use a secure onion encryption scheme which is a triple of algorithms: (Gen, FormOnion, ProcOnion).

See Section 2.1 for more details. During setup of an onion routing protocol, each honest party P generates a public-key pair (pk(P ), sk(P )) ← Gen(1 λ ) using the onion encryption scheme's key generation algorithm Gen. Each party P publishes his/her public key pk(P ) to a public directory so that everyone knows everyone else's public keys.

Let M be the space of fixed-length messages. An input σ = (σ 1 , . . . , σ N ) to the protocol is a vector of inputs, where σ i is a set of message-recipient pairs for party P i . For m ∈ M and P j ∈ P, the inclusion of a message-recipient pair (m, P j ) in input σ i means that party P i is instructed to send message m to recipient P j . In this paper, we consider the following "benchmark" input space, dubbed the simple input/output setting (I/O). An input σ = (σ 1 , . . . , σ N ) is in the simple I/O setting if there exists a permutation function π : P → P such that each party P ∈ P is instructed to send a message to party π(P ) and no other message, i.e., ∀P ∈ P, ∃m P ∈ M such that σ P = {(m P , π(P ))}. The simple I/O setting is a superset of the spaces considered in prior works [3,25,30,31].

Unless stated otherwise, the adversary is active and can observe the traffic on all communication channels and, additionally, can non-adaptively corrupt and control a constant fraction of the parties. By non-adaptively, we mean that the corruptions are made independently of any protocol run.foot_1 Without loss of generality, this type of corruption is captured by allowing the adversary to select the set Bad of corrupted parties prior to the beginning of the protocol run. Once the adversary corrupts a party, the adversary can observe the internal state and computations of the corrupted party and arbitrarily alter the behavior of the party. By V Π,A (1 λ , σ), we denote the view of the adversary A when it interacts with protocol Π on input: the security parameter 1 λ and the instructions σ. The view consists of all the observations that A makes during the run: the values and positions of every onion at every round, the states and computations of every corrupted party between every pair of consecutive rounds, the randomness used by A, and the numbers of messages received by the honest parties. The view does not include the honest parties' randomness. V Π,A,Bad (1 λ , σ) denotes A's view given its choice Bad for the corrupted parties. At the end of the protocol run, each honest party P i outputs the set O Π,A i (1 λ , σ) of (non-empty) messages from the message space M that P i receives from interacting with adversary A in a run of protocol Π on input σ. We define the output O Π,A (1 λ , σ) of protocol Π in an interaction with adversary A on input σ as the N parties' outputs: 3

Our results

We now describe our results. Our construction pertains to the problem setting described in Section 1.1. Our lower bound applies more generally to any arbitrary input set (not necessarily constrained to the simple I/O setting). Following prior work [3,25,30,31], we use a natural game-based definition of anonymity: a protocol is anonymous if the adversary cannot distinguish the scenario in which Alice sends a message to Bob while Carol sends one to David, from one in which Alice's message goes to David while Carol's goes to Bob; (see Definition 4). More precisely, for any pair of inputs (σ 0 , σ 1 ) that agree on the inputs and outputs for the adversarial participants, O Π,A (1 λ , σ 0 ) ≈ O Π,A (1 λ , σ 1 ), where "≈" denotes indistinguishability.

We relate anonymity of an onion routing protocol to two new concepts: An onion routing protocol mixes if it sufficiently shuffles the honest users' onions making it infeasible for the adversary to trace a received message back to its sender. A protocol equalizes if the adversary cannot determine the input from the numbers of messages received by the parties; in other words, the number of messages output by each participant -or the fact that a participant did not receive an output at all -are random variables that are computationally unrelated to the input vector σ. (See Definitions 5 and 7.)

We show that in many cases, mixing and equalizing implies anonymity, i.e., an onion routing protocol that mixes and equalizes is anonymous. (See Theorem 3 for the formal theorem statement.) We use this to prove that our protocol is anonymous. Anonymity also implies equalizing; this observation is useful for proving a lower bound that (almost) matches our protocol.

Anonymous, "robust," and efficient onion routing

As we just explained, our strategy is to construct a protocol that mixes and equalizes.

Intuitively, mixing is the easier one to achieve: the onions need to sufficiently shuffle with other onions traveling over the network to ensure that each of them is hard to trace. This intuition is essentially correct with the caveat that an active adversary can strategically interfere with this process by dropping onions. To ensure that each onion shuffles with a sufficiently large number of onions (formed by an honest party) a sufficiently large number of times, our protocol uses checkpoint onions [3] that each intermediary expects to receive, and if a constant fraction (e.g., one-third) of them don't arrive because the adversary dropped them, the protocol aborts.

An active adversary who controls a fraction of the participants can try to "isolate" an honest party Alice from the rest of the network by dropping all of the messages/onions received directly from Alice. In a fault-tolerant network protocol, the remaining participants may still be able to get their messages through to their destinations. In this case, based on who received an output, an adversary can infer who Alice's intended recipient was. This attack explains why equalizing is difficult to achieve.

To overcome this attack, we introduce a new type of onions, called merging onions. When two merging onions belonging to the same pair arrive at some intermediary I, I recognizes that they are from the same pair (although, other than their next layer and destination, I does not learn anything else about them). The protocol directs I to discard one of them (denoted, pp) and the parties' states (denoted, states). Thus, we could be more precise by denoting the view and the output as V Π,A (1 λ , pp, state, σ) and O Π,A (1 λ , pp, states, σ), but we will use the simpler notation for better readability.

(chosen at random) while sending its mate along. If only one onion of the pair arrived at I while its mate is missing (i.e. the adversary dropped it some time earlier in the protocol run), then I simply sends along the mate that survived, and there is nothing to discard.

Why does this help? Suppose that both Alice and Allison created 2 h merging onions; at rounds r 1 , r 2 , . . ., r h each of these onions (if it hasn't been deleted yet) will meet a mate. Say, exactly one of Alice's onions is dropped by the adversary at some point prior to round r 1 , so its mate (the onion it was supposed to pair with at round r 1 ) was not dropped. Also, suppose that none of Allison's onions were dropped. Then at round r 1 all but one of Alice's remaining merging onions will meet a mate, and half of them will be dropped, so exactly 2 h-1 of Alice's onions will remain in the system -which is exactly how many of Allison's onions remain. Additional h -1 opportunities to merge account for the possibility that the adversary has dropped a larger number of Alice's onions. Merging onions ensure that the number of Alice's onions that remain in the system at the end of the protocol is the same as the number of Allison's onions, i.e., that the protocol equalizes. The fact that Alice was targeted and many of her onions had been dropped upfront doesn't matter because the protocol discards all but one of them anyway! (See Section 4 for a more in-depth description of merging onions and how to construct them.)

Positive result. We construct an onion routing protocol Π ▷◁ , pronounced "Pi-butterfly," because it uses a butterfly network. Π ▷◁ takes advantage of the merging onions technique described above. It is (a) anonymous from the active adversary who can corrupt up to a constant fraction κ < 1 2 of the parties and (b) robust, i.e. whenever the adversary drops at most logarithmic (in the security parameter) number of message packets (i.e. onions), Π ▷◁ delivers the messages from honest senders with overwhelming probability. Moreover, (c) during the execution of the protocol, every honest party transmits up to a polylog (in the security parameter) number of onions: specifically γ 1 log N log 3+γ2 λ onions, where N is the number of participants, and λ is the security parameter. γ 1 and γ 2 are parameters that can be set as desired: increasing them increases the rate at which the maximum distance in the adversarial views for any two inputs shrinks. (See Theorem 12 for the precise relationship.)

Onion encryption schemes

Our work on onion routing builds upon a secure onion encryption scheme [2, 7,24]. Recall that an onion encryption scheme is a triple: (Gen, FormOnion, ProcOnion). The algorithm Gen generates a participant key pair, i.e., a public key and a secret key. The algorithm FormOnion forms onions, and the algorithm ProcOnion processes onions.

Let P be a set of participants, and let Bad ⊆ P be the set of corrupt parties. For every honest P ∈ P \ Bad, let (pk(P ), sk(P )) ← Gen(1 λ , pp, P ) be the key pair generated for party P , where λ is the security parameter, and pp, the public parameters. For every corrupt party P ∈ Bad, let pk(P ) denote P 's public key. Let M be the message space consisting of messages of the same fixed length, and let the nonce space S consist of nonces of the same fixed length. These lengths may be a function of the security parameter λ. Here, a nonce is really any metadata associated with an onion layer.

FormOnion takes as input a message m ∈ M, an ordered list (Q 1 , . . . , Q d-1 , R) of parties from P, the public keys (pk(Q 1 ), . . . , pk(Q d-1 ), pk(R)) associated with these parties, and a list (s 1 , . . . , s d-1 ) of (possibly empty) nonces from S associated with the layers of the onion. 4The party R is interpreted as the recipient of the message, and the list

is the routing path. The output of FormOnion is a sequence (O 1 , . . . , O d ) of onions. Such a sequence is referred to as an evolution, but every O i in the sequence is an onion. Because it is convenient to think of an onion as a layered encryption object where processing an onion O i produces the next onion O i+1 , we sometimes refer to the process of revealing the next onion as "decrypting the onion" or "peeling the onion."

For every i ∈ [d -1], only intermediary party In our constructions, a sender of a message m to a recipient R "forms an onion" by generating nonces and running the FormOnion algorithm on the message m, a routing path (Q 1 , . . . , Q d-1 , R), the keys (pk(Q 1 ), . . . , pk(Q d-1 ), pk(R)) associated with the parties on the routing path, and the generated nonces; the formed onion is the first onion O 1 from the list of outputted onions.

Secure onion encryption. Suppose that (honest) Alice generates an onion carrying a message m for Bob. That is, she generates a string of nonces and runs the algorithm FormOnion on the inputs: the message m, the routing path (Q 1 , . . . , Q i-1 , I, Q i+1 , . . . , Q d-1 , Bob), the public keys associated with the routing path, and the nonces. Let O denote the onion for intermediary party I, i.e., O is the i th onion in the outputted evolution. Suppose that (honest) Carol runs the algorithm FormOnion on the inputs: the message m ′ , the routing path

, David), the public keys associated with the routing path, and some nonces. Let O ′ denote the onion for intermediary party I. Provided that the onion encryption scheme is secure, if party I receives onions O and O ′ in the same round and consequently processes the two onions in the same batch, then the adversary cannot tell which processed onion resulted from processing O and which resulted from processing O ′ . In other words, onions formed by honest parties "mix" at honest parties. For a precise, cryptographic definition of secure onion encryption, see the recent paper by Ando and Lysyanskaya [2].

Onion routing protocols

In an onion routing protocol, all the packets sent between protocol participants are treated as onions; i.e., upon receipt, they are fed to ProcOnion. Moreover, internally, there are type checks that ensure that these onions are processed properly. There are two cases for processing an honestly formed onion properly: the case where peeling the onion reveals its next layer and destination and the case where it reveals a message for the processing party.

If Q i runs ProcOnion and outputs the next layer of the onion O i+1 (together with its destination Q i+i and nonce s i+1 ), then the only two options for what an onion routing protocol permits

Which of these actions are taken depends on the specifics of the algorithm and also on the values (Q i+1 , s i+1 ). In other words, an onion routing protocol cannot have an onion sent to incorrect destinations or fed as input to another algorithm.

Further, if Q i runs ProcOnion and outputs a message m ̸ = ⊥, then this message becomes (ultimately, at the end of the protocol) part of Q i 's output, i.e., it will be on the list of messages that have been sent to Q i . In other words, m cannot be internal to the protocol; it must be a message that someone sent to Q i via the protocol. Conversely, the only way that a message m can be on the list of messages received by Q i is if Q i obtained it by peeling one of the onions it received.

These restrictions on protocol design are natural. Indeed, any implementation of onion routing would ensure that it is adhered to by using type checking of the objects created, sent, and processed by the algorithm. Without such a restriction, any protocol can be thought of I T C 2 0 2 1 9:8

Security definitions: anonymity, equalizing, and mixing A motivating example. Consider Ando, Lysyanskaya, and Upfal's very simple protocol Π p (p, for passive) in the passive adversary setting [3]. Recall that corrupted parties also follow the protocol in this setting. Let Servers ⊆ P be the set of servers which is a subset of P. During the onion-forming phase, every party P generates an onion from the messagerecipient pair (m, R) in P 's input by first choosing d -1 servers (S 1 , . . . , S d-1 ), each chosen independently and uniformly at random from Servers. Next, P forms an onion O by running FormOnion on the message m, the routing path P → = (S 1 , . . . , S d-1 , R), the public keys associated with P → , and the sequence of empty nonces. At the first round of the execution phase, each party P sends its formed onion O to the first server S 1 on the routing path. For every round r ∈ [d], each server S does the following: Between the r th and (r + 1) st rounds, S processes all the onions it received at the r th round. At the (r + 1) st round, S sends the processed onions to their respective next destinations. At the d th round, each party receives an onion that, once processed, reveals a message m for the party. Π p is anonymous if the protocol sufficiently shuffles the onions during the execution phase. In prior work [3], Ando, Lysyanskaya, and Upfal showed that sufficient shuffling occurs when the server load (i.e., the average number of onions received by a server at a round: N |Servers| ) and the number of rounds (i.e., d) are both superlogarithmic in the security parameter. However, there is no parameter setting for which Π p can be anonymous from the active adversary. If κN out of N participants are corrupted, then with probability κ, the adversary can determine the recipient of any honest party, say Alice: Suppose that during 9:9 the onion-forming phase, Alice picks a routing path that begins with an adversarial party S 1 . During the execution phase, the adversary can direct S 1 to drop Alice's onion before the second round. In this case, the adversary can figure out who Alice's recipient is (say, it's Bob) by observing who does not receive an onion at the end of the protocol run.

The motivating example illustrates that while mixing (i.e. sufficiently shuffling onions) is helpful for achieving anonymity, it is not enough. To be anonymous, the protocol must also guarantee that the numbers of messages received by the parties don't reveal the input. We call this property, equalizing.

Here, we provide formal game-based definitions of anonymity (Section 3.1), equalizing (Section 3.2), and mixing (Section 3.3). Given these definitions, it can be shown that for indifferent onion routing protocols, equalizing and mixing imply anonymity:

Anonymity

Anonymity is a property of a messaging protocol Π (i.e., Π doesn't have to be an onion routing protocol).

In the anonymity game (for defining anonymity), the adversary necessarily learns the corrupt parties' inputs and received messages. For example, let N = 4, and let P 3 be a corrupt party. Suppose that the adversary chooses as inputs σ 0 = (σ 0 1 , σ 0 2 , σ 0 3 , σ 0 4 ) and

Then, the adversary can determine the input from P 3 's input. Suppose that the adversary chooses as inputs σ 0 and σ 1 such that σ 0 contains an instruction to send message m 0 to P 3 , whereas σ 1 contains an instruction to send message m 1 ̸ = m 0 to P 3 . Then, the adversary can determine the input from P 3 's received message. Thus, the adversary's choice for (σ 0 , σ 1 ) is constrained to pairs of inputs that differ only in the honest parties' inputs and "outputs."

We define this formally by first defining equivalence classes for inputs as follows. Let Σ be a set of input vectors. Let A be the adversary, and let Bad be the set of parties controlled by A. Fixing Bad imposes an equivalence class on Σ. Each equivalence class is defined by a vector (e 1 , e 2 , . . . , e N ). For each corrupted party P i ∈ Bad, e i = (σ i , M i ) "fixes" the input σ i for P i and also, the set M i of messages instructed to be sent from honest parties to P i . For each honest party P i ∈ P \ Bad, e i = V i "fixes" the number V i of messages instructed to be sent from honest parties to P i . An input vector belongs to the equivalence class (e 1 , e 2 , . . . , e N ) if for every P i ∈ Bad, the input for P i is σ i , the set of messages from honest parties to P i is M i , and e i = (σ i , M i ); and if for every P i ∈ P \ Bad, the number of messages from honest parties to P i is V i , and e i = V i . Two input vectors σ 0 and σ 1 are equivalent w.r.t. the adversary's choice Bad for the corrupted parties, denoted σ 0 ≡ Bad σ 1 , if they belong to the same equivalence class imposed by Bad.

We now describe the anonymity game (below); the protocol Π is anonymous if this induces indistinguishable adversarial views.

The anonymity game. AnonymityGame(1 λ , Π, A, Σ) is parametrized by the security parameter 1 λ , a protocol Π, an adversary A, and a set Σ of input vectors.

Equalizing

Here, we introduce a new concept called equalizing, which is closely related to anonymity. Like anonymity, equalizing is a property of a messaging protocol Π.

Informally, Π equalizes if observing how many messages each party received during the protocol run does not reveal whether the protocol ran on σ 0 or σ 1 . In Π p (in our motivating example), whether Bob receives a message or not exposes who was sending Bob the message: Alice or another party, Allison; so Π p does not equalize. Instead, in an equalizing protocol, the probability that Bob receives a message doesn't depend on the sender's identity. Put another way, Bob is expected to receive the same number of messages in the scenario where Alice is the sender as the one where it is Allison. Formally, equalizing is defined with respect to the equalizing game (below).

The equalizing game. EqualizingGame(1 λ , Π, A, D, Σ) is parametrized by the security parameter 1 λ , a protocol Π, an adversary A, a distinguisher D, and a set Σ of input vectors.

The challenger for the equalizing game first interacts with the adversary exactly the same way as the challenger for the anonymity game. (See the previous section, Section 3.1, for the description of the anonymity game.) Recall that at the end of the anonymity game, each honest party P r outputs the set O Π,A r (1 λ , σ b ) of (non-empty) messages from the message space M that it obtained during the execution from processing onions. Let v r be the number of messages that P r received during the run, i.e., v

(These statistics are part of the adversary's view in the anonymity game.)

We define the statistics for the corrupt parties differently since C does not get to observe how many messages the corrupt parties output; indeed it is not even clear what it means for a corrupt party to produce an output. For each recipient P r ∈ Bad, let v r correspond to the number of onions that C has routed to an adversarial participant P ′ such that (1) they had been formed by an honest participant with P r as the recipient; and (2) all the participants after P ′ on the remainder of this onion's route are controlled by the adversary. In other words, v r is the number of onions from honest participants that P r would receive if, internal to the adversary, all the onions are processed and delivered to their next destinations. We define this formally below.

Let msPairs(P r ) denote the set of message-sender pairs for P r . That is, for every (m, P s ) ∈ msPairs(P r ), the input σ s for P s includes the message-recipient pair (m, P r ), i.e., (m, P r ) ∈ σ s . Let receivableOnions(P r ) be the following set of onions: An onion O is in receivableOnions(P r ) if there exists a message-sender pair (m, P s ) ∈ msPairs(P r ) such that i. O was formed by C (on behalf of P s ) by running FormOnion on input the message m, a routing path For each adversarial recipient P r ∈ Bad, we define the statistic v r to be the number of onions in receivableOnions(P r ) that the challenger sent out during the execution.

Let v = (v 1 , v 2 , . . . , v N ). C provides these statistics v alone (and not the rest of the view) to the distinguisher D, who outputs a guess b ′ for the challenge bit and wins the game if b ′ = b, i.e. if it correctly determines whether the challenger ran the protocol on input σ 0 or σ 1 . The definition for equalizing is as follows:

▶ Definition 5 (Equalizing). A messaging protocol Π(1 λ , pp, states, $, σ) equalizes for the adversary class A w.r.t. the input set Σ if for every adversary A ∈ A and distinguisher D, D wins EqualizingGame(1 λ , Π, A, D, Σ) with negligible advantage, i.e., Pr D wins EqualizingGame(1 λ , Π, A, D, Σ) -1 2 = negl(λ).

On the Complexity of Anonymous Communication Through Public Networks

The mixing game. Let OE = (Gen, FormOnion, ProcOnion) be a secure onion encryption scheme. MixingGame(1 λ , Π, A) is parametrized by the security parameter 1 λ , an onion routing protocol Π, and an adversary A.

First, the adversary A and the challenger C set up the parties' keys (exactly as we described above for the anonymity game): A chooses a subset Bad ⊆ P of the parties to corrupt and sends Bad to C. For each honest party in P \ Bad, C generates a key pair for the party by running the onion encryption scheme's key generation algorithm Gen and sends the public keys pk(P \ Bad) of the honest parties to the adversary A. A picks the keys for the corrupted parties and sends the public-key portions pk(Bad) to C.

Next, the input is selected: A identifies a set S ⊆ P \ Bad of honest target senders and a set R ⊆ P, |R| = |S| of target receivers. In addition to S and R, A also decides part of the input; for every non-target sender P s ∈ P \ S, A chooses a message m and a unique non-target recipient P r ∈ P \ R such that P s 's input becomes σ s = {(m, P r )}; and for every target recipient P r ∈ R, A chooses a message m r to be sent to P r . We call the portion of the input that A decides "the partial input vector," and denote it σ. A sends (S, R, σ) to the challenger C. C supplies the rest of the input vector σ = (σ 1 , . . . , σ N ) by choosing a random bijection g from S to R; each P s ∈ S is instructed to send the message m g(Ps) to g(P s ) ∈ R, i.e., σ s = {(m g(Ps) , g(P s )} where the message m g(Ps) was supplied by A as part of the partial input vector.

Next, C interacts with A in an execution of protocol Π on input σ with C acting as the honest parties adhering to the protocol and A controlling the corrupted parties. Whenever the protocol Π specifies for an onion to be formed or processed, C runs the onion encryption scheme's onion-forming algorithm FormOnion or onion-processing algorithm ProcOnion.

Let O R be the set of onions received by the parties in R.

At the end of the execution, A chooses two onions O s , O s ∈ O R and a target sender P s ∈ S and outputs (O s , O s, P s ).

Let an onion O be a "valid challenge onion" if (i) there exists a message m r ∈ M and a target recipient P r ∈ R such that m r is A's choice for the message to be sent to P r , and (ii) O is the last onion to be received by the recipient over the network in the onion evolution generated by C on behalf of one of the target senders running FormOnion on the message m r and a routing path ending in P r .

Let sender(O s ) be the sender of O s , and let sender(O s) be the sender of O s. To maximize his chances of winning the game, the adversary wants both O s and O s to be valid challenge onions such that O s was sent by P s , while O s was not. Formally, if A chose two valid challenge onions, and {P s } ⊂ {sender(O s ), sender(O s)} ⊆ S, then A wins iff P s = sender(O s ). Otherwise, if A did not choose two valid challenge onions, or if {P s } ̸ ⊂ {sender(O s ), sender(O s)} or {sender(O s ), sender(O s)} ̸ ⊆ S, then A wins with probability one-half. See Figure 1 for a quick reference to the mixing game.

We now define mixing as follows.

▶ Definition 7 (Mixing). An onion routing protocol Π(1 λ , pp, states, $, σ) mixes conditioned on the event E for the adversary class A if given E, every adversary A ∈ A wins MixingGame(1 λ , Π, A) with negligible advantage, i.e.,

The protocol computationally (resp. statistically) mixes if the adversaries in A are computationally bounded (resp. unbounded).

Now that we have defined mixing formally, let us walk the reader through our definitional choices. The starting intuition is that this definition needs to capture that it should be hard for the adversary to pinpoint the origin of an onion received by one of the target recipients. This goal comes with a caveat that of course an adversary can determine the sender of an onion that one of the target senders has just created, or, more generally, that hasn't traveled very far and hasn't had a chance to mix with any onions from other target senders. Hence, we need to restrict the set of onions on which the adversary can win to a set of onions that have traveled far and have already had a chance to mix with other onions. This is why we have the requirement that the onion be a valid challenge onion. Intuitively, a valid challenge onion is one that was formed by a target sender and has already arrived at its destination, a target recipient, and now the adversary's job is to figure out where it came from.

Next, let us explain why, to win the game, the adversary must produce two valid challenge onions, and correctly attribute one of them to a sender P s , while the other must have originated with another target sender. What does it mean that the adversary cannot trace an onion? One intuitive approach would be to say: the adversary's chances of winning the game where he picks just one onion and guesses its origin are close to a simulator's chances of winning a game where he just guesses a sender, and the challenger picks the onion uniformly at random and independently of the simulator's guess. The problem with this approach is that we don't know the best strategy for such a simulator and with what probability it would succeed. So our approach is to have the adversary pick a sender and two onions. "Mixing" means that, if it so happens that exactly one of them comes from P s and the other comes from another target sender, then try as he may, the adversary cannot tell which is which any better than by guessing randomly; and if it doesn't happen that way, then the adversary wins with probability one-half.

Checkpoint onions

Our goal is to achieve anonymity by ensuring that our protocol mixes and equalizes in the presence of an active adversary that drops onions. The challenge is: if the adversary drops too many onions, then the remaining ones don't have enough onions to mix with, and so the resulting protocol will not mix. Checkpoint onions give the honest participants a way of checking that there are still enough onions in the system for mixing to be possible.

A checkpoint onion O is a dummy onion (containing the empty message ⊥) formed by a party P that travels through the network until, at a pre-determined checkpoint round r, it arrives at the intermediary I, who is expecting it. If it fails to arrive, then I is alerted to the activity of an active adversary. More precisely, let F • (•, •) be a pseudo-random function over two inputs, keyed by sk(P, I) which is a secret key shared between P and I. Let b be a binary predicate. Let D be the diagnostic rounds; the honest parties test whether enough onions remain in the system after these rounds. For each intermediary I and each round r ∈ D, P determines whether or not to create a checkpoint onion that will arrive at I at round r by computing f = F (sk(P, I), (r, 0)) and then checking if b(f ) = 1; if so, P creates this checkpoint onion. Similarly, the intermediary I will know to expect a checkpoint onion from P at round r by computing f = F (sk(P, I), (r, 0)) and then checking if b(f ) = 1.

P forms O by running FormOnion on input the empty message ⊥, a randomly chosen routing path P → = (I 1 , . . . , I d ), the public keys associated with parties on P → , and a sequence (s 1 , . . . , s d-1 ) of nonces. The nonce s r which will be received by I, is the value that I will know to expect: s r = F (sk(P, I), (r, 1)); the rest are random nonces. The reason that I will know to expect s r is that I can compute it too, since sk(P, I) is shared between P and I. Of course, the shared key sk(P, I) need not be set up in advance: it can be generated from an existing PKI, e.g., using Diffie-Hellman.

If the adversary drops an onion belonging to the same evolution as O before it reaches I, I will detect it: it will detect that no onion with nonce s r was received in round r. (Since F is pseudorandom, it is highly unlikely that another onion peels to the same nonce value.)

Merging onions

Checkpoint onions help with mixing, but not with equalizing. If our routing protocol just has every sender form one "message-bearing" onion to its recipient and send it along in addition to a set of checkpoint onions (as in the protocol Π a of Ando, Lysyanskaya, and Upfal [3]), then an adversary who targets the sender Alice can cause Alice's recipient Bob to receive the message with a smaller probability than her alternative recipient, Bill; so this protocol will not equalize and, from Theorem 6, has no hope of achieving anonymity.

So how can we design a protocol that equalizes? One approach is to detect when the adversary drops any onions at all (e.g., using verifiable shuffling) [25,30] and abort when that happens. While this approach equalizes, it is not at all fault-tolerant. To achieve fault tolerance and equalizing, the protocol must be able to react to the adversary dropping onions in a way that is less dramatic than total abort. This can be accomplished by using a new tool: merging onions. The idea here is that a sender P can create two onions, O 1 and O 2 that bear the same message to the same recipient R. Further, they will be routed through the same intermediary I, arriving at I at the same round r. Let O ′ 1 (resp. O ′ 2 ) denote the r th layer of O 1 (resp. O 2 ) that arrives at I at round r. When I peels both O ′ 1 and O ′ 2 , I discovers that they are (essentially) the same onion, and only forwards one of them to the next destination. If I receives just one of them (because the other one had been dropped by the adversary), then it forwards it to the next destination too.

The onion-forming phase. During the onion-forming phase, each honest party P creates two types of onions: merging onions and checkpoint onions.

On input {(m, R)}, P forms a set of x merging onions using the number y of rounds in an epoch, the message m, and the recipient R.

In addition to merging onions, P generates (on average) x checkpoint onions using the set D = {y, 2y, . . . , (log x + 1)y} as the diagnostic rounds. (Appropriate functions are chosen for F • (•, •) and b(•) such that P generates x checkpoint onions in expectation. See Checkpoint onions in Section 4 to recall how these functions are used for generating checkpoint onions.) For both merging onions and checkpoint onions, the length of the routing path is fixed; it is (log x + 1)y + 1.

The execution phase. All onions are created during the onion-forming phase and released simultaneously in the first round of the execution phase.

After each round r of the execution phase, P peels all onions it received at the r th round and merges mergeable onions (i.e., if two onions peel to the same nonce value, drop one of them at random).

If r is a diagnostic round (i.e., r ∈ D), P runs the following diagnostic test: Let Ckpts(P, r) denote the set of checkpoints that P expects to see from peeling the onions between rounds r and r + 1. P counts how many checkpoints from Ckpts(P, r) are missing. If the number exceeds a fixed threshold value t, then P aborts. Otherwise, P continues for another round by sending the processed onions to their respective next destinations in random order. At the end of the execution phase, P peels the onions it received at the last round and outputs the set of (non-empty) messages it received.

▶ Remark 8. Π x,y,t △ is anonymous from the adversary who corrupts up to κ fraction of the parties when (i) the onion encryption scheme is secure, (ii) the number x of onions formed by each (honest) party is Ω 2 ⌈log(χ(log χ+1))⌉ where χ = max( N log 2+ϵ λ, log 2(1+ϵ) λ), (iii) the number y of rounds per epoch is Ω log 1+ϵ λ , and (iv) the threshold t is 2(1 -δ)(1κ) 3 κ log 1+ϵ λ. (See the full version of the paper for the proof.) The reason that Π x,y,t △ needs so many onions is that the adversary can target Alice and drop a lot of her onions before the honest participants realize (via checkpoint onions) the presence of an attack and abort. The protocol Π ▷◁ presented in the next section improves on this by giving the routing paths enough structure that missing onions can be detected sooner.

The butterfly network and variants

Recall [26,Chapter 4.5.2] that the butterfly network B = (V (B), E(B)) is a directed graph on (n + 1)2 n vertices. The vertices are organized into N = 2 n rows and n + 1 columns, so each vertex has an address (r, c) where 1 ≤ r ≤ N and 0 ≤ c ≤ n. Vertices in column i represent potential locations of a data packet (here, an onion) at epoch i;

each participant P has a dedicated row. An edge from (P, i) to (Q, i + 1) means that an onion can travel from participant P to participant Q in epoch i. The edges of the specific butterfly network that will be useful for us are E(B) = {((P, i), (Q, i + 1)) | P = Q or binary representations of P and Q differ in position i + 1 only}.

Let J and J ′ be two participants whose binary representation differs in bit i + 1 only. In Π ▷◁ , epoch i is dedicated to having an onion bounce y times between J and J ′ . This way, by the end of the epoch, the onions that J and J ′ held at the beginning of the epoch will be mixed together if one of them is honest. More formally, the onions travel along the edges of a stretched butterfly network, defined as follows: its N (ny + 1) vertices are organized into N rows and ny + 1 columns; and its edges are: E(β) = {((P, j), (Q, j + 1)) | for i = ⌊j/y⌋, ((P, i),

However, what if both J and J ′ are adversarial? Then sending the onions through the stretched butterfly network just once will result in the adversary knowing the i th bit of an onion's destination! So to prevent this, we will send the onions through the iterated stretched butterfly network. For an integer z, let β z denote the stretched butterfly network iterated z times. More precisely, β z is a directed graph in which the vertices are organized into N rows and nyz + 1 columns, i.e., a vertex has an address (r, c) where 1 ≤ r ≤ N and 0 ≤ c ≤ nyz. The edges are as follows:

To summarize, we begin with a butterfly network B, then we stretch it by y to get β, then we iterate it z times to get β z ; see Figure 2. By a "walk through β z " we mean a sequence (J 0 , . . . J nyz ) such that, for each i < nyz, ((J i , i), (J i+1 , i + 1)) ∈ E(β z ). A random walk from a node J 0 is a sequence that begins with J 0 such that for i > 0, each J i is a walk selected uniformly at random conditioned on the first i elements being (J 0 , . . . , J i-1 ). A random walk starting at any address can be sampled efficiently.

The onion-forming phase

On input {(m, R)}, each honest party P generates exactly x merging onions and (on average) x checkpoint onions. To form an onion, P first needs to pick a path for it. Each onion will (potentially) travel to d def = (nyz + 1) + y log x + 1 parties to reach its destination: the first nyz + 1 steps involve a random walk through the iterated stretched butterfly network (the mixing sub-phase), and the next y log x + 1 steps will take the onion through the equalizing sub-phase and to the recipient.

To begin with, P generates the x merging onions as follows: Let T be the binary tree of height log x. Let k be an address of a node in T (i.e., k is a binary string of length at most log x); let v k denote this node. I.e., V (T ) = {v k | k is a binary string, |k| ≤ log x}. To each non-leaf vertex v k in T , P assigns a sequence of y random parties and y random nonces; let

) denote the sequence of vertices and

) denote the sequence of nonces corresponding to vertex v k . (Up until this step, this is exactly how merging onions are formed in Π △ .) For each leaf vertex v ℓ , P picks a random walk through the iterated stretched butterfly β z and nyz + 1 random nonces; let J → v ℓ = (J v ℓ ,0 , . . . , J v ℓ ,nyz ), denote the random walk, and let t → v ℓ = (t v ℓ ,0 , . . . , t v ℓ ,nyz ) be the sequence of nonces. Let v ℓ be a leaf of T . Let v ℓ,i = v ki where k i is the i-bit prefix of ℓ. I.e. v ℓ,ℓ = v ℓ and v ℓ,0 = v ε , and (v ℓ,h , v ℓ,h-1 , . . . , v ℓ,0 ) is the path from v ℓ to the root of the tree, where h = log x. P will create an onion O ℓ for each leaf v ℓ . Its routing path is

where k i is the i-bit prefix of ℓ, and R is the recipient, and such that

) denote the sequence of nonces corresponding to this path. To form the onion O ℓ corresponding to v ℓ , P runs the algorithm FormOnion on the message m, the routing path I → ℓ , the public keys associated with the routing path, and the nonce sequence s → ℓ . After forming the merging onions, P generates the checkpoint onions. Just as in Π △ , the execution phase consists of epochs, and the last round of every epoch is a diagnostic round. Here, each epoch lasts y rounds, thus round r > 0 is a diagnostic round if r is a multiple of y. For each diagnostic round r and for each intermediary I, P uses the pseudorandom function F sk(P,I) (r, 0) to determine whether to form a checkpoint onion to send to I at round r, and if so, calculates the nonce s = F sk(P,I) (r, 1).

When F sk(P,I) (r, 0) = 1, P generates a checkpoint onion to be verified by party I in round r. Recall that d def = (nyz + 1) + y log x + 1; so round d is the last round of the execution phase. Since the checkpoint onion should not be distinguishable from a merging one during the mixing sub-phase, it needs to travel over the edges of the iterated stretched butterfly network for the first nyz + 1 rounds, and follow a random path through the network during the equalizing sub-phase, all the way until the last round d.

As a result, for r ≥ nyz + 1, P generates the routing path by first picking a random walk J 0→nyz = (J 0 , . . . , J nyz ) through the iterated stretched butterfly network starting at a random node J 0 , and then choosing each participant on the next part of the path J nyz+1→r-1 = (J nyz+1 , . . . , J r-1 ) uniformly at random from P. Next, J r = I, and each router on the remaining stretch of the path J r+1→d is, again, chosen uniformly at random from P. So the resulting routing path is J → I,r = (J 0→nyz , J nyz+1→r-1 , J r , J r+1→d ). P chooses the corresponding nonces {s I,r,j } j∈{0,...,d-1}\{r} uniformly at random, sets s I,r,r = s, and gives the resulting routing path, sequence (s I,r,0 , . . . , s I,r,d-1 ) of nonces and the empty message to FormOnion to obtain checkpoint onion O I,r .

If r ≤ nyz, then round r occurs during the mixing sub-phase, as the onion is making its way through the butterfly network. So its path has to be formed in such a way that it arrives at I at round r; but it needs to be a randomly chosen path conditioned on this event (so that a checkpoint onion's path is distributed the same way as one of a merging onion). Let J 0→nyz be a random walk through β z that is at address I at round r. Let each intermediary in the sequence J nyz+1→d be chosen uniformly at random from P. Again, for j ̸ = r, 0 ≤ j ≤ d -1, the nonce s I,r,j is chosen at random, while s I,r,r = s. Let J → I,r = (J 0→nyz , J nyz+1→d ). Run FormOnion on input the routing path J → I,r , sequence of nonces s → I,r and the empty message to obtain checkpoint onion O I,r . ▶ Remark 9. In both Π △ and Π ▷◁ , the onion layers are tagged with their respective round number to prevent replay attacks. If by peeling an onion received at round r, an honest relaying party observes a round number r ′ ̸ = r, the party drops the onion. (We can, therefore, assume that replay attacks do not happen. We can safely do so since the security of the onion encryption scheme prevents the adversary from modifying the onions formed by honest participants in any meaningful way. See, for example Ando and Lysyanskaya's work on onion encryption [2], for a sufficiently strong construction.)

The execution phase

At the beginning of the execution phase, each party P is live. P 's status will change from live to aborted if it ever receives a special abort message from another party. An aborted party sends the special abort message to a random sample of x parties. (A slight technicality is that, since all messages must be onions, the abort message is a specially formed onion.)

For each r ∈ {0, . . . , d -1}, each live honest party P first peels all the onions it received at the r th round. It merges onions that are mergeable: if it received two onions that have the same nonce, then it drops one of them, selected at random, and sends the other one to its next destination.

If r is a diagnostic round (i.e., a multiple of y), then P runs the diagnostic test: P compares the number of checkpoint onions it expects to receive with the number it received. For every participant Q ∈ P, if F sk(Q,P ) (r, 0) = 1, then P expects to receive a checkpoint onion with nonce s = F sk(Q,P ) (r, 1) in this round. In the mixing sub-phase, if fewer than t checkpoint onions are missing so far in the protocol run (not just in this round, but cumulatively), then P continues the run by processing all the other onions.

Otherwise, P 's status changes: it is no longer live but becomes an aborted party. In the equalizing sub-phase, change status to aborted if there are t or more missing checkpoint onions in this round, else continue. At the last round (round d) of the execution phase, P peels the onions it received and outputs the set of (non-empty) messages it received.

Proof that Π ▷◁ is anonymous, robust, and efficient

In this section, we will prove that there exists a parameter setting (for x, y, z, and t) such that Π ▷◁ is simultaneously anonymous, fault-tolerant, and efficient. Our measure of efficiency is onion cost per user, which measures how many onions are transmitted by each user in the protocol. This is an appropriate measure when the parties pass primarily onions to each other. It is also an attractive measure of complexity because it is algorithm-independent: If we measured complexity in bits, it would change depending on which underlying encryption scheme was used. Since an onion contains as many layers as there are intermediaries, its bit complexity scales linearly with the number of intermediaries. (We assume that every message m can be contained in a single onion.) To translate our lower bound from onion complexity to bits, we will consider onions to be at least as long (in bits) as the message m being transmitted and the routing information. More formally, (1 λ , σ) denote the number of onions formed by an honest party that party P i transmits directly to another party in a protocol run of Π with adversary A, security parameter λ and σ. The onion cost of Π is OC

The expectation is taken over the input σ ←$ Σ, the party P i ←$ P, and the randomness $ of the protocol.

For an adversary class A, the onion cost of Π interacting with A w.r.t. Σ is the maximum onion cost over the adversaries in A, i.e., OC Π,A (1 λ , Σ) def = max A∈A OC Π,A (1 λ , Σ).

Our formal notion of fault tolerance is robustness, defined below: ▶ Definition 11 (Robustness). A messaging protocol Π is robust if in every interaction in which the adversary drops at most a logarithmic (in the security parameter) number of message packets, Π delivers all messages sent out by honest participants w.o.p.

Let A κ denote the class of active adversaries who can corrupt up to a constant κ fraction of the participants. In this section, we will prove the following upper bound on onion cost: ▶ Theorem 12. For any constants κ < 1 2 and γ 1 , γ 2 > 0, there is a setting of x, y, z, and t such that Π x,y,z,t ▷◁ is robust and anonymous from the adversary class A κ with onion cost at most γ 1 log N log 3+γ2 λ (in the presence of A κ ), where λ is the security parameter and N = ω(log λ) is the number of participants.

Proof. Recall that the number of corruptions is κ < 1 2 . Set ϵ 1 such that γ 1 = 6ϵ 3 1 and ϵ 2 such that γ 2 = 3ϵ 2 . Let x = y = z = ϵ 1 log 1+ϵ2 λ. Let an onion (layer) be commutable if (i) an honest party formed it, and (ii) it is not a checkpoint onion for verification by an adversarial party (more precisely, it does not belong to the same evolution as a checkpoint onion for verification by an adversarial party); and let t = W 3 , where W = (1-κ)x z log N +log x is the expected number of commutable checkpoint nonces at a party at a diagnostic round.

Having set the parameters, we wish to show that the protocol Π x,y,z,t ▷◁ (a) is robust; (b) has onion cost OC ≤ γ 1 log N log 3+γ2 λ; and (c) is anonymous, provided that the underlying onion encryption scheme is secure.

Part (a) is true by inspection.

To see why (b) follows, recall that each participant forms x merging onions and, on average, x checkpoint onions; let X be the maximum number of onions formed by an honest party. Each of these onions will need to be processed in each round, so OC ≤ Xd, where d is the number of rounds. Using Chernoff bounds, X < 3x with overwhelming probability. The number of rounds is d = (nyz + 1) + y log x + 1; for our setting of parameters, therefore, OC ≤ 6ϵ 3 1 log N log 3(1+ϵ2) λ. We show part (c) via a series of lemmas that follow. First, we invoke the UC composition theorem of Canetti [8] in order to replace cryptographic algorithms for onion encryption with ideal encryption; this allows our further analysis to assume that onions reveal nothing to an intermediary I other than the information that is intended for I (Lemma 13). Let Π ideal ▷◁ be the resulting protocol. Next, we argue that Π ideal ▷◁ is an indifferent onion routing protocol (Lemma 15). This is helpful because then we will be able to invoke Theorem 3. Third, we discard, for the purposes of analysis, all the checkpoint onions that are checked by the adversary; we show that if a protocol mixes (resp. equalizes) in this setting, then it mixes (resp. equalizes). Finally, we show that in this setting, Π ▷◁ mixes (Lemma 16) and equalizes (Lemma 17). Then, putting it all together, we get our desired result. ◀ ▶ Lemma 13. Let Π be onion routing protocol that makes use of an onion encryption scheme that is UC-secure [8] under a computational assumption A. Let Π ideal be the same protocol, but the onion encryption scheme is replaced by the ideal onion encryption functionality of Camenisch and Lysyanskaya [7]. If Π ideal is anonymous, then Π is anonymous under assumption A.

Proof. The Lemma follows by the UC composition theorem of Canetti [8]. ◀ ▶ Remark 14. Since CCA2-secure public-key encryption UC-realizes the ideal public-key encryption functionality of Canetti, and in Π ▷◁ , the adversary already knows how many layers of a given onion have already been peeled, forming onions by using CCA2-secure encryption to encrypt each layer will also result in an anonymous Π ▷◁ .

▶ Lemma 15. Π ideal ▷◁ is indifferent.

Proof. In Π ideal ▷◁ , the length of each routing path is fixed, and the intermediaries and nonces of honestly formed onion layers do not depend on the input σ to the protocol. The procedure for generating intermediaries and nonces takes as input only the values x, y, and z. Thus, by definition, Π ideal ▷◁ is indifferent. ◀

For the subsequent lemmas (Lemmas 16-18), we analyze only commutable onions.

▶ Lemma 16. With parameters x, y, z, and t defined as above, Π ideal ▷◁ mixes for the adversary who corrupts up to half of the parties.

▷◁

delivers messages in the final round d, then w.o.p., the adversary dropped (at most) a constant fraction of the commutable checkpoint onions before the last epoch: The adversary cannot drop more than a constant fraction of all commutable onions without also dropping a proportional number of checkpoint onions. This is because if the adversary were to drop more than a constant fraction of all commutable onions, then, from known probability concentration bounds [22], w.o.p., the adversary would drop close to a proportional number of checkpoint onions, which, in turn, would cause all honest parties to abort the run. Combining this with Chernoff bounds we get: during each round of the penultimate epoch e, each honest party processed a polylogarithmic (in the security parameter) number of commutable onions. From Chernoff bounds, we also get: during epoch e, each commutable onion went to an honest party a polylogarithmic number of times. Thus, either the Π ideal ▷◁ aborts, or it sufficiently shuffles the commutable onions during the penultimate epoch since shuffling for a polylogarithmic number of rounds with a polylogarithmic number of other onions is sufficient for mixing. Either way, Π ideal ▷◁ mixes. ◀ ▶ Lemma 17. With parameters x, y, z, and t defined as above, Π ideal ▷◁ equalizes for the adversary who corrupts up to half of the parties, who also receives everything about noncommutable onions as an auxiliary input.

Before proving Lemma 17, let us prove the following: ▶ Lemma 18. Let Π ideal ▷◁ run with parameters x, y, z, and t are as defined above on input σ, with A corrupting up to half of the participants, and receiving an auxiliary input about non-commutable onions as an auxiliary input. If there is an unaborted honest party at the beginning of the equalizing phase, then with overwhelming probability for each honest party P , at least 1-κ 9 of P 's merging onions remained undropped by the adversary at the end of the mixing phase. (Recall that κ is the corruption rate.) I T C 2 0 2 1

On the Complexity of Anonymous Communication Through Public Networks

Proof sketch. In the first round, the adversary A knows the sender of each commutable onion. As the protocol progresses, A loses track of this information. Thus, A's optimal tactic is to target Alice upfront by dropping every onion that might have come from Alice that is routed to an adversarial party during the first three rounds of the first epoch (as well as the last round of the epoch).

In the first round, some of Alice's onions route to a corrupt party; A drops all of these. However, from Chernoff bounds, w.o.p., at least a constant fraction of Alice's onion go to an honest party first. Let O be such an onion, and let P be the honest party that receives O in the first round. Recall that during each epoch of the mixing phase, P shuffles onions back and forth with another party P ′ . A can attempt to drop O if P ′ is corrupt. However, even if P ′ is corrupt, A cannot drop O if it arrives at P first and remains at P during rounds 2 and 3 (and return to P at round y) -so, using probability concentration bounds, 1-κ 9 of the time. Thus, even if A employs the optimal tactic for dropping Alice's onions, (at least) 1-κ 9 of Alice's onions will make it to the equalizing phase. Since A cannot do better than this, this proves Lemma 18.

◀ Proof sketch of Lemma 17. From Lemma 18, if Π ideal ▷◁ continues into the equalizing phase, then a constant fraction of each honest party's merging onions are still in play at the start of the equalizing phase. However, Lemma 18 does not guarantee that there will be an epoch i > nyz such that the number of Alice's merging onions at epoch i, numMO Alice,i , will be close to that of Allison's, numMO Allison,i . To prove that Π ideal ▷◁ equalizes, we need to show that there exists an epoch i ≤ d such that (for any two parties Alice and Allison), numMO Alice,i ≈ numMO Allison,i . If A doesn't drop any commutable onions during the equalizing phase, then this condition is satisfied by the merging of onions.

So what can A do? The only information that A has for guessing where any commutable onion came from is which onions are part of a mergeable pair and which are not; this is because the onions are shuffled during the mixing phase and each epoch of the equalizing phase. Let a singleton be a commutable onion that is not part of a mergeable pair; note that it can be either a checkpoint onion or a merging onion. W.l.o.g., suppose that A dropped more of Alice's onions upfront (during the mixing phase) than Allison's. Then, at the start of the equalizing phase, it is likely that more singletons are Alice's merging onions than Allison's merging onions. So, A can attempt to prevent the numbers of merging onions from evening out by dropping singletons. We can show that the best that A can do is to drop as many singletons as possible (without causing the protocol to be aborted) at the beginning of the equalizing phase. (Of course, A could also drop onions that belong in a mergeable pair, but this would only help to even out the numbers of merging pairs.) Even if A does this, there exists an epoch i ≤ d such that numMO Alice,i ≈ numMO Allison,i .

Armed with Lemma 18 and the above analysis, we can prove that Π ideal ▷◁ equalizes. If the adversary drops too many onions during the mixing phase, then Π ideal ▷◁ equalizes since every honest party stops participating (Lemma 18), and so no one receives their message. Otherwise, Π ideal ▷◁ equalizes since enough of each sender's merging onions make it to the equalizing phase (Lemma 18), and the numbers of merging onions are eventually evened out by the merging of onions (above). ◀

Our lower bound: polylog onion cost is required

In this section, we present our lower bound: an onion routing protocol can be anonymous from the active adversary only if the onion cost is superlogarithmic in the security parameter. Our lower bound holds for protocols that are minimally functional for the active adversary.

We call this notion weakly robustness, defined below. The reason this definition is weaker than robustness (Definition 11) is that here we only insist that the protocol guarantee delivery for senders whose onions are never dropped.

▶ Definition 19 (Weakly robust). Let Π(1 λ , pp, states, $, σ) be an onion routing protocol and let A be an adversary attacking Π that drops at most O(log(λ)) onions. Π is weakly robust if whenever A doesn't drop any onions sent by honest party P , P 's message will be delivered to its recipient with overehlming probability.

▶ Theorem 20. If the onion routing protocol Π(1 λ , pp, states, $, σ) is weakly robust and (computationally) anonymous from the adversary A who corrupts up to a constant fraction of the parties and drops at most f (λ) = O(log(λ)) onions, then the onion cost of Π interacting with A is ω(f (λ)).

Proof sketch. Let us give the intuition for the proof of this theorem. If an honest P i sends out only O(log(λ)) onions, then an adversary that chooses which participants to corrupt uniformly at random has a 1/λ O(1) chance of controlling each and every participant that ever receives an onion directly from P i . (This is because O(log(λ)) = O(log(N )), since λ and N are polynomially related.) Thus with non-negligible probability it can cut off P i entirely by dropping all of the onions it sends out, guaranteeing that the intended recipient of P i 's message never receives the message; yet, by weak robustness (Definition 19), we can show that there will be some recipient whose probability of receiving his message is high. Therefore, Π will not equalize (Definition 5): based on who failed to receive the message, it is possible to determine whether P i 's intended recipient was Bob or Bill. Since it does not equalize, by Theorem 6, it is not anonymous. See the full version of this paper for the proof. ◀