Yale University Department of Computer Science

Security Analysis of Accountable Anonymous Group Communication in Dissent Ewa Syta Aaron Johnson Henry Corrigan-Gibbs Shu-Chun Weng David Wolinsky Bryan Ford YALEU/DCS/TR-1472 January 31, 2013

Abstract Users often wish to communicate anonymously on the Internet using, for instance, group discussion forums or instant messaging. Misbehaving users may abuse this anonymity to disrupt communication, however, and existing solutions do not adequately address this risk. Messaging protocols such as DC-nets leave groups vulnerable to denial-of-service and Sybil attacks, mixnets are difcult to protect against trafc analysis, and accountable voting protocols are unsuited to general anonymous messaging. DISSENT , originally introduced by Corrigan-Gibbs and Ford (2010), is the rst general communication protocol that offers provable anonymity, integrity and accountability for moderatesize groups, and efciently handles unbalanced loads where few members wish to transmit in a given round. We provide a full description of an improved DISSENT protocol, dene its precise security properties, and give rigorous proofs of these properties. Our improved protocol is a direct result of this security analysis, which identied several non-trivial attacks on the original protocol stemming from subtle design aws.

Security Analysis of Accountable Anonymous Group Communication in Dissent

Ewa Syta Aaron Johnson Henry Corrigan-Gibbs Bryan Ford Shu-Chun Weng David Wolinsky

Introduction

Anonymous participation is often considered a basic right in free societies (Yale Law Journal 1961). The limited form of anonymity the Internet provides is a widely cherished feature (Teich, Frankel, Kling, and Lee 1999; Wallace 1999), enabling people and groups with controversial or unpopular views to communicate and organize without fear of personal reprisal (Stein 2003). Yet anonymity makes it difcult to trace or exclude misbehaving participants (Davenport 2002). Online protocols providing stronger anonymity, such as mix-networks (Chaum 1981; Adida 2006), onion routing (Goldschlag, Reed, and Syverson 1999; Dingledine, Mathewson, and Syverson 2004), and Dining Cryptographers Networks or DC-nets (Chaum 1988; Waidner and Ptzmann 1989; Sirer et al. 2004; Golle and Juels 2004), further weaken accountability, yielding forums in which no content may be considered trustworthy and no reliable defense is available against anonymous misbehavior. DISSENT (Dining-cryptographers Shufed-Send Network) is a communication protocol that provides strong integrity, accountability and anonymity. Members of small, private online groups, whose membership is closed and known to its members, are able to send anonymous messages to each other, to the whole group, or to a non-member, in that the receiver knows that some member sent the message, but no one knows which member. DISSENT holds members accountable, not by compromising their anonymity but rather by ensuring that communication resources are allocated among all communicating members, and that any disruption results in the identication of some malicious member during a blame process. Members are thus unable to corrupt or block other members messages, overrun the group with spam, stuff ballots, or create unlimited anonymous Sybil identities (Douceur 2002) or sock puppets (Stone and Richtel 2007) with which to bias or subvert the groups deliberations. DISSENT builds on the shufe of Brickell and Shmatikov (2006a), combining that with DC-net techniques for efcient bulk communication. It uses only readily available cryptographic primitives and handles arbitrarily large messages and unbalanced loads efciently. Each member sends
The work of Ewa Syta, Henry Corrigan-Gibbs, Shu-Chun Weng, David Wolinsky, and Bryan Ford (email: [email protected]) was supported by the Defense Advanced Research Projects Agency (DARPA) and SPAWAR Systems Center Pacic, Contract No. N66001-11-C-4018. Aaron Johnson (email: [email protected]) was supported by DARPA. Any opinions, ndings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reect the views of DARPA or SPAWAR. Department of Computer Science, Yale University, CT U.S. Naval Research Laboratory

exactly one message per round, making it usable for voting or assigning pseudonyms with a 1-to1 correspondence to real group members. DISSENT has limitations, of course. It is not intended for large-scale, open-access anonymous messaging or le sharing (Goldschlag, Reed, and Syverson 1999; Clarke, Sandberg, Wiley, and Hong 2000). DISSENTs accountability property assumes closed groups, and may be ineffective if a malicious member can leave and rejoin the group under a new (public) identity. Finally, DISSENTs serialized GMP - SHUFFLE protocol imposes a per-round startup delay that makes DISSENT impractical for latency-sensitive applications. Further discussion on related anonymous communication systems is included in Section 6. DISSENT was rst introduced by Corrigan-Gibbs and Ford (2010). In addition to sketching the protocol and security arguments, they describe practical usage considerations and give the results of several performance experiments based on a prototype implementation. We focus here on a detailed exposition of DISSENT and a rigorous analysis of its security properties. Indeed, during our analysis of the original protocol, we identied several attacks. For example, anonymity could be broken by replaying protocol inputs in subsequent rounds, by providing at certain points incorrect ciphertexts to some members and correct ones to the rest, or by copying ciphertexts at other points. Accountability for disruption could be avoided by copying the protocol inputs from honest members, and honest members could potentially be falsely accused of disruption by rearranging valid signed messages to create phony logs. Protocol termination could be prevented for some members by causing failures for them while allowing the rest to terminate successfully and thus not participate in a blame process. See the appendix more details of these attacks. In order to x these aws, we made several non-trivial modications to the original protocol. To prevent replay attacks we added key generation steps. To prevent equivocation attacks we added rebroadcast steps, and have members intentionally cause intermediate protocol failures when equivocation is observed. We add the use of non-malleable commitments to prevent submission duplication, and we add phase numbers to prevent log forgery. Finally, to prevent non-termination of the protocol, we make all steps non-optional, in particular including an opportunity for blame at the end of every execution to ensure accountability. We are able to give proofs of security for this improved protocol. In particular, we provide rigorous proofs of integrity, accountability, and anonymity. Obtaining a fully secure protocol with proofs required a surprising amount of additional work given the relative simplicity and maturity of the underlying ideas. However, as observed by Wikstr om (2004), the complexity of anonymous communication protocols has frequently resulted in incomplete proofs and subtle errors (see further discussion in Section 6). The main contributions of this paper, therefore, are (1) we provide a full description of an improved DISSENT protocol, (2) we present precise denitions of its security properties, and (3) we give rigorous proofs that the protocol satises those denitions. Section 2 outlines DISSENTs framework and security model. Section 3 describes the GMP SHUFFLE protocol, and Section 4 details the GMP - BULK transfer protocol. Section 5 provides formal security properties and their proofs. Section 6 summarizes related work, and Section 7 concludes.

Protocol Overview

is designed to be used in a group setting. Each member i of the group is associated with a long term public signing key pair (ui , vi ). DISSENT provides a shufed send communication primitive that gives sender anonymity among that group. During each protocol run, every group
DISSENT

member i secretly creates a message mi and submits it to the protocol. The protocol effectively collects all secret messages, shufes their order according to some random permutation that no one knows, and broadcasts the resulting sequence of messages. Each input message mi can have a different length Li . We present a messaging interface, called the General Messaging Protocol, that DISSENT implements. DISSENT in fact denes two protocols implementing this interface: the GMP - SHUFFLE protocol provides anonymous communication for xed-length messages, and the GMP - BULK protocol builds on this to provide efcient anonymous communication of arbitrary-length messages.

2.1

The General Messaging Protocol

A Group Messaging Protocol GMP is a 3-tuple of algorithms SETUP (vi ), ANONYMIZE (mi , K, nR , , f ) and VERIFY- PROOF(pj , i ). SETUP takes a members public signing key vi as input and outputs one or more session nonces nR , a set K of all members signing keys, an ordering of members , and optionally a message length L. All group members run the SETUP algorithm before each protocol run to agree on common parameters. Such agreement might be achieved via Paxos (Lamport 1998) or BFT (Castro and Liskov 1999). We emphasize that SETUP does not generate members signing keys; rather, it uses long term signing keys submitted by each member. ANONYMIZE takes a message mi , a set K of members signing keys, one or more round nonces nR , an ordering of members , and optionally a ag f as input, and outputs either (SUCCESS, Mi ), where Mi is a set of messages, or (FAILURE, BLAMEi , i ), where BLAMEi is a set of observed misbehaviors, and i is a log of a protocol run. After agreeing on common parameters, the group runs the ANONYMIZE algorithm. The goal of the algorithm is to anonymously broadcast the set of messages submitted by group members. If a protocol run succeeds for a member, then she outputs the anonymized messages. Otherwise, the protocol run fails and the group member produces a set of blame proof(s) for the member misbehavior(s) responsible for the protocol run failure. VERIFY- PROOF takes a proof pj of member j s misbehavior and a log i as input, and outputs either TRUE indicating that pj is indeed a proof of j s misbehavior given the observed protocol history represented by log i , or FALSE otherwise. If a run of ANONYMIZE fails for member i, then i blames at least one dishonest member j by producing a proof pj of j s misbehavior and a log i . VERIFY- PROOF is used to verify that proof pj does in fact indicate misbehavior by j given i .

2.2

The GMP-Shufe Protocol

The GMP - SHUFFLE protocol enables the anonymous exchange of equally sized messages. However, it incurs extra communication if only one member wishes to send, and its decrypt-and-shufe phase is inherently serial. GMP - SHUFFLE builds on a data mining protocol by Brickell and Shmatikov (Brickell and Shmatikov 2006b) to broadcast the input set of xed-length messages, one from each group member, in an unknown permutation, providing cryptographically strong anonymity. Like many anonymous messaging protocols, the original data mining protocol was vulnerable to untraceable denial-of-service (DoS) attacks by malicious group members. We remove this vulnerability by adding go/no-go and blame phases, which can trace and hold accountable any group member maliciously disrupting the protocol. In the GMP - SHUFFLE protocol, all members 1, . . . , N choose their secret messages m1 , . . . , mN of equal length L. Each member has a long lived signing key pair (ui , vi ) and knows the ordering of 4

the group and a session nonce nR . For a single run of the protocol, each member generates two key pairs, called inner and outer, and shares the public keys with the group. Each member i iteratively encrypts its message mi using all inner and then all outer public keys. The resulting ciphertext messages are sent to a group leader who strips one layer of encryption from each ciphertext using his outer public key, permutes the messages, and forwards the permuted set to the next member who repeats the process. Removing all layers of outer encryption yields a set of inner ciphertext messages which member N broadcasts to the entire group. All members inspect the set to verify that their inner ciphertext is present. If all members messages are included and every step of the protocol completes successfully, each member releases its inner private key allowing the set of permuted secret messages to be recovered. If any inner ciphertext is missing or corrupted, however, the inner keys are destroyed and the entire group enters a blame phase to nd the culprit member(s). Section 3 details the GMP - SHUFFLE protocol and Section 5 demonstrates its security.

2.3

The GMP-Bulk Protocol

The GMP - BULK protocol uses ideas from DC-nets (Chaum 1988; Waidner and Ptzmann 1989; Sirer et al. 2004; Golle and Juels 2004) to anonymously transmit variable-length messages. In place of the DoS-prone slot reservation systems in prior DC-nets schemes, however, DISSENT leverages its GMP - SHUFFLE protocol to prearrange the DC-nets transmission schedule, guaranteeing each member exactly one message slot per round. GMP - BULK uses the GMP - SHUFFLE protocol to broadcast an unknown permutation of the message descriptors submitted by each member. Each descriptor di contains the length Li of member is message mi , a cryptographic hash of mi , a vector Si of seeds sij , where each seed is encrypted with j s session public key and assigns each member j a pseudorandom bulk ciphertext to transmit, and a vector Hi of hashes Hij validating each bulk ciphertext. The shufed order of the message descriptors indicates the order in which the anonymous senders should transmit their secret messages. Then, all group members broadcast bit streams based on pseudorandom seeds included in the message descriptors, so that XORing all members bit streams together yields a permuted set of all members variable-length messages. During a members own transmission slot, he transmits his own message XORd with the messages he has instructed all other members to generate. During another group members transmission slot, members broadcast a pseudorandom bit string generated from an encrypted seed in the slots message descriptor. Cryptographic hashes in the message descriptors enable members to verify the correctness of each others bulk transmissions, ensuring message integrity and DoS protection throughout. If any group member sends an invalid bit string, then in a blame phase the owner of that transmission slot uses GMP - SHUFFLE to anonymously broadcast an accusation exposing the faulty group member. The GMP - BULK protocol is detailed in Section 4 and Section 5 proves its security.

2.4

Security Model

We assume the adversary is polynomial-time limited. We allow him to control a colluding subset of group members. We dene the rest of the members as honest, in that they run the prescribed algorithms, and their internal states are hidden from the adversary. We assume that communication channels exist between all members, and that they can be observed by the adversary. The security properties we wish the protocol to satisfy are integrity, accountability, and anonymity, as we describe below. Formal denitions of these properties and their proofs are given in Section 5. 5

 Integrity: The protocol offers integrity if every honest member for whom the protocol completes successfully has the same output and receives the messages of all the other honest members. Accountability: The protocol offers accountability if (i) every honest member for whom the protocol failed obtains proof of some members misbehavior valid under VERIFY- PROOF, and (ii) the adversary cannot produce a valid proof of misbehavior by an honest member. Anonymity: The protocol maintains anonymity if the adversary can guess the sources of the messages from honest users with probability no greater than random guessing. We observe that these properties do not imply that DISSENT completes for all members, and, in fact, we cannot guarantee that the protocol terminates if a member stops participating at some point. However, the protocol execution is very simple: a xed sequence of phases during which all members send no message or all send one message. If a properly signed message indicating the desired protocol run and phase is received from every member, the protocol proceeds to the next round. Therefore every member knows when another should send a message, and thus gossip techniques such as those used in PeerReview (Haeberlen, Kouznetsov, and Druschel 2007) can be applied in a wrapper protocol to ensure liveness. Moreover, we note that when every member follows the protocol, not only does it complete but it succeeds, as will be clear from the protocol description.

2.5

Cryptographic Primitives and Security Assumptions

DISSENT makes use of several cryptographic tools, and its security depends on certain assumptions about their security.

2.5.1

Hash functions

We use a standard denition (Stinson 2005) of a collision-resistant unkeyed hash function and will denote the hash of message m as HASH{m}. We assume that the hash function used is secondpreimage resistant (Rogaway and Shrimpton 2004). Denition 1. A hash function is second-preimage resistance if it is computationally infeasible to nd any second input which has the same output as any specied input, i.e. given x, to nd a second pre-image x = x such that h(x) = h(x ). 2.5.2 Encryption

We use a cryptosystem that consists of: (i) a key generation algorithm taking a security parameter and producing a private/public key pair (x, y ); (ii) an encryption algorithm taking public key y , plaintext m, and some random bits R, and producing a ciphertext c = {m}R y ; (iii) a deterministic decryption algorithm taking private key x and ciphertext c, and returning the plaintext m. A member R1 :RN indicates iterated can save the random bits R used during encryption. The notation c = {m}y 1 :yN 1 . . . }RN . We omit R when an encryptions random encryption via multiple keys: c = {. . . {m}R y1 yN inputs need not be saved. We assume that members can check an arbitrary (x, y ) purported to be a key pair to verify that it could have been generated by the specied key generation algorithm. We also assume that 6

the underlying public-key cryptosystem provides indistinguishable ciphertexts against a chosenciphertext attack. That is, the cryptosystem is IND-CCA2 secure (Bellare, Desai, Pointcheval, and Rogaway 1998). Denition 2. A cryptosystem is IND-CCA2 if, for all probabilistic polynomial-time adversaries, the advantage in the distinguishing game is negligible as a function of the security parameter . The distinguishing game (Bellare, Desai, Pointcheval, and Rogaway 1998; Brickell and Shmatikov 2006a) is played between an adversary A and a challenger C who takes as input the challenge bit b. 1. The challenger C uses to generate a key pair (x, y ) and gives the public key y to the adversary A. 2. A may encrypt polynomially many messages m using y and decrypt polynomially many arbitrary ciphertexts c. To decrypt a ciphertext c = {m}y , A queries c to C , who sends back m = {c}x . 3. Eventually, A chooses two messages m0 and m1 and sends them to C . 4. C computes cb = {mb }y and sends it to A. 5. A may perform polynomially many encryptions of any m, and polynomially many decryptions of any ciphertexts c, provided that c = cb . 6. A outputs a guess b {0, 1} for the value of b. The adversarys advantage in the distinguishing game is equal to P r AC (0) = 1 P r AC (1) = 1 , where the probability is taken over the randomness of the adversary and the challenger. 2.5.3 Digital Signatures

We use a signature scheme that consists of: (i) a key generation algorithm taking a security parameter and producing a private/public key pair (u, v ); (ii) a signing algorithm taking private key u and message m to produce signature = SIGu {m}; and (iii) a deterministic verication algorithm taking public key v , message m, and candidate signature , and returning true iff is a correct signature of m using v s associated private key u. The notation {m}SIGu indicates the concatenation of message m with the signature SIGu {m}. We assume that the underlying digital signature scheme has a strong unforgeability property. That is, it is EUF-CMA secure (Goldwasser, Micali, and Rivest 1995). Denition 3. A digital signing scheme is EUF-CMA secure if, for all probabilistic polynomial-time adversaries, the adversarys advantage in the forging game is negligible as a function of the security parameter . The forging game is played between an adversary A and a challenger C . It is equivalent to a standard EUF-CMA game. 7

1. The challenger C uses to generate a key pair (x, y ) and gives the public key y to the adversary A. 2. A may request signatures on polynomially many messages. A chooses a message m and sends it to C , who sends back , a signature on m under y . A is allowed to query C in an adaptive fashion. 3. Eventually, A outputs a pair (m , ). The adversary wins the forging game if (m , ) is a valid message- signature pair under y assuming that m has never been queried to the challenger. The adversarys advantage is simply the probability of winning the forging game, where the probability is taken over the randomness of the adversary and the challenger. 2.5.4 Pseudo-random Number Generator

We use a standard denition (Stinson 2005) of a pseudorandom number generator (PRNG). Let g (s) be a pseudo-random number generator, where s is a seed. We will denote the rst L bits generated from g (s) as PRNG{L, s}. Denition 4. A function g : {0, 1} 1 () {0, 1} 2 () is a pseudorandom number generator if, for all probabilistic polynomial-time adversaries, the adversarys advantage in the pseudorandomness game is negligible as a function of the security parameter . The pseudorandomness game is played between an adversary A and a challenger C (b). 1. If b = 0, C chooses s {0, 1} 1 () uniformly at random and sets r = g (s). If b = 1, C chooses r {0, 1} 2 () uniformly at random. 2. C sends r to A. 3. A outputs a guess b {0, 1} for the value of b. The adversarys advantage in the pseudorandomness game is P r AC (0) = 1 P r AC (1) = 1 , where the probability is taken over the randomness of the adversary and the challenger. 2.5.5 Non-malleable Commitments

We use the denition by Dolev, Dwork, and Naor (2000) of a non-malleable commitment. The notation x = COMMIT{c} indicates that x is a commitment to c, and the notation c = OPEN{x} indicates that c is the opening of the commitment x.

3
3.1

GMP-Shufe
Protocol Description

The Group Messaging Protocol-Shufe GMP - SHUFFLE is an instantiation of the Group Messaging Protocol and consists of three algorithms: SETUP - S, ANONYMIZE - S, and VERIFY- PROOF - S. Before each protocol run, all members run the SETUP - S algorithm to agree on the common parameters needed for each run. One parameter thus determined is the xed message length L. Each member i pads or trims input message mi to length L. All members use the remaining parameters K , nR , and as inputs to ANONYMIZE - S. This algorithm also takes a fail ag f which is always set to FALSE when the algorithm is run as a part of GMP - SHUFFLE . The fail ag will sometimes be set to TRUE when ANONYMIZE - S is run as a part of GMP - BULK . If a run of GMP - SHUFFLE completes, it can either succeed (Denition 6), revealing a set of anonymized messages, or fail (Denition 7), in which case some faulty member(s) are blamed. The VERIFY- PROOF - S algorithm is used to validate a proof of a members misbehavior produced upon a protocol failure.

3.2

The Setup-S Algorithm

SETUP - S (vi ) takes each members public signing key vi as input, and outputs a session nonce nR , a set K of all members signing keys, an ordering of members , and a xed message length L.

3.3

The Anonymize-S Algorithm

The purpose of ANONYMIZE - S(mi , K, nR , , f ) when run by each member in a group on the collective input messages M is to produce anonymized messages M . ANONYMIZE - S takes a message m of a xed length L, K , nR , , and a fail ag f as input. A protocol run of ANONYMIZE - S succeeds for member i if an internal ag SUCCESSi is set to TRUE after completion of ANONYMIZE - S and fails otherwise. After a successful completion of a protocol run, member i outputs (SUCCESS, Mi ), where, as we show in Section 5, Mi consists of N messages including every message submitted by an honest member. After a protocol failure, member i produces (FAILURE, BLAMEi , i ). BLAMEi includes proofs pj = (j, c) for each member j for whom a check c of her behavior failed in Phase 6 from is point of view. At least one of the following checks always fails for some member j from is point of view provided that SUCCESSi = FALSE. In such situation a proof pj is added to BLAMEi . The checks are listed in the order they are applied by member i during the protocol. Each check is associated with a check number that ANONYMIZE - S uses to form a proof of a particular form of misbehavior, and VERIFY- PROOF - S uses to conrm a record of that misbehavior. Check 1 (c1 ): Incomplete log or equivocation (different versions of messages in released logs). Check 2 (c2 ): Mismatched inner key pair in Phase 5. Check 3 (c3 ): Empty inner private key in Phase 5 without a justifying GOk = FALSE or broadcast-hash inequality. Check 4 (c4 ): Mismatched outer key pair or empty outer private key in Phase 6 regardless of a GOk = FALSE message or broadcast-hash inequality. 9

 Check 5 (c5 ): Invalid public key in Phase 1. Check 6 (c6 ): Invalid commitment in Phase 2a. Check 7 (c7 ): Incorrect commitment or invalid ciphertext or identity in Phase 2b. Check 8 (c8 ): Incorrect set of permuted ciphertexts after decryption in Phase 3. Check 9 (c9 ): Invalid ciphertext(s) after decryption in Phase 3. Check 10 (c10 ): Duplicate ciphertext(s) after decryption in Phase 3. Check 11 (c11 ): Incorrect GOj in Phase 4. Check 12 (c12 ): Incorrect broadcast hash in Phase 4. For every member i, a complete log includes messages sent and received within SETUP - S and the following messages for each phase of ANONYMIZE - S: SETUP - S: All protocol messages. Phase 1: Sent: i1 , received: k1 for all k = i. Phase 2a: Sent: i2a , received: k2a for all k = i. Phase 2b: Sent: i2b , received: if i = 1, then k2b for all k = i, if i = 1, then no message. Phase 3: Sent: i3 , received: if i = 1, then no message, if i = 1, then (i1)3 . Phase 4: Sent: i4 , received: k4 for all k = i. Phase 5: Sent: i5 , received: k5 for all k = i. Phase 6: Sent: i6 , received: k6 for all k = i. Algorithm description. ANONYMIZE - S(mi , K, nR , , f ) Phase 1: Generation of Inner and Outer Key Pairs.
sec , O pub ), Each member i chooses two ephemeral encryption key pairs (Iisec , Iipub ) and (Oi i and broadcasts pub i1 = {Iipub , Oi , nR , 1, i}SIGui .

Member i veries that the messages she receives contain valid public keys. If the verication fails, member i sets an internal ag GOi to FALSE to indicate that a step of the protocol failed. Phase 2a: Data Commitment. Each member i encrypts her datum mi with all members inner public keys, in reverse order pub pub from IN to I1 Ci = {mi }I pub :I pub .
N 1

10

Member i stores the inner ciphertext Ci for later use, then further encrypts Ci with all members outer public keys to obtain the outer ciphertext Ci = {Ci }Opub :Opub .
N 1

If a public key released by some member j was invalid, i generates and uses a random key for j to allow the protocol to go forward. Now member i calculates a non-malleable commitment to Ci and i Xi = COMMIT{Ci , i} and broadcasts i2a = {Xi , nR , 2a, i}SIGui . Member i waits to receive such a message from every other member and then veries that they include valid commitments. If they do not, GOi is set to FALSE. Phase 2b: Data Submission. Member i sends member 1 an opening of her commitment i2b = {OPEN{Xi }, nR , 2b, i}SIGui . Member 1 veries that each i2b successfully opens Xi and that the result is a valid ciphertext and i. If not, member 1 sets GO1 to FALSE. Phase 3: Anonymization. Member 1 collects the results of opening the commitments into a vector C0 = (C1 , . . . , CN ), randomly permutes its elements, then strips one layer of encryption from each ciphertext sec to form C . Member 1 sends to member 2 using private key O1 1 13 = {C1 , nR , 3, 1}SIGu1 . Each member 1 < i < N in turn accepts Ci1 , permutes it randomly, strips one layer sec to form C , then sends of encryption using key Oi i i3 = {Ci , nR , 3, i} SIG ui to member i + 1. Member N similarly creates N 3 and broadcasts it to all members. Member i skips decryption for any invalid ciphertext in Ci1 . Any member i who detects a duplicate or invalid ciphertext in Ci sets GOi to FALSE. Phase 4: Verication. All members now hold CN , which should be a permutation of C1 , . . . , CN . Each member i veries that her own inner ciphertext Ci is included in CN and sets GOi to FALSE if not. If f = TRUE then member i always sets GOi = FALSE regardless of the above verication. If f = FALSE and the GOi ag has not yet been set to FALSE, it is now set to TRUE. Each member i creates a vector B of all broadcast messages - that is, messages for which identical copies should have been delivered to all members - from prior phases: all members public key messages from phase 1, all members commitment messages from phase 2a, and member N s phase 3 message containing CN . Thus, B = (11 , . . . , N 1 , 12a , . . . , N 2a , N 3 ). Member i broadcasts i4 = {GOi , HASH{B }, nR , 4, i}SIGui . 11

 Phase 5: Key Release and Decryption. Case 1. If member i receives GOj = TRUE and HASH{Bj } = HASH{Bi } from every member j , and her GOi = TRUE, then member i destroys her copy of Ci and broadcasts her inner private key Iisec to all members i5 = {Iisec , nR , 5, i}SIGui . Upon receiving messages from every other member, member i veries that each non-empty sec is valid and corresponds to the public key I pub . If member i receives inner private key Ij j at least one empty key or if any key pair fails the verication, then i sets the internal ag SUCCESSi to FALSE . Otherwise, SUCCESSi is set to TRUE and member i removes the N levels of encryption from CN , resulting in Mi = {m1 , . . . , mN }, the anonymized set of messages submitted to the protocol. Case 2. If member i received GOj = FALSE or HASH{Bj } = HASH{Bi } from any member j , or her own ag GOi = FALSE, then member i destroys her inner private key Iisec , and sends to all members an empty string instead of her inner private key. Member i broadcasts i5 = {0, nR , 5, i}SIGui and sets the internal ag SUCCESSi to FALSE. Phase 6: Blame. Case 1. Member is SUCCESSi = TRUE. In this case, member i acknowledges a successful completion of the protocol. Member i creates a vector T of all signed messages she sent and received in Phases 15, and broadcasts i6 = {T , nR , 6, i}SIGui . Now, member i outputs (SUCCESS, Mi ), which completes the protocol. Case 2. Member is SUCCESSi = FALSE and for every member j GOj = TRUE and HASH {Bj } = HASH {Bi }.
pub Member i keeps her outer private key Oi secret, and broadcasts an empty string instead of her key and a vector T of all signed messages she sent and received in Phases 15

i6 = {0, T , nR , 6, i}SIGui . Case 3. Member is SUCCESSi = FALSE and for any member j GOj = FALSE or HASH{Bj } = sec , permutation and a vector T HASH {Bi }. Member i broadcasts her outer private key Oi i of all signed messages she sent and received in Phases 15
sec i6 = {Oi , i , T , nR , 6, i}SIGui .

12

Now, member i continues with the following steps if she executed Case 2 or Case 3. If member i executed Case 1, then the protocol has completed. Upon receiving a message j 6 from every other member j , member i inspects every log T and discards any message in T that is not properly signed or does not have the correct round or phase number. Then, member i veries each member j s T to ensure that it contains all messages sent and received by j in Phases 15 as well as that the contents of all messages included in T match the corresponding messages in the other T logs of other members. For every member j whose T is incomplete or for whom different versions of any message j are revealed, member i sets pj = (j, c1 ), where c1 indicates the failed check number, and adds pj to BLAMEi . If there is an incomplete T or an equivocation is observed, member i creates a log i of the protocol run that consists of all messages sent and received by i during SETUP - S and ANONYMIZE - S . Then, member i outputs ( FAILURE , BLAME i , i ), which concludes the protocol. Otherwise, member i uses those messages in the T logs but not sent to i to complete her view of Phases 15, and thus she proceeds to examine the remaining part of the protocol. She begins by verifying the inner and outer key pairs revealed by other members. Member i sec and for whom the verication blames each member j who revealed his inner private key Ij
sec , I pub ) failed in Phase 5. Member i sets p = (j, c ) and adds p to of his key pair (Ij j 2 j j BLAME i Then, for every member j who sent an empty inner private key in Phase 5, member i checks the GOk ags and broadcast hashes. Member i blames each member j whose inner private key was empty if there is no GOk = FALSE or non-matching broadcast hash. Member i sets pj = (j, c3 ) and adds pj to BLAMEi . For every member j who revealed his outer private sec is valid and corresponds to the key in Phase 6, member i checks if the outer private key Oj pub outer public key Oj . In addition, for every member j who sent an empty outer private key in Phase 6, member i checks the vector T in j 6 of all messages sent and received by j to sec by showing that in Phase 4 every GO TRUE and all verify that she justies not sending Oj = broadcast hashes were the same. For every member j whose outer private key is invalid or non-matching, or who was not justied in withholding the outer private key, member i sets pj = (j, c4 ) and adds pj to BLAMEi .

Member i continues by replaying the protocol from the perspective of every member j using that members revealed messages and keys. Any member who does not follow the protocol given the messages she receives is added to BLAMEi . More precisely, member i examines the actions of the other members in each phase as follows: Sub-Phase 1: For every member j who sends an invalid public key, member i sets pj = (j, c5 ) and adds pj to BLAMEi . Sub-Phase 2a: For every member j who sends an invalid commitment, member i sets pj = (j, c6 ) and adds pj to BLAMEi . Sub-Phase 2b: For every member j who sends an opening that does not successfully open her commitment or that does not result in a valid ciphertext and identity j , member i sets pj = (j, c7 ) and adds pj to BLAMEi . Sub-Phase 3: In the case that all outer private keys are revealed and all outer private 13

keys correspond to the outer public keys, member i checks that every member j sends a permutation of the decrypted valid ciphertexts and the invalid ciphertexts as contained in Cj 1 . For any member that fails this check, member i sets pj = (j, c8 ) and adds pj to BLAME i . Member i further checks that the submitted ciphertexts do not cause failures by producing duplicate or invalid ciphertexts after decryption. If the submitted ciphertext Cj of member j contains an invalid ciphertext after d decryptions, 1 d N , then member i sets pj = (j, c9 ) and adds pj to BLAMEi . If the submitted ciphertexts Cj and Ck of members j = k decrypt to the same ciphertext after d decryptions, 1 d N , then member i blames members j and k . Member i sets pj = (j, c10 ) and pk = (k, c10 ), and then adds pj and pk to BLAMEi . Sub-Phase 4: In the case that all outer private keys are revealed and all outer private keys correspond to the outer public keys, member i veries that member j properly reported GO j = FALSE based on the messages seen by j in Phases 13. At least one of the following checks must have failed from j s point of view to justify a GOj = FALSE. Sub-Sub-Phase 1: Member i veries the validity of public keys using messages (11 , . . . , N 1 ) sent by all members. Sub-Sub-Phase 2a: Member i veries the correctness of the submitted commitments using (12a , . . . , N 2a ). Sub-Sub-Phase 2b: (This check is done only for member 1) Member i veries that the commitments correspond to the ciphertexts and that the resulting ciphertexts and identities are valid using (12a , . . . , N 2a ) and (12b , . . . , N 2b ). Sub-Sub-Phase 3: Member i veries that there are no duplicate or invalid ciphertexts sent from j using j 3 . Sub-Sub-Phase 4: Member i veries that j s inner ciphertext Cj is included in CN . To determine Cj , member i opens the commitment Xj and decrypts the resulting ciphertext with each of the outer private keys. If all of the above checks were successful and GOj = FALSE, then member i sets pj = (j, c11 ) and adds pj to BLAMEi . In addition, member i checks if the HASH{Bj } that she received in j 4 is correctly calculated from the broadcast messages. If not, member i sets pj = (j, c12 ) and adds pj to BLAMEi . To conclude the protocol, member i creates a log i consisting of the messages sent and received during SETUP - S and ANONYMIZE - S and outputs (FAILURE, BLAMEi , i ).

3.4

Verify-Proof-S Algorithm

VERIFY- PROOF - S (pj , i ) is used to verify a member j s misbehavior. The algorithm takes as input a proof pj and a log i . It should be that pj = (j, c), where j is a members identier and c is the number of a check which failed for j from is point of view. i should be is log of a protocol run, including all messages sent and received by member i in SETUP - S and ANONYMIZE - S. VERIFY- PROOF - S outputs TRUE if pj is a veriable proof of j s misbehavior based on i and FALSE otherwise.

14

3.4.1

Algorithm description.

VERIFY- PROOF - S (pj , i )

Step 1: Proof verication. Verify that pj = (j, c), where c is a valid check number and j is a valid member identier. If so, then proceed to the next phase. Otherwise, output FALSE and stop. Step 2: Log verication. All messages included in log i are veried to ensure that signatures on the included messages are valid. Each message is checked to verify that it contains a correct round nonce given the execution of the SETUP - S algorithm and a correct phase number. All messages with invalid signatures, round nonces or phase numbers are discarded. If the resulting log does not include all messages that were supposed to have been sent and received by i during SETUP - S and ANONYMIZE - S, as described in the descriptions of those algorithms, then output FALSE and stop. Otherwise, verify that the logs of all sent and received messages revealed in Phase 6 by every member j are complete and consistent. That is, for every message j 6 , consider the included vector T . Discard any message in T that is not properly signed or does not have the correct round or phase number, and inspect every T to verify that it includes all messages sent and received in Phases 15. Then, for every message recorded as sent by one member and received by another, check that the contents match, and, for every message that is supposed to be a broadcast, check that the contents of all observed copies match. If any T is incomplete or inconsistent and c = c1 , then output FALSE and stop. Otherwise, if c = c1 or all logs are complete and consistent, then proceed to the next phase. Step 3: Proof verication decision. If all T logs were determined to be complete and consistent, i is augmented to contain all Phase 15 messages sent and received by all members. Otherwise, c = c1 , and a log i of just is perspective will be sufcient. The resulting i is examined as follows to verify that j failed check c: If c = c1 , then we wish to verify that member j sent an incomplete T or equivocated in the protocol. Using message j 6 , which is either of the form {T , nR , 6, j }SIGuj , {0, T , nR , 6, j }SIGuj sec , , T , n , 6, j } SIG , depending on j s execution of the protocol, check if T or {Oj j uj R contains all messages sent and received by j in Phases 15 such that all messages are properly signed and include correct phase and round numbers. If it does not, then output TRUE and stop. Otherwise, using the logs T in the messages k6 of each member k , determine whether there exist copies of a message j that are properly signed with correct round and phase numbers but have different contents. If such evidence of equivocation exists, then output TRUE and stop; else output FALSE and stop. If c = c2 , then we wish to verify that member j sent an invalid inner key pair. sec , n , 5, j } SIG Check if j sent j 5 of the form {Ij uj in Phase 5. If not, then output R
FALSE
pub pub , Oj , nR , 1, j }SIGuj and and stop. If yes, then using messages j 1 = {Ij pub sec is a valid key pair under the chosen encryption scheme. If and Ij j 5 , check if Ij

15

sec is invalid or does not match I pub , then output TRUE and stop, else output FALSE Ij j and stop.

If c = c3 , then we wish to verify that member j improperly sent an empty inner key in Phase 5. Check if j sent j 5 of the form {0, nR , 5, i}SIGui in Phase 5. If not, then output FALSE and stop. If so, then check each message k4 for GOk = FALSE or a non-matching HASH {Bk }. If none are found, then output TRUE and stop; else output FALSE and stop. If c = c4 , then we wish to verify that member j sent an invalid outer key pair or improperly sent an empty outer private key in Phase 6. sec , T , n , 6, j } SIG Check if j sent j 6 of the form {Oj uj in Phase 6. If so, then using R
pub pub pub sec is messages j 1 = {Ij , Oj , nR , 1, j }SIGuj and j 6 , check whether Oj and Oj sec is invalid or does not match O pub , then output TRUE and stop. a valid key pair. If Oj j

Otherwise, check if j sent j 6 of the form {0, T , nR , 6, i}SIGui . If not, then output FALSE and stop. If so, then check if j received a message k4 from some member k that included either a GOk set to FALSE or a non-matching HASH{Bk }. If so, then output TRUE and stop; else output FALSE and stop. If c = c5 , then we wish to verify that member j sent an invalid public key in Phase 1. pub pub pub pub Using j 1 = {Ij , Oj , nR , 1, j }SIGuj , check if Ij and Oj are valid public keys.
pub If Ij or Opub is not a valid key, then output TRUE and stop; else output FALSE and stop.

If c = c6 , then we wish to verify that member j sent an invalid commitment in Phase 2a. Using j 2a = {Xj , nR , 2a, j }SIGuj , check whether Xj is a valid commitment. If it is not, then output TRUE and stop; else output FALSE and stop. If c = c7 , then we wish to verify that member j s commitment is incorrect or results in an incorrect ciphertext or identity. Using j 2a = {Xj , nR , 2a, j }SIGuj and j 2b = {OPEN{Xj }, nR , 2b, j }SIGuj , check whether Xj matches OPEN{Xj } and results in a valid ciphertext. If Xj does not match OPEN {Xj } or does not yield a valid ciphertext and identity j , then output TRUE and stop, else output FALSE and stop. If c = c8 , then we wish to verify that member j did not send a permutation of decrypted ciphertexts in Phase 3. sec , , T , n , 6, k } SIG Check if every member k sent k6 of the form {Ok uk in Phase 6. R k pub pub If not, then output FALSE and stop. If so, then using k1 = {Ik , Ok , nR , 1, k }SIGuk sec and O pub are valid and matching. and k6 , check if each members outer keys Ok k If not, then output FALSE and stop. If so, then, using (j 1)3 = {Cj 1 , nR , 3, j 1}SIGuj 1 , j 3 = {Cj , nR , 3, j }SIGuj , and j 6 , check whether Cj is a permutation of decrypted ciphertexts. That is, using j , permute the elements of the vector Cj 1 sec and verify whether included in (j 1)3 , then decrypt each valid ciphertext using Oj the resulting vector matches the vector in j 3 . If they do not match, then output TRUE and stop, else output FALSE and stop. 16

 If c = c9 , then we wish to verify that member j s decrypted outer ciphertext Cj results in an invalid ciphertext. sec , , T , n , 6, k } SIG Check if every member k sent k6 of the form {Ok uk in Phase 6. R k pub pub If not, then output FALSE and stop. If so, then using k1 = {Ik , Ok , nR , 1, k }SIGuk sec and O pub are valid and matching. If and k6 , check if each members outer keys Ok k not, then output FALSE and stop. If so, then using j 2b = {OPEN{Xj }, nR , 2b, j }SIGuj , produce ciphertext Cj . Then use the outer private keys to iteratively remove the layers of encryption from the ciphertexts in Cj , verifying that a valid ciphertext is produced after every step. If at any point an invalid ciphertext is produced, then output TRUE and stop, else output FALSE and stop. If c = c10 , then we wish to verify that member j s decrypted outer ciphertext Cj results in a duplicate ciphertext. sec , , T , n , 6, k } SIG Check if every member sent k6 of the form {Ok uk in Phase 6. If R k pub pub not, then output FALSE and stop. If so, then using k1 = {Ik , Ok , nR , 1, k }SIGuk sec and O pub are valid and matching. If and k6 , check if each members outer keys Ok k not, then output FALSE and stop. If so, then using the k2b = {OPEN{Xk }, nR , 2b, k }SIGuk of every member k , produce the submitted ciphertexts Ck . Use the outer private keys to iteratively remove the layers of encryption from the valid ciphertexts in each Ck , and if at any point the result for Cj is the same as the result for some other Ck , then output TRUE and stop, else output FALSE and stop. If c = c11 , then we wish to verify that member j sent an incorrect GOj in Phase 4.
sec , , T , n , 6, k } SIG Check if every member sent k6 of the form {Ok uk in Phase 6. If R k pub pub not, then output FALSE and stop. If so, then using k1 = {Ik , Ok , nR , 1, k }SIGuk sec and O pub are valid and matching. If and k6 , check if each members outer keys Ok k not, then output FALSE and stop. If so, then check if GOj = FALSE in j 4 . If not, then output FALSE and stop, else continue.

A-S Phase 1: Using (11 , . . . , N 1 ) check whether j received valid inner and outer public keys. If any key is invalid, then output FALSE and stop. A-S Phase 2a: Using (12a , . . . , N 2a ) verify whether commitments (X1 , . . . , XN ) are valid. If any commitment is invalid, then output FALSE and stop. A-S Phase 2b: If j = 1, then using (12a , . . . , N 2a ) and (12b , . . . , N 2b ) verify whether Xk matches OPEN{Xk } and results in a valid ciphertext and identity k for all k G. If any commitment does not properly open or results in an invalid ciphertext or identity, then output FALSE and stop. A-S Phase 3: Using j 3 , check whether the contained set of ciphertexts includes duplicate or invalid ciphertexts. If there is an invalid or duplicate ciphertext, then output FALSE and stop. A-S Phase 4: Using j 2b , (16 , . . . , N 6 ), and N 3 verify whether j s inner ciphertext Cj was included in CN . To determine Cj , open the commitment Xj included in j 2b and decrypt the resulting ciphertext with each of the outer private keys included in (16 , . . . , N 6 ). If the calculated Cj was not included in CN , then output FALSE and stop, else output TRUE and stop. 17

 If c = c12 , then we wish to verify that j sent an incorrect HASH{B }. Calculate B using messages (11 , . . . , N 1 , 12a , . . . , N 2a , N 3 ) received by j . Then, check whether HASH {B } matches the HASH {B } included in j 4 . If HASH {B } = HASH {B }, then output TRUE, else output FALSE.

4
4.1

GMP-Bulk
Protocol Description

The Group Messaging Protocol-Bulk GMP - BULK is an instantiation of the Group Messaging Protocol and consists of three algorithms: SETUP - B, ANONYMIZE - B, and VERIFY- PROOF - B. Each member i submits a message mi of variable length Li to the ANONYMIZE - B protocol after all members run SETUP - B to agree on common protocol run parameters. If a run of GMP - BULK completes, it can either succeed (Denition 6) or fail (Denition 7). In case of a protocol failure the VERIFY- PROOF - B protocol is used to validate the proofs of members misbehavior generated upon a protocol failure.

4.2

The Setup-B Algorithm

takes each members public signing key vi as input, and outputs a session nonce nR identifying a run of ANONYMIZE - B, a session nonce nR1 identifying a run of ANONYMIZE - S in Phase 3 of ANONYMIZE - B, and a session nonce nR2 identifying a run of ANONYMIZE - S in Phase 7 of ANONYMIZE - B, a set K of members signing keys , and an ordering of members . Since members submit messages of variable lengths, there is no need to agree on a xed message length L.

SETUP - B (vi )

4.3

The Anonymize-B Algorithm

The purpose of ANONYMIZE - B(mi , K, nR , nR1 , nR2 , ) when run by each member in a group on the collective input messages M is to produce anonymized messages M . The algorithm takes a message m and the output of SETUP - B as input. A run of ANONYMIZE - B succeeds for member i if, upon completion of ANONYMIZE - B, her internal ag SUCCESSi is set to TRUE, and fails if SUCCESSi is set to FALSE . If a protocol run succeeds, then member i outputs ( SUCCESS, Mi ), where, as we show in Section 5, Mi consists of N messages including every message submitted by an honest member. If a protocol run fails, then member i produces (FAILURE, BLAMEi , i ). BLAME i includes proofs pj = (j, c) for each member j for whom a check c fails in Phase 7 from member is point of view. The checks in this phase are as follows, listed in the order they are applied by member i during the protocol. As before, each check is associated with a check number that ANONYMIZE - B uses to form a proof of a particular form of misbehavior, and VERIFY- PROOF - B uses to conrm a record of that misbehavior. Check 1 (c1 ): Equivocation in Phase 4 or Phase 5. Check 2 (c2 ): Failure of ANONYMIZE - S in Phase 3 or Phase 7 without justication. Check 3 (c3 ): Empty or incorrect ciphertext(s) sent in Phase 4.

18

 Check 4 (c4 ): Unveriable proof included in the notication in Phase 4. Check 5 (c5 ): Invalid public key sent in Phase 1a. Check 6 (c6 ): Equivocation in Phase 1a. The log i includes all messages sent and received by i during SETUP - B and ANONYMIZE - B as well as the output of ANONYMIZE - S in Phase 3 and Phase 7. For every member j , a complete log j consists of the following messages. SETUP - B: All protocol messages. Phase 1a: Sent: j 1a , received: k1a for all k = j . Phase 1b: Sent: j 1b , received: k1b for all k = j . Phase 2: No messages. Phase 3: Sent: j 3 and all messages sent in shufe, received: k3 for all k = j , and all messages received in shufe.
ANONYMIZE - S
1 output: Mj = d1 , . . . , dN if ANONYMIZE - S succeeds or BLAMEs j , ANONYMIZE - S fails as well as all messages sent and received within the protocol.

s1 j

if

Phase 4: Sent: j 4 , received: k4 for all k = j . Phase 5: Sent: j 5 , received: k5 for all k = j . Phase 6: No messages. Phase 7: Sent: j 7 and all messages sent in shufe; received: k7 for all k = j and all messages received in shufe.
ANONYMIZE - S
2 output: Mj = A1 , . . . , AN if ANONYMIZE - S succeeds or BLAMEs j , ANONYMIZE - S fails as well as all messages sent and received within the protocol.

s2 j

if

Algorithm description. ANONYMIZE - B(mi , K, nR , nR1 , nR2 , ) Phase 1a: Session Key Pair Generation. Each member i chooses an ephemeral encryption key pair (xi , yi ) and broadcasts i1a = {yi , nR , 1a, i}SIGui . Phase 1b: Key Verication. After receiving a public key from every member j , member i noties other members about the set of keys she receives. Member i creates Kie = {11a , . . . , N 1a } and broadcasts i1b = {Kie , nR , 1b, i}SIGui .

19

 Phase 2: Message Descriptor Generation. Member i creates a message descriptor di of a xed length d . Member i sets Li = 0 if she does not wish to send a message in this protocol run and Li to the desired message length if she wishes to send a message. Case 1. Successful key verication. Member i veries each set of public keys received in Phase 1b to ensure that other members received the same set of valid public keys. If every e contains the same set of public keys and every public key y K e is valid, then member Kj j j i chooses a random seed sij for each member j and generates Li pseudorandom bits from sij to obtain ciphertext Cij = PRNG{Li , sij } (j = i), where Li and sij are of xed lengths for all members. Member i now XORs her message mi with each Cij for j = i to obtain ciphertext Cii : Cii = Ci1 . . . Ci(i1) mi Ci(i+1) . . . CiN Member i computes hashes Hij = HASH{Cij }, encrypts each seed sij with j s public key to R form Sij = {sij }yjij , and collects the Hij and Sij into vectors Hi and Si : Hi = (Hi1 , . . . , HiN ) Si = (Si1 , . . . , SiN ) Member i forms a message descriptor di , which has a xed length d di = {Li , Hi , Si }.
e contains a non-matching set of keys or any K e Case 2. Failed key verication. If any Kj j contains an invalid key, then member i creates an empty message descriptor of the desired length d

di = 0d . Case 3. No message to send. If member i chooses not to send a message in this protocol run, she sets Li = 0 and assigns random values to Hi and Si . Member i forms her message descriptor di as follows and pads it to the desired length d di = {Li , Hi , Si }. Phase 3: Message Descriptor Shufe. Each member i runs the ANONYMIZE - S protocol described in Section 3 using (di , K, nR1 , , fi ) as input, where the xed-length descriptor di is the secret message to be shufed. Member i sets fi = TRUE if i created an empty message descriptor, and member i sets fi = FALSE otherwise. 20

If ANONYMIZE - S succeeds, member i has a list Mi of message descriptors in some random s1 1 permutation . If the protocol fails outputting (FAILURE, BLAMEs i , i ), member i saves s1 s1 BLAME i and i . If member i set fi = TRUE, then i prepares a proof p of the dishonest member j s misbehavior to distribute to other members. If member j sent an invalid key, then member i sets p = (j, c5 , j 1a ), where c5 indicates the failed check number and j 1a is the message received by i in Phase 1a. If member j equivocated, then member i sets p = (j, c6 , j 1a , j 1a ), where e j 1a is the message received by i in Phase 1a and j 1a is a message included in some Kk that contains a different key for j than in j 1a . If there is more than one culprit member j , member i chooses one j to blame in some way that does not depend on her message (e.g. randomly). If member i received all valid and matching keys, then member i sets p = 0. Member i broadcasts: i3 = {p , nR , 3, i}SIGui . Phase 4: Data Transmission. Case 1. If ANONYMIZE - S fails, then member j sets GOj = FALSE and shares her blame set s s BLAME j 1 and log j 1 by broadcasting
1 j 4 = {GOj , BLAMEs j ,

s1 j , nR , 4, j } SIG uj .

Case 2. If ANONYMIZE - S succeeds, member j sets GOj = TRUE and decrypts each encrypted seed Sij with private key xj to reveal sij . If sij matches the seed sjj that j chose for herself in her own descriptor, then j sets Cij = Cjj . Otherwise, j sets Cij = PRNG{Li , sij }. Member j then checks HASH{Cij } against Hij . If the hashes match, j sets Cij = Cij . If Sij is not a valid ciphertext, sij is not a valid seed, or HASH{Cij } = Hij , then j sets Cij to an empty ciphertext, Cij = {}. Member j now sends each Cij in -shufed order by broadcasting j 4 = {GOj , C(1)j , . . . , C(N )j , nR , 4, j }SIGuj . Phase 5: Acknowledgment Submission. Each member k noties other members about the outcome of the previous phase. Case 1. If GOj = FALSE for any member j , then member k adds each message j 4 containing GO j = FALSE into a vector Vk . Case 2. If GOj = TRUE for every member j but some ciphertext Cij is empty or satises HASH {Cij } = Hij , then slot (i) has been corrupted. Member k adds each message j 4 containing such a corrupting ciphertext to a vector Vk . Case 3. If GOj = TRUE for every member j and all ciphertexts Cij are non-empty and satisfy HASH {Cij } = Hij , then member k sets Vk = {}. In every case member k broadcasts k5 = {Vk , nR , 5, k }SIGuk . 21

 Phase 6: Message Recovery. If GOi = TRUE for every member i, then for each uncorrupted slot (i), member k recovers member is message by computing mi = Ci1 ... CiN . If Vk = {}, then from member k s point of view none of the slots were corrupted and all messages Mk = (m1 , . . . , mN ) were successfully recovered. If Vk = {}, then some message slot was corrupted or a step of the protocol has failed. Phase 7: Blame. For each member i, if i observed a corrupted slot with a descriptor matching di (there may be more than one) and received all GOj = TRUE, then i generates an accusation naming the member j who sent that incorrect ciphertext. If there is more than one culprit member, member i chooses one to blame in any way that only depends on the output of ANONYMIZE - S and on Vi . Each accusation has a xed length a , indicates the corrupted slot (i), contains the seed sij that i assigned j , and contains the random bits that i used to encrypt the seed: Ai = {j, (i), sij , Rij }. Each member i who does not have an accusation to send submits the empty accusation Ai = 0a . These accusations will be sent anonymously using the ANONYMIZE - S protocol. However, before running it, members look for evidence of equivocation in the previous two rounds. Every member i compares each message j 4 that she received in some Vk in Phase 5 with the message j 4 that she received directly from j in Phase 4. If the contents of these do not match, ignoring any j 4 with an improper signature or incorrect round or phase number, then member sets fi = TRUE to cause ANONYMIZE - S to fail in order to inform other members about the equivocation. If all such messages match, member i sets fi = FALSE. Member i then runs ANONYMIZE - S(Ai , K, nR2 , , fi ). After ANONYMIZE - S completes, there is an opportunity for members who deliberately failed the shufe to distribute evidence of equivocation. For a member i who set fi = TRUE because of conicting messages j 4 and j 4 , i creates a proof of j s equivocation by setting p = (j, c1 , j 4 , j 4 ). If there is more than one culprit member j , member i chooses one j to blame in any way that depends at most on the broadcast messages k4 and k5 sent and received by i. If member i had fi = FALSE, then i sets p = 0. Member i then broadcasts i7 = {p , nR , 7, i}SIGui . Let Ok be the output of the ANONYMIZE - S protocol for member k . After receiving a message i7 from every other member i, member k executes one of the following cases.

22

2 Case 1: Ok = (FAILURE, BLAMEs k ,

s2 k ).

2 Member k sets SUCCESSk = FALSE. Then k considers every blame entry (i, c) BLAMEs k . If c = c11 , then i could not have justiably caused the blame shufe to fail, and so k adds (i, c2 ) to BLAMEk . Otherwise c = c11 , and member k looks in i7 for possible justication of the failure. If i7 does include two versions of the same ciphertext C j (included in properly signed messages that include correct phase and round numbers) for some member j , then k adds (j, c1 ) to BLAMEk . Otherwise, k adds (i, c2 ) to BLAMEk .

s2 ) and Vk = {}. Case 2: Ok = (SUCCESS, Mk

Member k sets SUCCESSk = TRUE.

s2 ) and Vk includes ciphertexts. Case 3: Ok = (SUCCESS, Mk s2 that targets an ink checks the validity of every accusation Ai = (j, (i), sij , Rij ) in Mk R correct ciphertext received by k . To do so, k replays the encryption Sij = {sij }yjij , checks that the encrypted seed Sij included in di matches Sij , and checks that the hash Hij in di matches HASH{PRNG{Li , sij }}, where Li is also obtained from di . If the accusation is valid, s2 then member k adds (j, c3 ) to BLAMEk . If Mk includes no valid accusation targeting an incorrect ciphertext received by k , then k sets SUCCESSk = TRUE. Otherwise, member k sets SUCCESSk = FALSE . s2 Case 4: Ok = (SUCCESS, Mk ) and Vk contains GOi = FALSE for some i.

Member k sets SUCCESSk = FALSE. Then k considers every GOi = FALSE in Vk . Member k checks i4 to see if the contained blame set and log constitute a valid proof of 1 some member j s misbehavior. To do so, member k checks that s i contains nR1 as the 1 round number that is a result of SETUP - B and that VERIFY- PROOF - S(pj , s i ) = TRUE for s1 some pj BLAMEi . If not, then member k blames i by adding (i, c4 ) to BLAMEk . If s1 1 so, then k considers every pj BLAMEs i such that VERIFY- PROOF - S (pj , i ) = TRUE . If pj = (j, c11 ), then member k adds (j, c2 ) to BLAMEk . If pj = (j, c11 ), then member k examines j 3 to see if member j justiably caused a failure of ANONYMIZE - S to expose bad key distribution by some member . If j 3 includes an invalid key y in a properly signed message with correct round and phase numbers, then member k adds ( , c5 ) to BLAMEk . If j 3 includes two different versions of public key y in properly signed messages with correct round and phase numbers, then member adds ( , c6 ) to BLAMEk . Otherwise, k adds (j, c2 ) to BLAMEk . In every case, k concludes as follows. If SUCCESSk = TRUE, k outputs (SUCCESS, Mk ). Otherwise, member k creates a log k of the protocol run that all messages sent and received by k during SETUP - B and ANONYMIZE - B as well as the output of the ANONYMIZE - S protocol in Phases 3 and 7. Member k outputs (FAILURE, BLAMEk , k ).

4.4

Verify-Proof-B Algorithm

The VERIFY- PROOF - B(pj , i ) algorithm is used to verify a members misbehavior. VERIFY- PROOF - B takes as input a proof pj and a log i . A proof pj should consist of a tuple (j, c), where j is a members identier and c indicates the check that failed for member j from member is point of view. A

23

log i should include all messages sent and received during SETUP - B and ANONYMIZE - B by member i as well as the output of ANONYMIZE - S in Phases 3 and 7. The protocol outputs TRUE if pj is a proof of j s misbehavior given is log i and FALSE otherwise. Algorithm description.
VERIFY- PROOF - B (pj , i )

Step 1: Proof verication. Verify that pj includes a valid check number c and member identier j . If the proof pj is valid, then proceed to the next phase. If pj is invalid, then output FALSE and stop. Step 2: Log verication. All messages included in the log i are veried to ensure that signatures on included messages are valid given the included member identier. Each message is checked to verify that it contains a correct round nonce given the execution of the SETUP - B protocol and a correct phase number. All messages with invalid signatures, round nonces, or phase numbers are discarded. If the resulting log does not include all messages that were supposed to have been sent and received by i during SETUP - B and ANONYMIZE - B, as described in the descriptions of those algorithms, as well as the output of ANONYMIZE - S in Phases 3 and 7, then output FALSE . Otherwise, proceed to the next phase. Step 3: Proof verication decision. Log
i

is examined as follows to verify that j failed check c:

If c = c1 , then we wish to verify that member j equivocated in Phase 4 or Phase 5. Check if ANONYMIZE - S failed in Phase 7. If not, then output FALSE and stop. If yes, 2 then use log s i to check each message k7 = {p , nR , 7, k } SIG uk . If no p is of the form (j, c1 , j 4 , j 4 ), where j 4 and j 4 are properly signed messages with correct round and phase numbers and are of the form {TRUE, C1 , . . . , CN , nR , 4, j }SIGuj for some ciphertexts Ci , then output FALSE and stop. Else, if j 4 and j 4 contain different messages for any such p , then output TRUE and stop. Else output FALSE and stop. If c = c2 , then we wish to verify that member j caused a failure of ANONYMIZE - S in Phase 3 or Phase 7 without justication. Check if either ANONYMIZE - S failed in Phase 7 or there was some k4 in Vi with GOk = FALSE. If not, then output FALSE and stop. 2 If ANONYMIZE - S failed in Phase 7, then consider each proof pj BLAMEs i blaming s2 s2 j . Verify that VERIFY- PROOF - S(pj , i ) = TRUE and that i uses nR2 as the round number, and if not discard this proof. Otherwise, if pj = (j, c11 ) then output TRUE and stop. If instead pj = (j, c11 ), then we must check whether j caused a protocol failure in order to distribute a proof of equivocation of some other member k . Using message j 7 = {p , nR , 7, j }SIGuj , check if p is of the form (k, c1 , k4 , k4 ) with k = j and where k4 and k4 have different contents and are properly signed with correct round and phase numbers. If not, then output TRUE and stop. If no proof results in an output of TRUE, then output FALSE and stop. 24

Otherwise, the blame shufe succeeded for i, but some member indicated a failure of the descriptor shufe. For every k that sent a k4 of the form s1 s1 1 {FALSE, BLAMEs k , k , nR , 4, k } SIG uk , consider every proof pj BLAME k blaming s1 1 j . Verify that VERIFY- PROOF - S(pj , s i ) = TRUE , and that the round number in k is nR1 , and if not discard this proof. Otherwise, if pj = (j, c11 ), then output TRUE and stop. If instead pj = (j, c11 ), then we must check whether j caused a protocol failure in order to distribute a proof of misbehavior of some other member k . Using message j 3 = {p , nR , 3, j }SIGuj , check if (i) p is of the form (k, c5 , k1a ) with k = j and where k1a contains an invalid public key yk and is properly signed with correct round and phase numbers, or (ii) p is of the form (k, c6 , k1a , k1a ) with k = j and where the keys in k1a and k1a are unequal and both messages are properly signed with correct round and phase numbers. If not, then output TRUE and stop. If no proof pj results in an output of TRUE, then output FALSE and stop. If c = c3 , then we wish to verify that member j sent an empty or incorrect ciphertext Ckj in Phase 4. Check if (i) j sent j 4 of the form {TRUE, C(1)j , . . . , C(N )j , nR , 4, j }SIGuj in Phase 4, and (ii) ANONYMIZE - S in Phase 7 succeeded for member i with an accusation Ak = {j, (k ), skj , Rkj } naming j as a faulty member in its output. If not, then output FALSE and stop. Otherwise, we need to check that the accusation against j is valid. Doing so requires comparing the accusation to the descriptors received by j . We need to be sure that j received the descriptors claimed by i. To do so, rst recompute the hash of broadcast messages in Phases 13 of the descriptor shufe and compare it to the hash that i sent in Phase 4 of that shufe. If the hashes are not the same, output FALSE and stop. Otherwise, further compare them to the hash sent by j in Phase 4 of the descriptor shufe. If they do not match, output FALSE and stop. Otherwise, examine the inner private keys received by i in Phase 5 of the descriptor sec is invalid or does not match its public key I pub , output FALSE shufe. If any key Ik k and stop. Otherwise, use these keys to decrypt the inner ciphertexts contained in the nal broadcast of Phase 3. Let {Lk , Hk , Sk } be the resulting descriptor in the slot (k ) pointed to by the accusation. Recall that C(k)j is the ciphertext for this slot that j sent to i in message j 4 . Check if (i) HASH{C(k)j } does not match the hash in the j th element of Hk , (ii) the encryption of the accusation seed skj under the key sent in j 1a using the random bits Rkj of the accusation is equal to the j th encrypted seed in Sk , and (iii) HASH { PRNG {Lk , skj }} is equal to the hash in the j th element of Hk . If not, output FALSE and stop. If so, output TRUE and stop. If c = c4 , then we wish to verify that member j unjustiably reported in Phase 4 a failure of ANONYMIZE - S. s1 1 Check if j sent j 4 of the form {FALSE, BLAMEs j , j , nR , 4, j } SIG uj . If not, then output FALSE and stop. If so, examine j 3 to see if j justiably caused failure of the descriptor shufe. If (i) it contains an invalid key yk in a properly signed message with correct round and phase numbers, or (ii) it contains two different versions of the same 25

key yk in properly signed messages with correct round and phase numbers, then output FALSE and stop. 1 Otherwise, check if (i) s j does not contain the round number nR1 that is the output of s s SETUP - B in i , or (ii) pi BLAME j 1 VERIFY- PROOF - S (pi , j 1 ) = FALSE . If so, then output TRUE and stop, else output FALSE and stop. If c = c5 , then we wish to verify that member j sent an invalid key in Phase 1a. Check if k3 = {p , nR , 3, k }SIGuk sent by any member k contains p of the form (j, c5 , j 1a ), where j 1a contains an invalid public key yj and is properly signed with correct round and phase numbers. If yes, then output TRUE and stop, else output FALSE and stop. If c = c6 , then we wish to verify that member j equivocated in Phase 1a and sent two different public keys. Check if any k3 = {p , nR , 3, k }SIGuk contains p of the form (j, c6 , j 1a , j 1a ) such that j 1a and j 1a have different message contents and are properly signed with correct round and phase numbers. If yes, then output TRUE and stop, else output FALSE and stop.

Security properties and proofs

In this section, we formally dene and analyze integrity, accountability, and anonymity and prove that DISSENT satises these properties. These denitions are precise versions of the notions used by Corrigan-Gibbs and Ford (2010).

5.1

Notation

Let G be the set of all members participating in the protocol, H be the set of honest members and D the set of dishonest members. For security properties expressed as a game between an adversary A and challenger C , we denote the output of the adversary as AC . We use (Gi ) to denote P r Gi (0) = 1 P r Gi (1) = 1 , which is the advantage of game Gi . We also use b to indicate the complement of bit b: b = 1 b.

5.2

Preliminary Denitions

We use the following technical denitions, some making precise notions discussed earlier and some introduced here, to express the security denitions, theorems, and proofs. Denition 5. A function is negligible in an input if it is non-negative and goes to zero with that input asymptotically faster than any inverse polynomial. The input is assumed to be a security parameter unless otherwise stated. Denition 6. A protocol run of a GMP protocol succeeds for member i if the ANONYMIZE algorithm terminates with output (SUCCESS, Mi ). Denition 7. A protocol run of a GMP protocol fails for member i if the ANONYMIZE algorithm terminates with output (FAILURE, BLAMEi , i ). 26

Denition 8. A member is honest if she faithfully carries out the protocol according to its specication, does not cooperate with the adversary, and is not under his control. Denition 9. A member is dishonest if she is not honest. Denition 10. A group member i blames member j if pj BLAMEi upon a protocol failure resulting in (FAILURE, BLAMEi , i ) . Denition 11. A veriable proof of j s misbehavior given TRUE .
i

is a pj such that VERIFY- PROOF(pj , i ) =

Denition 12. A group member i exposes member j if i holds a veriable proof of j s misbehavior given a log i of a protocol run in which member j participated using his long-term signing key uj .

5.3

Integrity

Denition 13. A Group Messaging Protocol GMP offers integrity if after a complete run of the protocol involving N group members 1. each honest member i terminates with either (SUCCESS, Mi ) or (FAILURE, BLAMEi , i ), and 2. for every honest member who terminates with (SUCCESS, Mi ), except with negligible probability, Mi contains exactly N of the same messages, includes each honest members message, and has the messages in the same order. In Section 5.3.1 we provide a proof that the GMP - SHUFFLE protocol maintains integrity. Section 5.3.2 contains a proof for the GMP - BULK protocol. The proofs are structured as follows. First, we show that a protocol run can either succeed or fail for each honest i. Then, we show that each honest i who succeeds obtains a same set Mi of exactly N messages that includes every honest members message. 5.3.1 The GMP-Shufe Protocol

We will show that the GMP - SHUFFLE protocol terminates either with success or failure, depending on the outcome of the verication in Phase 4 and the key release and decryption in Phase 5. If both phases complete successfully, then member i recovers secret messages submitted to the protocol and the protocol completes outputting (SUCCESS, Mi ). If any step of Phase 4 or 5 fails, then member i outputs (FAILURE, BLAMEi , i ) after executing the blame procedures in Phase 6. Lemma 1. After a complete run of GMP - SHUFFLE, each honest group member i terminates with either (SUCCESS, Mi ) or (FAILURE, BLAMEi , i ). Proof. After running ANONYMIZE - S, each honest member is internal SUCCESSi ag is set to either TRUE or FALSE indicating the outcome of the protocol from is point of view. Member i has SUCCESSi = TRUE only if in Phase 4 she has a go message and receives a complete set of go messages and matching broadcast hashes from every member, and in Phase 5 she receives a complete set of non-empty and matching inner private keys from every member. Otherwise, member is ag is set to FALSE. For every honest member i, ANONYMIZE - S outputs (SUCCESS, Mi ) if SUCCESSi = TRUE and (FAILURE, BLAMEi , i ) if SUCCESSi = FALSE. Hence, each protocol run of GMP - SHUFFLE terminates with either (SUCCESS, Mi ) or (FAILURE, BLAMEi , i ) for every honest group member i. 27

Lemma 2. For every honest member i who terminates with (SUCCESS, Mi ) after running GMP - SHUFFLE, except with negligible probability, Mi includes the same N messages, includes each honest members message, and has the messages in the same order. Proof. Let i be an honest member for whom the protocol run succeeds. According to the protocol specication, i terminated with (SUCCESS, Mi ) because (i) in Phase 4 her own GOi = TRUE, (ii) in Phase 4 she receives messages such that GOj = TRUE and HASH{Bj } = HASH{Bi } for every sec matched member j G, and (iii) in Phase 5 she received non-empty inner private keys such that Ij
pub Ij for every j G. Bi contains all broadcast messages member i sent and received in Phases 13, and thus, by (i) and (ii) and the assumption that the hash function is second-preimage resistant, member i is in possession of the same CN and inner public keys as every other honest member j , except with negligible probability. Furthermore, (iii) applies to every honest j for which the protocol is successful, and so every such j has inner private keys that match the common inner public keys. Thus, member i can decrypt each ciphertext included in CN using her set of inner private keys to obtain N messages, and the resulting list contains the same messages in the same order as each honest user j that successfully terminates. Moreover, because member j sends i GOj = TRUE, the inner ciphertext Cj must be in their common CN . Therefore, after decryption, i obtains the message mj of each honest member j .

Theorem 1. The GMP - SHUFFLE protocol offers integrity. Proof. Following Lemma 1 we know that each honest group member i terminates with either (SUCCESS, Mi ) or (FAILURE, BLAMEi , i ) after a complete protocol run of GMP - SHUFFLE. Following Lemma 2 we know that, for every honest member who terminates with (SUCCESS, Mi ), except with negligible probability, Mi contains the same N messages in the same order, including each honest members message. Thus the GMP - SHUFFLE protocol offers integrity. 5.3.2 The GMP-Bulk Protocol

We will show that the GMP - BULK protocol terminates either with success or failure, depending on the outcome of the shufe in Phase 3 and Phase 7. If ANONYMIZE - S succeeds in Phase 3, all ciphertext Cij are correct, and ANONYMIZE - S succeeds in Phase 7, or if there is no valid accusation for each Cij that is incorrect after ANONYMIZE - S in Phase 7 succeeds, then the protocol completes successfully outputting (SUCCESS, Mi ). Otherwise, the protocol fails, member i executes the blame procedures and outputs (FAILURE, BLAMEi , i ). Lemma 3. After a complete run of GMP - BULK, each honest group member i terminates with either (SUCCESS, Mi ) or (FAILURE, BLAMEi , i ). Proof. After running ANONYMIZE - B, each honest member is internal SUCCESSi ag is set to either TRUE or FALSE indicating the outcome of the protocol from is point of view. Member i has SUCCESSi = TRUE only if in Phase 4 she receives a correct and complete set of ciphertexts Cjk for every k G and the ANONYMIZE - S protocol succeeds in Phase 7, or there is no valid accusation in Phase 7 for every incorrect ciphertext Cjk received in Phase 4 following a successful run of the ANONYMIZE - S protocol in Phase 7. Otherwise, member is ag is set to FALSE .

28

For every honest member i, ANONYMIZE - B outputs (SUCCESS, Mi ) if SUCCESSi = TRUE and (FAILURE, BLAMEi , i ) if SUCCESSi = FALSE. Hence, each protocol run of GMP - BULK terminates with either (SUCCESS, Mi ) or (FAILURE, BLAMEi , i ). Lemma 4. For every honest member i who terminates with (SUCCESS, Mi ) after running GMP - BULK, except with negligible probability, Mi includes the same N messages, Mi includes each honest members message, and the messages in Mi are in the same order. Proof. Assume that there exists an honest member i for whom GMP - BULK terminates successfully. Then, according to the protocol specication, it must be that (i) each member k G sends i GO k = TRUE in Phase 4, (ii) the run of the ANONYMIZE - S protocol completes successfully for i in Phase 7, and (iii) either HASH{Cjk } = Hjk for all ciphertexts received by i in Phase 4 or no valid accusation is received in Phase 7 for any ciphertext such that HASH{Cjk } = Hjk . The descriptor and blame shufes are executed by calling ANONYMIZE - S using the parameters produced by SETUP - B. These parameters are produced in the same way that SETUP - S does as part of GMP - SHUFFLE , and therefore Theorem 1 applies to the descriptor and blame shufes. Thus every honest member for whom the descriptor shufe is successful, except with negligible probability, obtains the same N message descriptors in the same order, including a message descriptor for each honest member. By (i), the descriptor shufe is successful for every honest member, and thus they all obtain these same descriptors. Similarly, every honest member for whom the blame shufe is successful obtains the same N accusations in the same order, including each accusation from an honest member. By (ii), the blame shufe is successful for every honest member for whom the bulk protocol is successful, and thus they all obtain these same accusations. Therefore, if honest members receive different ciphertexts in Phase 4, the second-preimage resistance of the hash implies that at least one of the ciphertexts must not match the corresponding hash. The recipient of that ciphertext would report the corruption in Phase 5, and the equivocation would prevent the accusation shufe from succeeding for any honest member, contradicting (ii). Thus all honest members that successfully terminate must have the same sequence of N descriptors and the same ciphertexts. This implies that these members obtain the same N messages in the same order from the bulk protocol. In addition, as shown, the descriptors obtained by every honest member include the descriptors of all of the honest members in the same slots. Because each honest member receives the same ciphertexts, any corruption of an honest members slot would be seen by that member. That member would then produce an accusation which, as we have described, would be obtained from the blame shufe by all honest members who terminate successfully. This would contradict condition (iii) of successful termination. Therefore, no slot containing an honest members descriptor can be corrupted at an honest user. This implies that the messages obtained by an honest member from successful termination of the bulk protocol must contain the messages of all honest members. Theorem 2. The GMP - BULK protocol offers integrity. Proof. Following Lemma 3 we know that each honest group member i terminates with either (SUCCESS, Mi ) or (FAILURE, BLAMEi , i ) after a complete protocol run of GMP - BULK. Following Lemma 4 we know that, for every honest member who terminates with (SUCCESS, Mi ), except with negligible probability, Mi contains the same N messages in the same order, including each honest members message. Thus the GMP - BULK protocol offers integrity.

29

5.4

Accountability

Denition 14. A Group Messaging Protocol GMP offers accountability if, after a complete protocol run, 1. the BLAMEi set of any honest member i for whom the protocol failed is non-empty, 2. no honest member is exposed, except with negligible probability, and 3. an honest member exposes every member she blames. These properties must hold even when the protocol run is preceded by other protocol runs. In Section 5.4.1 we prove that the GMP - SHUFFLE protocol offers accountability. Section 5.4.2 contains a corresponding proof for the GMP - BULK protocol. The checks of each protocol form the backbone of each proof. A main argument of the proofs is that the protocol fails when one of the checks fails, each such failure for i results in an addition to BLAME i , and because VERIFY- PROOF uses the same checks each such addition exposes the blamed member. In addition, the round nonces, phase numbers, and member identities included in each signed message prevent an adversary from creating a log that contains anything but the actual messages sent by an honest member in a given round and phase. The protocols ensure that these sent messages include the messages received by the honest member where necessary. Thus an honest member is always seen in the log as behaving correctly and is not exposed. 5.4.1 The GMP-Shufe Protocol

Lemma 5. If, after a complete run of GMP - SHUFFLE, SUCCESSi = FALSE for an honest member i, then BLAMEi is non-empty, and every proof it contains is veriable given log i . Proof. We will show that, whenever SUCCESSi = FALSE, i adds a proof pj to BLAMEi , and every proof it adds is veriable. In fact, it sufces to show that, whenever SUCCESSi = FALSE, i adds a proof pj to BLAMEi , because it is straightforward to see that any such pj is veriable. In VERIFY- PROOF - S , proof verication of pj (Step 1) always succeeds, because pj always includes valid check number and member identier; log verication of i (Step 2) always succeeds because the protocol completes by assumption, and i adds all her messages to log i ; and the proof verication decision (Step 3) always succeeds because it outputs TRUE given pj for exactly the same logs in which i adds pj to BLAMEi . Therefore, we can simply show that, whenever the protocol fails for i, a proof is added to BLAME i . In ANONYMIZE - S , SUCCESSi = FALSE upon protocol completion only in the following three cases: (1) in Phase 4, GOi = FALSE or a non-matching broadcast hash is received, (2) in Phase 4, GOk = FALSE for some k = i, (3) in Phase 5, an empty, invalid, or non-matching inner private key is received. In any of these cases, if an inconsistent or incomplete T log is received in some j 6 , then (j, c1 ) is added to BLAMEi . Therefore we assume from this point on that all T logs are complete and consistent and proceed to examine these cases separately. Suppose case (1) occurs. We consider the conditions in each of the phases up to Phase 4 that can cause GOi = FALSE, and we identify in each case a proof pj that must be added to BLAMEi : 30

 In Phase 1, an invalid public key must be received from some j . Then pj = (j, c5 ). In Phase 2a, an invalid commitment must be received from some j . Then pj = (j, c6 ). In Phase 2b, a commitment opening must fail or result in an invalid ciphertext or identity. Then pj = (j, c7 ). In Phase 3, Ci must have an invalid or duplicate ciphertext. If some member j releases an empty, invalid, or non-matching outer private key in Phase 6, then pj = (j, c4 ). Otherwise, i replays the permutations and decryptions of Phase 3. During the replay, if some member j did not correctly permute and decrypt her inputs, then pj = (j, c8 ). Otherwise, i must observe a member j whose commitment value decrypted either to an invalid ciphertext, in which case pj = (j, c9 ), or to a duplicate ciphertext, in which case pj = (j, c10 ). In Phase 4, it could be that the inner ciphertext Cj is not in CN . In this case, as in the previous one, if some member j releases an empty, invalid, or non-matching outer private key in Phase 6, then pj = (j, c4 ). Otherwise, i replays Phase 3 and during the replay must observe some member j who did not correctly permute and decrypt her inputs. Then pj = (j, c8 ). It could also be that a non-matching broadcast hash is received from j , in which case j must have sent an incorrect hash, and pj = (j, c12 ). Next suppose case (2) occurs. If some member j releases an empty, invalid, or non-matching outer private key in Phase 6, then pj = (j, c4 ). Otherwise, i replays the protocol. If any member j sent an invalid public key or an invalid commitment, then pj = (j, c5 ) or pj = (j, c6 ), respectively. If k = 1 and commitment opening failed or resulted in an invalid ciphertext for some j , then pj = (j, c7 ). If there were invalid or duplicate ciphertexts in Ck , then i must observe a member j who either did not correctly permute and decrypt her inputs, in which case pj = (j, c8 ), or committed to a value that decrypted to an invalid or duplicate ciphertext, in which case pj = (j, c9 ) or pj = (j, c10 ), respectively. If the inner ciphertext of member k is not included in CN , then there must be some member j who did not correctly permute and decrypt her inputs, and pj = (j, c8 ). Otherwise, k incorrectly set GOk , and pj = (j, c11 ) with j = k . Finally, suppose case (3) occurs. An empty inner private key can only be justied by a GOk = FALSE for some k or a non-matching broadcast hash from some j . In either case we have already identied the pj added by i. If an empty key from some j is not justied, then pj = (j, c3 ). If an invalid or non-matching inner private key is received from some j , then pj = (j, c2 ). Thus we have shown that honest member i adds some proof pj to BLAMEi whenever SUCCESSi = FALSE , and furthermore that any such pj is a veriable proof given log i . Lemma 6. An honest member j is not exposed after a run of GMP - SHUFFLE, except with negligible probability. Proof. Suppose that the adversary exposes an honest member j . That is, suppose that he produces a proof pj and log i such that VERIFY- PROOF - S(pj , i ) = TRUE. To pass the initial proof verication, it must be the case that pj = (c, j ). To pass the log verication, it must be the case either that c = c1 or that all the T logs in the j 6 of i are complete and consistent. Each message in ANONYMIZE - S identies the sender and is signed by that sender. By the EUFCMA property of the signature scheme, the adversary is not able to forge a signature under any honest members key, except with negligible probability, and therefore any message signed by j in i must have been sent by j . Furthermore, each message identies the round and phase for which that message was sent. An honest member sends exactly one message during each phase of a given

31

round. Therefore, every message in i from j must have actually been sent during that round and phase by j . Given these facts, we can go through each possible check and show that for each one the needed log evidence cannot exist. Whenever we refer to message k , we are referring to the message that i indicates was sent by member k in phase . Suppose that c = c1 . Then for the proof to verify, i must contain either different copies of the same message for a given phase or an incomplete log T in a j 6 . An honest j would never send such messages. Thus c = c1 . In each of the remaining cases, the log vectors T in the k6 were veried during log verication to be complete and consistent, and i is augmented with all messages from all members during Phases 15. Thus we can assume that each message k sent or received by j during these phases appears with the same contents in i . pub Suppose that c = c2 . Then it must be the case that j 1 and j 5 have non-matching Ij and sec Ij . j would never send such a pair, however. Thus c = c2 . Suppose that c = c3 . Then j must have sent an empty inner key, which implies that j observed either a GOk = FALSE or a non-matching broadcast hash HASH{Bk }. Therefore the k4 do not contain the evidence needed for VERIFY- PROOF - S to validate this check. Thus c = c3 . pub sec that do not match, or j Suppose that c = c4 . Then either j sent outer keys Oj and Oj incorrectly sent an empty outer private key. j only ever sends matching outer keys, and so the former case cannot apply. If j sent an empty outer private key, it must have been the case that, for all k4 , the contained GOk = TRUE and HASH{Bk } = HASH{Bj }. Therefore the k4 do not contain the evidence needed for VERIFY- PROOF - S to validate this check. Thus c = c4 . Suppose that c = c5 . Then j must have sent an invalid key in j 1 . An honest j would never send an invalid key, though, and thus c = c5 . Suppose that c = c6 . The j must have sent an invalid commitment in j 2a . An honest j would never send an invalid commitment, though, and thus c = c6 . Suppose that c = c7 . Then either j s commitment opening in j 2b does not match the commitment in j 2a , or the value from the opening is not a valid ciphertext or identity. j always sends a matching commitment and opening, though, and j s committed value is always a valid ciphertext and her identity. Thus c = c7 . Suppose that c = c8 . Then the messages in j 3 must not be a permutation and decryption of sec released by j . However, j does correctly permute and the messages in (j 1)3 using the key Oj decrypt during Phase 3 and only ever releases the correct key used in that decryption. Thus c = c8 . Suppose that c = c9 . Then j must send a value Cj into the Phase 3 shufe that results in an invalid ciphertext after some sequence of decryptions by the outer private keys released by all members. Those private keys are checked to match the outer public keys received by j , however, and j correctly forms Cj by encrypting mj with the inner and outer public keys in sequence. Therefore it can never be that Cj results in an invalid ciphertext after decryption by some of the outer private keys, and c = c9 . Suppose that c = c10 . Then it must be that for some ciphertext Ck , k = j , both Ck and Cj yield the same result after some number of sequential decryptions by the outer private keys. As we established above, the messages in Phases 15 of i sent and received by j are those actually sent and received by j during the protocol run. Thus, if the adversary were able to produce a commitment to a value that is related to Cj in that some sequential decryptions yield the same result, then we could construct an adversary that violates the non-malleability of the commitment scheme (Dolev, 32

Dwork, and Naor 2000). Thus c = c10 . Suppose that c = c11 . Then it must be that j sent GOj = FALSE without justication. The justication needed would be receiving an invalid public key in Phase 1, receiving an invalid commitment in Phase 2a, receiving an invalid commitment opening or opening an invalid ciphertext or identity in Phase 2b, producing invalid or duplicate ciphertexts during Phase 3, or not receiving her own inner ciphertext Cj at the end of Phase 3. However, each of these conditions is true in i if it was true during the run from j s perspective. In particular, the inner ciphertext as determined by VERIFY- PROOF - S must be the inner ciphertext of j because the decryption keys are veried to match the public keys seen by j . j would only send GOj = FALSE if one of these conditions held, and thus c = c11 . Suppose that c = c12 . Then it must be that the broadcast hash that j sent in Phase 4 does not match the hash of all broadcast messages up to that point. j sends the correct hash, however, and thus c = c12 . Therefore, there is no value of c for which VERIFY- PROOF - S could output TRUE given i , except with negligible probability, and the adversary cannot expose an honest member. Theorem 3. The GMP - SHUFFLE protocol offers accountability. Proof. Following Lemma 5 we know that after a failed run of GMP - SHUFFLE for an honest member i, BLAMEi is non-empty. Additionally, every proof included in BLAMEi is veriable given a log i , hence, an honest member exposes every member she blames. Following Lemma 6 we know that an honest member j is not exposed after a run of GMP - SHUFFLE, except with negligible probability. Thus the GMP - SHUFFLE protocol offers accountability. 5.4.2 The GMP-Bulk Protocol

Lemma 7. If, after a complete run of GMP - BULK, SUCCESSi = FALSE for an honest member i, then BLAMEi is non-empty, and every proof it contains is veriable given log i . Proof. We will show that, whenever SUCCESSi = FALSE, i adds a proof pj to BLAMEi , and every proof it adds is veriable. In fact, it will sufce to show that, whenever SUCCESSi = FALSE, i adds a proof pj to BLAMEi , because we rst prove that any such pj is veriable. In VERIFY- PROOF - B, proof verication of pj (Step 1) always succeeds, because honest i always includes a valid check number and member identier in pj . Log verication of i (Step 2) always succeeds because the protocol completes by assumption, and i adds all her messages to log i . Finally, given complete log i , the properties of that log that must hold for the proof verication decision (Step 3) to output TRUE on proof pj are almost exactly the same properties that must hold for honest i to add pj to BLAMEi . In fact, VERIFY- PROOF - B only veries as true more proofs for a given log than would be created by i, as we show by considering each check separately:
2 pj = (j, c1 ): VERIFY- PROOF - B omits checking for (j, c11 ) BLAMEs i and otherwise makes the same log checks to verify pj as ANONYMIZE - B does during blame to produce pj .

pj = (j, c2 ): VERIFY- PROOF - B and ANONYMIZE - B use the same log checks for this pj .

33

 pj = (j, c3 ): VERIFY- PROOF - B adds a check to make sure that the descriptors claimed by i are those received by j , but this check is always satised by the log of an honest i. All other checks are the same for this pj . pj = (j, c4 ): VERIFY- PROOF - B omits checking that the blame shufe succeeds and that Vi contains some GOk = FALSE. Otherwise, it is the same as ANONYMIZE - B for this pj . pj = (j, c5 ): VERIFY- PROOF - B omits checking that the blame shufe succeeds, that Vi contains some GOk = FALSE, and that the member with evidence of a bad key gets blamed rst. Otherwise, it the same as ANONYMIZE - B for this pj . pj = (j, c6 ): VERIFY- PROOF - B omits checking that the blame shufe succeeds, that Vi contains some GOk = FALSE, and that the member with equivocation evidence gets blamed rst. Otherwise, it the same as ANONYMIZE - B for this pj . Thus, VERIFY- PROOF - B(pj , i ) = TRUE for every pj BLAMEi . Therefore, we can simply show that, whenever the protocol fails for i, a proof is added to BLAME i . In ANONYMIZE - B , SUCCESSi = FALSE upon protocol completion only in the following cases: 1. The blame shufe fails. 2. The blame shufe succeeds and outputs a valid accusation. 3. Some j 4 contains GOj = FALSE. We consider each case and identify a proof p that is added to BLAMEi in each one. s2 2 In case (1), by Lemma 5, there exists a veriable proof (j, c) BLAMEs i given i . If c = c11 and evidence of ciphertext equivocation by k exists in j 7 , then p = (k, c1 ). Otherwise, p = (j, c2 ). In case (2), p = (j, c3 ). In case (3), p = (j, c4 ) if j 4 contains no veriable proofs, p = (k, c2 ) if j 4 has a veriable proof of k s misbehavior and k provides no justication in k3 , and p = ( , c5 ) or p = ( , c6 ) if j 4 has a veriable proof of k s misbehavior but k provide evidence against in k 3 . Thus, if GMP - BULK fails for i, BLAMEi contains a veriable proof given i and only contains such proofs. Lemma 8. An honest member j is not exposed after a run of GMP - BULK, except with negligible probability. Proof. Suppose that the adversary exposes an honest member j . To pass the proof verication of VERIFY- PROOF - B, it must be the case that he produces a proof pj = (c, j ). To pass the log verication, it must be the case the log i is complete. Each message in ANONYMIZE - B identies the sender and is signed by that sender. By the assumption the signature scheme is EUF-CMA, the adversary is not able to forge a signature under any honest members key, except with negligible probability, and therefore any message signed by j in i must have been sent by j . Furthermore, each message identies the round and phase for which that message was sent. An honest member sends at most one message during each phase of a given round. Therefore, every message in i from j must have actually been sent during that round and phase by j . 34

Given these facts, we can go through each possible check and show that for each one the needed log evidence cannot exist. Whenever we refer to message k , we are referring to the message that i indicates was sent by member k in phase . Suppose that c = c1 . Then for the proof to verify, i must contain different copies of the same message for Phase 4. An honest j always sends the same message to every member in any given phase and therefore such messages do not exist. Thus c = c1 . Suppose that c = c2 . Then ANONYMIZE - S must have failed in Phase 3 or Phase 7. If ANONYMIZE - S failed in Phase 3, then for the proof to verify member j must have not distributed a proof of another members bad key or key equivocation, and there must be a veriable 1 pj BLAMEs k for some member k . However, if j intentionally causes a failure, then she always distributes an appropriate proof in j 3 , and if she does not, then by Lemma 6 a veriable proof blaming j cannot be produced, except with negligible probability. If ANONYMIZE - S failed for i in Phase 7, then for the proof to verify member j must have 2 not distributed a proof anothers member equivocation in Phase 4, and pj BLAMEs i must be veriable. However, if j causes a failure of the blame shufe, then she always distributes a proof of equivocation in j 7 , and if she does not, then by Lemma 6 a veriable proof blaming j cannot be produced, except with negligible probability. Thus c = c2 . Suppose that c = c3 . Then j must have sent an incorrect or empty ciphertext in Phase 4. Observe that the hash of broadcast messages in i is veried to be equal to the broadcast hash sent by j , and thus, by the second-preimage resistance property, it must be that the inner public keys and inner ciphertexts in i are the same as those seen by j , except with negligible probability. The inner private keys are veried to match their public keys, and thus the descriptors computed by VERIFY- PROOF - B must match those seen by j . An honest j would only send a non-empty ciphertext Ckj if the pseudorandom bits from its decrypted seed yield the correct hash value. Given that the computed descriptors match those seen by j and that only one seed can encrypt to a given ciphertext, the accusation must not satisfy the validity checks in VERIFY- PROOF - B. If j sends an empty ciphertext Ckj , then it must be that due to a problem with descriptor dk that she observed. That is, it must be that Skj is not a valid ciphertext, skj is not a valid seed, or HASH{Ckj } = Hkj . If any of the above descriptor problems exist, then because the descriptors used in VERIFY- PROOF - B must match the ones seen by j , the accusation must not satisfy the validity checks in VERIFY- PROOF - B. Thus c = c3 . Suppose that c = c4 . Then it must be that j sent GOj = FALSE in j 4 without justication. The justication needed either would be evidence in j 3 of a bad key or key equivocation in Phase 1a or would be a veriable proof in j 4 of misbehavior during ANONYMIZE - S in Phase 3. If j sent GOj = FALSE in j 4 , it must have been that the descriptor shufe failed for j . If j intentionally caused this shufe to fail, then j observed bad or non-matching keys and distributed 1 the evidence in j 3 . If j did not intentionally cause shufe failure, then by Lemma 5, BLAMEs j s1 contains a veriable proof given j . Thus c = c4 . Suppose that c = c5 . Then j must have sent an invalid key in j 1a . An honest j would never send an invalid key, though, and thus c = c5 . Suppose that c = c6 . Then for the proof to verify, i must contain different copies of the same message for Phase 1a. However, an honest j always sends the same message to every member in any given phase. Thus c = c6 . Therefore, there is no value of c for which VERIFY- PROOF - B could output TRUE given i , except 35

with negligible probability, and the adversary cannot expose an honest member. Theorem 4. The GMP - BULK protocol offers accountability. Proof. Following Lemma 7 we know that after a failed run of GMP - BULK for an honest member i, BLAME i is non-empty. Additionally, every proof included in BLAME i is veriable given a log i , hence, an honest member exposes every member she blames. Following Lemma 8 we know that an honest member j is never exposed after a run of GMP - BULK, except with negligible probability. Thus the GMP - BULK protocol offers accountability.

5.5

Anonymity

Denition 15. A protocol maintains anonymity with k colluding members if, for all probabilistic polynomial-time adversaries, the advantage in the anonymity game with any k dishonest members is negligible. Note that the denition will only make sense for 0 k N 2. We use the anonymity game described by Brickell and Shmatikov (2006a). The anonymity game is played between an adversary A and a challenger C (b), where b denotes a hidden challenge bit. The adversary plays the roles of k dishonest members, while the challenger plays the role of the N k honest members. The anonymity game works as follows: 1. As many times as A requests, C (b) takes message inputs for the honest members from A and uses them to execute the protocol with A, giving him a copy of every message sent.
c 2. A chooses two honest participants and and two message inputs mc 0 and m1 . He also chooses message inputs mh for each honest member h and sends his choices to C (b). c. 3. C (b) assigns m = mc b and m = m b

4. A and C (b) execute the protocol, during which C (b) gives A a copy of every message sent. 5. As many times as A requests, C (b) takes message inputs for the honest members and uses them to execute the protocol with A, giving him a copy of every message sent. 6. The adversary outputs a guess b {0, 1} for the value of b. The adversarys advantage in the anonymity game is equal to P r AC (0) = 1 P r AC (1) = 1 , where the probability is taken over the randomness of both the adversary and of the challenger. 5.5.1 The GMP-Shufe Protocol

We consider the anonymity game running GMP - SHUFFLE and show that the adversarys advantage in winning this game is negligible. We begin by using any adversary A to construct Game 0, in which a new challenger C 0 randomly guesses whether a given honest user will release her outer private key during the nal phases 36

of the protocol. When C 0 guesses correctly, he behaves exactly as C would in the anonymity game and the game ends with the output of A. When C 0 guesses incorrectly, the game output is a random bit. C 0 guesses independently of A, and so we will be able to show that the game outputs advantage in Game 0 is 1/2 the advantage of A in the anonymity game. Then we dene Game 1, in which a further modied challenger C 1 creates the inner or outer ciphertexts of by starting with a plaintext unrelated to the challenge message mb . We will be able to show that advantage in Game 1 is negligibly close to the advantage in Game 0 by showing how a non-negligible change in advantage would allow us to distinguish encrypted messages with non-negligible probability. Finally, we dene Game 2 by creating a challenger C 2 from C 1 in the same way that C 1 was created from C 0 , except replacing by and mb with m b in the changes. We can show that the advantage changes negligibly from Game 1 to Game 2 using a similar argument as used from Game 0 to Game 1. It will be the case that the advantage in Game 2 must be 0 because the adversary sees the same distribution of messages from the challenger regardless of the challenge bit. Let h1 , h2 , . . . , hN k be the honest users in the order they appear in the shufe. Let Z i indicate that the challenger C i guesses that h1 should release her outer private key at some point as part of ANONYMIZE - S, let Gi be a game output for Game i, and let F i indicate whether or not the challenger failed in Game i. In the games and their associated random variables, the challenge bit b is a hidden input that we generally omit. Game 0: In this game, A interacts with a challenger C 0 that sometimes fails. C 0 sets Z 0 {0, 1} uniformly at random. C 0 behaves the same as C except in the following cases of the challenge shufe, when his guess about which keys will be released proves to be incorrect: 1. In Phase 3 (Anonymization), Z 0 = 0 and the partial decryptions of the outer ciphertexts C sec . . . , I sec do not appear exactly once each in the ciphertext vector and C with keys I1 h1 1 Ch1 1 sent to h1 . C 0 can check this by comparing to the partial ciphertexts created during Phase 2a. 2. In Phase 4 (Verication), Z 0 = 0 and either of the inner ciphertexts C and C is missing either from the copy of vector CN sent to or from the copy sent to . Again, C 0 can notice this by comparing to inner ciphertexts created during Phase 2a. 3. In Phase 5 (Key Release and Decryption), Z 0 = 1 and member h1 receives GOj = TRUE and HASH {Bj } = HASH {Bh1 } for every member j = h1 , and GO h1 = TRUE . 4. In Phase 6 (Blame), Z 0 = 0 and i) GOh1 = FALSE, ii) h1 received GOj = FALSE from any member j , or iii) h1 received HASH{Bj } = HASH{Bh1 } from any member j . In each of these cases, F 0 = 1, C 0 terminates, and the game output G0 is set to a uniformly random bit. In every other case, F 0 = 0, C 0 correctly executes ANONYMIZE - S on behalf of the honest users, and G0 is set to the output bit of A. Game 1: In this game, we further modify the challenger to dene C 1 , which replaces with unrelated ciphertexts the intermediate stages of the construction of the inner or outer ciphertext of , depending on Z 1 . That is, C 1 behaves the same as C 0 , except 1. In Phase 2a,

37

Case 1: Z 1 = 0. A partially encrypted outer ciphertext for is created and stored as C = {{}I pub :I pub }Opub :Opub , and the outer ciphertext is then created as C = {C }Opub :Opub .
N 1 N h1 h1 1 1

Also create C = {mb }I pub :I pub for later use. The public keys used for each ciphertext of 1 N are those received by in Phase 1. Case 2: Z 1 = 1. The inner ciphertext for is created and stored as C = {}I pub :I pub , and the outer ciphertext C is created from C in the same way as C 0 . Again, the public keys used for each ciphertext of are those received by in Phase 1. The rest of the phase is executed in the same way as C 0 . 2. In Phase 3, if Z 1 = 0 and both the stored ciphertext C and the partial decryption of C sec . . . , I sec (which C 1 knows because it created C ) appear exactly once each in the by IN h1 1 vector of ciphertexts Ch1 1 sent to h1 , then replace C with {C }Opub :Opub for inclusion in
N h1 +1 N 1

the vector Ch1 sent to h1 + 1, where the encryption uses the outer keys sent to . In every other way, C 1 executes in the same way as C 0 . Game 2: This game is created from Game 1 using the same changes given in its denition, except replacing with and mb with m b everywhere. The following lemma shows that Game 0 is a relevant starting point because its outputs advantage is 1/2 the advantage of A in the anonymity game: 1 P r AC (0) = 1 P r AC (1) = 1 , 2 where the probability is taken over the randomness of both the adversary and the challenger. (G0 ) = Proof. Let TA,C be the set of all possible game transcripts, that is, sequences of messages, between A and C . Let TA,C 0 be the set of transcripts between A and C 0 . We claim that each member of TA,C and TA,C 0 falls into exactly one of following cases, which are nearly the same as the failure cases dening Game 0: 1. In Phase 3, the expected ciphertexts of and are not sent to h1 exactly once each. 2. Case 1 does not occur, and in Phase 4, either of the inner ciphertexts C and C is missing from either the copy of vector CN sent to or the copy sent to . 3. At the start of Phase 5, GOh1 = TRUE, and h1 receives from every member j GOj = TRUE and HASH{Bj } = HASH{Bh1 }. 4. Case 1 does not occur, Case 2 does not occur, and at the start of Phase 6 i) GOh1 = FALSE, ii) h1 received GOj = FALSE from some member j , or iii) HASH{Bj } = HASH{Bh1 } from some member j . Cases 1, 2, and 4 are mutually exclusive events because the latter of these cases are explicitly dened to occur only when the previous do not. Case 3 is disjoint from the other three cases because each of them either results in termination before Phase 5 or results in GOh = FALSE sent in Phase 5 from an honest node h. One of these cases always occurs because one of the following is true of the execution: 38 Lemma 9.

1. The challenger fails, which as mentioned above only happens in one of these cases. 2. After Phase 4, GOh1 = FALSE or h1 received from some member j GOj = FALSE or HASH {Bj } = HASH {Bh1 }, which implies that one of Cases 1, 2, or 4 above occurred. 3. After Phase 4, GOh1 = TRUE and h1 received from every member j GOj = TRUE and HASH {Bj } = HASH {Bh1 }, which implies that Case 3 above occurred. Now consider members of TA,C that fall in Case 1 above. C 0 sends messages according to the same distribution as C up to the Phase 3 message to h1 . Whether or not Case 1 also applies to a transcript in TA,C 0 is determined by the messages up to this point. Thus the probability that Case 1 applies to a transcript in TA,C 0 is the same as for a transcript in TA,C . Moreover, Z 0 is independent of these messages, and thus C 0 fails under the rst failure case of Game 0 with probability 1/2 among those TA,C 0 transcripts in Case 1. Among those same transcripts where C 0 does not fail under the rst failure case, Z 0 must be 1 and GOh1 = FALSE if Phase 4 is reached, so the other failure cases of Game 0 dont apply and C 0 behaves the same as C throughout the transcript. Therefore, the distribution of TA,C 0 transcripts in Case 1 given that F 0 = 0 is the same as the distribution of TA,C transcripts in Case 1. Next consider those TA,C transcripts not in Case 1. Because Case 1 does not apply, C and C 0 behave the same up through Phase 3. Whether or not Case 2 applies is determined by the end of Phase 3. Thus the probability that Case 2 applies to a TA,C 0 transcript is the same as for a TA,C transcript. Z 0 is again independent of all partial TA,C 0 transcripts in Case 2 up through Phase 3. Thus, C 0 fails under the second Game 0 failure case in transcripts in this case with probability 1/2. Moreover, when C 0 does not fail under the second failure case but the transcript is in Case 2, Z 0 = 1 and either GOh = FALSE for one of h {, } or the hashes of the broadcast vectors of and dont match. Thus, the other failure cases of Game 0 dont apply, and so C 0 behaves the same as C throughout the transcript. Therefore, the distribution of TA,C 0 transcripts in Case 2 given that F = 0 is the same as the distribution of TA,C transcripts in Case 2. Next consider those TA,C transcripts not in either Case 1 or Case 2. Because Case 1 and Case 2 dont apply, C and C 0 behave the same up through Phase 4. Whether or not Case 3 applies is determined by the end of Phase 4. Thus the probability that Case 3 applies to a TA,C 0 transcript is the same as for a TA,C transcript. Z 0 is again independent of all partial TA,C 0 transcripts in Case 3 up through Phase 4. Thus, C 0 fails under the third failure case in transcripts in this case with probability 1/2. Moreover, when C 0 does not fail under the third failure case but the transcript is in Case 3, Z 0 = 0, GOh1 = TRUE, h1 receives GOj = TRUE from all j , and HASH{Bj } = HASH{Bh1 } for all j . Thus, the fourth failure case of Game 0 does not apply. The rst two failure cases cant apply to any transcript in Case 3, and so C 0 behaves the same as C throughout the transcript. Therefore, the distribution of TA,C 0 transcripts in Case 3 given that F 0 = 0 is the same as the distribution of TA,C transcripts in Case 3. Finally, consider those TA,C transcripts not in Case 1, Case 2, or Case 3. Because Cases 13 dont apply, C and C 0 behave the same up through Phase 5. Whether or not Case 4 applies is determined by the end of Phase 5. Thus the probability that Case 4 applies to a TA,C 0 transcript is the same as for a TA,C transcript. Z 0 is again independent of all partial TA,C 0 transcripts in Case 4 up through Phase 5. Thus, C 0 fails under the fourth failure case in transcripts in this case with probability 1/2. Moreover, the other failure cases dont apply to transcripts in Case 4, and so, when Case 4 applies but C 0 does not fail, C 0 behaves the same as C throughout the transcript. Therefore, 39

the distribution of TA,C 0 transcripts in Case 4 given that F 0 = 0 is the same as the distribution of TA,C transcripts in Case 4. Thus, because F 0 = 0 with probability 1/2 for each of the above cases, F 0 = 0 with probability 1/2 overall. In addition, because the distribution of TA,C 0 transcripts in each of the above cases conditional on F 0 = 0 is the same as the distribution of TA,C transcripts in the same cases, and the probability of each case is the same between TA,C and CA,C 0 , the conditional distribution of TA,C 0 0 given F 0 = 0 is the same as the distribution of TA,C . The game output G0 (b) is AC (b) if F 0 = 0 and is a uniformly random bit if F 0 = 1. Therefore, P r[G0 (b) = 1] = P r[F 0 = 0]P r[G0 (b) = 1|F 0 = 0] + P r[F 0 = 1]P r[G0 (b) = 1|F 0 = 1] 1 1 1 = P r[AC (b) = 1] + , 2 2 2 which proves the lemma. The next lemma shows that changing the ciphertexts between Game 0 and Game 1 can only change the advantage of the game output by a negligible amount. Lemma 10. (G1 ) (G0 ) is negligible. Proof. We prove the lemma by constructing a distinguisher D(b) that has a non-negligible advantage in the distinguishing game if |P r[G1 (b) = 1] P r[G0 (b) = 1]| is non-negligible. Let bD be the challenge bit in the distinguishing game. D interacts with the distinguishing-game challenger CD (bD ) and A to execute either Game 0 or Game 1, depending on bD , as follows: 1. D simulates the challenger of the anonymity game C (b) exactly up to Phase 1 of the challenge shufe. Let Z denote the random guess about later key releases that D makes as part of the simulation.
sec , I pub ) and (O sec , O pub ), 1 < i N k . 2. For Phase 1, D generates encryption key pairs (Ih hi hi hi i pub from CD and generates the encryption key pair D obtains the public encryption key K1 pub sec (K2 , K2 ). Then,

Case 1: Z = 0. D sets
pub pub Oh = K1 and 1 pub sec pub sec , Ih1 ) = (K2 , K2 ). (Ih 1

Case 2: Z = 1. D sets
pub pub Ih = K1 and 1 pub pub sec sec (Oh , Oh ) = (K2 , K2 ). 1 1

Then D broadcasts these public keys from the honest members as described in the protocol. 3. For Phase 2a, Case 1: Z = 0. D sets C = {mb }I pub :I pub , m0 = {C }Opub :Opub and
N 1 N h1 +1

m1 = {{}I pub :I pub }Opub :Opub , using the encryption keys of . D submits (m0 , m1 ) to CD ,
N 1 N h1 +1

40

and receives cbD as a response. D sets C = cbD . D then nishes the phase as C 1 would starting after it creates C in Case 1. Case 2: Z = 1. D sets m0 = {mb }I pub :I pub and m1 = {}I pub :I pub . D submits (m0 , m1 )
N h1 +1 N h1 +1

to CD and receives cbD as a response. D sets C = {cbD }I pub

using the keys received by . D then nishes the phase as C 1 would starting after it creates C in Case 2. 4. Phase 2b is executed as described in the protocol. 5. For Phase 3, D rst receives a ciphertext vector of Ch1 1 intended for h1 . Then
sec , . . . , I sec (which Case 1: Z = 0, and both C and the partial decryption of C by IN h1 1 D can check because that ciphertext was constructed by D alone) appear in Ch1 1 exactly once. Then D replaces C with m0 , decrypts the remaining ciphertexts using CD , shufes the vector, and sets Ch1 to the result. D then nishes the phase as described in the protocol starting with sending Ch1 to member h1 + 1.

pub h1 1 :I1

. All encryption is done

Case 2: Z = 0, and C or the partial decryption of C does not appear in Ch1 1 exactly once. In this case, D terminates the simulation and sets G {0, 1} uniformly at random. Case 3: Z = 1. D has the private outer keys for all honest members, and therefore can execute this phase just as C 1 would. D executes this phase for other honest members hi , i > 1, as described in the protocol. 6. D executes Phase 4 as C 1 would, which is possible because this phase uses no private keys. If C 1 terminates, D terminates the simulation and sets G {0, 1} uniformly at random. 7. D executes Phase 5 as C 1 would. This is possible because if Z = 0 D has the inner private keys and if Z = 1 C 1 fails if inner private keys are required. If C 1 fails, D terminates the simulation and sets G {0, 1} uniformly at random. 8. D executes Phase 6 as C 1 would. This is possible because if Z = 0 C 1 fails if outer keys are required and if Z = 1 D has the outer private keys. If C 1 fails, D terminates the simulation and sets G {0, 1} uniformly at random. 9. As many times as requested, D takes messages for the honest members and executes the shufe protocol with A. 10. If the simulation did not terminate prematurely, let bA be the guess output by A and set G = bA . D outputs its guess in the distinguishing game as bD = G. We claim that D simulates C bD with A, that is, that D effectively executes Game 0 or Game 1, depending on bD . That D correctly simulates all steps of the anonymity game except the challenge shufe (i.e. Steps 14, 6, and 7) follows because it is dened as doing so, and these steps are the same for C 0 and C 1 . To show that the challenge shufe (Step 5) is simulated correctly, we show that for each phase, D simulates C bD : Phase 1: Although one public key is determined by the challenger CD , the end result is that D broadcasts inner and outer public keys for honest members that are generated using the cryptosystems key generation algorithm, just as both C 0 and C 1 do. 41

 Phase 2a: Case 1: bD = 0. The result of using the response from CD to construct C is that commits to {{mb }I pub :I pub }Opub :Opub , where the keys used are those received by , just as in C 0 . The other honest members behave as they do in C 1 by denition, which is the same as in C 0 . Case 2: bD = 1. The result of using the response from CD is that commits to {{}I pub :I pub }Opub :Opub , where the keys used are those received by , just as in C 1 . The other honest members behave as they do in C 1 by denition. Phase 2b: D, C 0 , and C 1 all execute this phase as described in the protocol. Phase 3:
sec , . . . , I sec appear in Case 1: Z = 0 and both C and the partial decryption of C by IN h1 1 Ch1 1 exactly once. For h1 , D replaces C with m0 = {{mb }I pub :I pub }Opub :Opub when
N 1 N h1 +1 N 1 N 1 N 1 N 1

constructing Ch1 , and the other ciphertexts are simply decrypted . This is just as both C 0 and C 1 would have done. For the other honest members, D executes them as described in the protocol, just as C 0 and C 1 would do.
sec , . . . , I sec does not Case 2: Z = 0 and either C or the partial decryption of C by IN h1 1 0 1 appear in Ch1 1 exactly once. D terminates the game, just as both C and C would do.

Case 3: Z = 1. D executes just as C 1 would by denition, which is the same as C 0 . Phases 46: D executes these phases just as C 1 would by denition, which is the same as C 0 . Thus D correctly simulates C bD for A. Moreover, observe that when C bD does not prematurely terminate, then D uses the output bA of A for the game output G, and when C bD does terminate, then D randomly sets G {0, 1}. This is exactly how GbD is set. Therefore, the advantage of D in the distinguishing game is Pr bD = 1|bD = 1 P r bD = 1|bD = 0 = |P r[G = 1|bD = 1] P r[G = 1|bD = 0]| = P r G1 = 1 P r G0 = 1 . Therefore, because we assume that the cryptosystem is IND-CCA2, P r[G1 = 1] P r[G0 = 1] must be negligible. This implies the lemma. Game 1 is modied to create Game 2 by replacing some ciphertexts of just as Game 0 was modied to create Game 1 by replacing ciphertexts of . Thus for similar reasons as before, it holds that that the advantage of the game output changes by a negligible amount from Game 1 to Game 2. Lemma 11. (G2 ) (G1 ) is negligible. Proof. The proof is exactly the same as the proof for Lemma 10 except for the following changes:
c. 1. Everywhere is replaced by , is replaced by , and mc b is replaced by m b

2. The simulation claim is that D simulates C bD +1 for A, rather than C bD . Thus the resulting execution is identical to either Game 2 or Game 1, rather than Game 1 or Game 0, and the output G is has the same distribution as GbD +1 , rather than GbD . 42

We now show that when Game 2 does not fail, the adversary has the same view whether mc 0 belongs to or and therefore has no advantage in the output of Game 2. In doing so we view the challenger C 2 as invoking a subroutine C 2 that just executes the challenge shufe of the anonymity game. This view allows our results to be reused when proving the anonymity of the bulk protocol, which calls the shufe as a subprotocol. Specically, we consider the simulation by C 2 of ANONYMIZE - S during the challenge run of the shufe protocol as an invocation of C 2 . The inputs from C 2 to C 2 are the challenge bit b, c the challenge members and , the challenge messages mc 0 and m1 , the honest non-challenge messages {mh }hH \{, } , the round number nR , the signing keys K , the member ordering , and fail ags {fh = FALSE}hH . Let I be a vector all of these inputs except b. Let the output of honest members from the challenge shufe be O = (Oh1 , . . . , OhN k ), where Ohi is the output of hi . C 2 fails if and only if C 2 fails. Let F 2 indicate that C 2 fails. Let M be the transcript of messages between C 2 and A during the challenge shufe. When F 2 = 1, O and M are dened to take a constant failure value. The following lemma shows that changing the challenge bit b does not change the joint probability of challenger failure, shufe messages, and honest members shufe outputs: Lemma 12. P r[M = m O = o F
2

= f |I = i b = 0] = P r[M = m O = o F

= f |I = i b = 1].

Proof. We consider the messages sent in each phase as well as the nal output and show that they do not depend on b. In order to do this, we also track some of the internal variables and show that they are updated the same way regardless of b. Phase 1: C 2 sets guess Z 2 independently of b.
sec , I pub ) and (O sec , O pub ) Each honest member h generates inner and outer keypairs (Ih h h h independently of b. pub pub The message h1 = {Ih , Oh , nR , 1, h}SIGuh sent by each honest member h H is independent of b by the above.

The messages to h from other honest members are shown above to be independent of b. The messages to h from A are independent of b because A uses the outputs of SETUP - S as well as the messages from honest users to generate its messages, both of which are shown above to be independent of b. GOh is set to FALSE if h receives invalid public keys. Thus by the above GOh is independent of b. Phase 2a: This phase depends on Z 2 , which has been shown to be independent of b. Case 1: Z 2 = 0. The partially decrypted outer ciphertexts Ch = {{h}I pub :I pub }Opub :Opub , h {, }
N 1 N

do not depend on b by the above. 43

h1

 The outer ciphertexts Ch = {Ch }Opub

the above. The inner ciphertexts Ch = {dh }I pub :I pub , h H \{, }, do not depend on b by 1 N the above. The outer ciphertexts Ch = {Ch }Opub :Opub , h H \{, }, do not depend on b by 1 N the above. Note that the inner ciphertext C = {mb }I pub :I pub does depend on b (and similarly
N 1

pub h1 1 :O1

, h {, }, do not depend on b by

for C ). Case 2: Z 2 = 1. The inner ciphertexts Ch = {h}I pub :I pub , h {, }, do not depend on b by the 1 N above. The inner ciphertexts Ch = {dh }I pub :I pub , h H \{, }, do not depend on b by 1 N the above. The outer ciphertexts Ch = {Ch }Opub :Opub , h H , do not depend on b by the 1 N above. The commitments Xh = COMMIT{Ch , h}, h H , do not depend on b because h does not and Ch does not by the above. The message h2a = {Xh , nR , 2a, h}SIGuh sent by each h H does not depend on b by the above. The additional inputs to A since his last output are messages h2a , h H , shown above to be independent of b. Thus the messages i2a , i D, received by h H are independent of b. The messages h2a , h H , received by h H are shown above to be independent of b. GOh is set to FALSE if h receives an invalid commitment, h H . Thus GOh still does not depend on b by the above. Phase 2b: The message h2b = {OPEN{Xh }, nR , 2b, h}SIGuh sent by each h H does not depend on b by the above. The additional inputs to A since his last output are messages h2b , h H , shown above to be independent of b. Thus the messages i2b , i D, received by h H are independent of b. The messages h2b , h H , received by h H are shown above to be independent of b. GOh is set to FALSE if h receives an invalid opening or an opening to an invalid ciphertext, h H . Thus GOh still does not depend on b by the above. Phase 3:

44

 Whether C 2 fails depends on Z 2 , on the partially decrypted ciphertexts C and C , and on the ciphertexts h1 receives during the shufe. Z 2 , C , and C are shown above to be independent of b. If h1 = 1, then the received ciphertexts are in the openings of the message committments from the previous phases. These are shown above not to depend on b. If h1 > 1, then these ciphertexts are from the adversary in this phase, and since his last output, the adversary has only received as additional input messages from honest users that are independent of b, as shown above. Thus the outputs of A continue to be independent of b. In either case, therefore, the probability that C 2 fails is independent of b. h H chooses a permutation h to apply to the elements of the ciphertext vector it receives in this phase. h is chosen independently of b. The behavior of h1 depends on Z 2 , which has been shown to be independent of b. Case 1: Z 2 = 0. A message is only sent by h1 if C 2 does not fail, which itself only happens when C and C appear exactly once each among the received ciphertexts. In this case, h1 replaces these by {C }ON :Oh1 +1 and {C }ON :Oh1 +1 , where the keys used are those received by the and , respectively. If the encryption keys received by and do not match, then and will send different broadcast hashes to h1 in Phase 4, and C 2 will fail by Phase 6. Assuming C 2 does not fail, the replacements C 2 makes for C and C are mb and m b , respectively, multiply 2 encrypted in the same way. C simply decrypts the rest of the received ciphertexts using its outer private key. The received ciphertexts are received from A, which has not received any messages since the last phase. Therefore the above shows that these ciphertexts are independent of b. The permutation h1 used in the vector Ch1 is uniformly random. Thus, regardless of b, Ch1 contains in a random order m0 and m1 encrypted in the same way as well as the decryptions of the rest of the received ciphertexts. Therefore, assuming C 2 has not and will not fail, the message h1 3 sent by h1 is independent of b. sec , messages Case 2: Z 2 = 1. The message h1 3 sent by h1 depends on h1 ,Oh 1 from the previous phases, and messages from the adversary in this phase. These are all shown above to be independent of b. The message i3 from member i > h1 depends on the messages from previous phases and messages in this phase from members j < i. We have shown above that messages from previous phases are independent of b. We inductively assume that messages in this phase from j < i are independent of b. For i D, the only additional inputs A has received since the last phase are j 3 , j < i, and therefore its outputs continue to be independent of b. For i H , i3 contains the permutation and decryption of the sec used ciphertexts received by i in (i1)3 . The permutation i and decryption key Oi are shown above to be independent of b. Therefore i3 is independent of b. GOh , h H , may be set to FALSE depending on the ciphertexts in h3 . This message is shown above to be independent of b, and so GOh remains independent of b. The messages h3 , h H received by h H are shown above to be independent of b. Phase 4: 45

 C 2 fails if Z 2 = 0 and either or received a vector CN that didnt contain both inner ciphertexts C and C at least once. If encryption keys received by and match, then the set {C , C } contains m0 and m1 encrypted in the same way, and thus it does not depend on b. CN and Z 2 are shown above to be independent of b. Therefore, if the encryption keys of and match, whether or not C 2 fails is independent of b. If those encryption keys dont match, then C 2 will fail in Phase 6. The keys are received in an earlier phase, and so it follows from above that whether or not they match is independent of b. GOh , h H \{, }, is updated depending on the inner ciphertext Ch , N 3 , the fail ag fh , and GOh itself, all of which are shown above to be independent of b. Thus GOh remains independent of b. The update to GOh , h {, }, depends on Z 2 , which is shown above to be independent of b, as follows: Case 1: Z 2 = 0. In this case, if the ciphertext vector CN sent to both and does not contain both the inner ciphertexts of and , then C 2 will fail. Assuming that C 2 does not fail, both GO and GO get set to FALSE if the fail ag is fh = TRUE, and otherwise keep any existing FALSE value or get a new value of TRUE. They thus remain independent of b. Case 2: Z 2 = 1. For h {, }, GOh is updated depending on fh , the message N 3 received by h, on Ch , and on GOh itself. In this case, the inner ciphertext Ch is shown above to be independent of b. Likewise, fh , N 3 and GOh are shown above to be independent of b. The message h4 = {GOh , HASH{B }, nR , 4, h}SIGuh , h H , does not depend on b by the above. The additional inputs to A since his last output are messages h4 , h H , shown above to be independent of b. Thus the messages i4 , i D, received by h H are independent of b. The messages h4 , h H , received by h H are shown above to be independent of b. Phase 5: Whether C 2 fails in this phase depends on Z 2 and on the messages sent and received by h1 . These are shown above to be independent of b, and thus failure in this phase is independent of b also. The message h5 sent by h H and several internal variables are set differently depending on the messages i4 sent and received by h, which are shown above to be independent of b, as follows: Case 1: h receives all GOi = TRUE and HASH{Bi } = HASH{Bh }. sec , n , 5, h} SIG The message h5 = {Ih uh does not depend on b by the above. R SUCCESSh depends on the messages sent and received up to and including this phase. These messages are shown above to be independent of b, and thus SUCCESSh is also.

46

 Mh depends on SUCCESSh and on the messages sent and received up to and including this phase. All of these are shown above to be independent of b, and thus Mh is also. Case 2: h receives some GOi = FALSE or HASH{Bi } = HASH{Bh }. The message h5 = {0, S, nR , 5, h}SIGuh does not depend on b by the above. SUCCESSh is set to FALSE, and thus is independent of b. The additional inputs to A since his last output are messages h5 , h H , shown above to be independent of b. Thus the messages i5 , i D, received by h H are independent of b. The messages h5 , h H , received by h H are shown above to be independent of b. Phase 6: Whether C 2 fails in this phase assuming the encryption keys of and match (a case already covered above) depends on Z 2 and on the messages sent and received by h1 . These are shown above to be independent of b, and thus failure in this phase under the matching-keys assumption is independent of b also. The message h6 sent by h H is created differently depending on SUCCESSh and the messages sent and received before this phase. These are shown above to be independent of b, and so the relevant case is independent of b as well. Case 1: SUCCESSh = TRUE. The message h6 = {T , nR , 6, h}SIGuh sent by h depends only on messages sent and received in previous phases. They are shown above to be independent of b, and thus h6 is as well. Case 2: SUCCESSh = FALSE, and for all i GOi = TRUE and HASH{Bi } = HASH {Bh }. The message h6 = {T , nR , 6, h} SIG uh sent by h depends only on messages sent and received in previous phases. They are shown above to be independent of b, and thus h6 is as well. Case 3: SUCCESSh = FALSE, and for some i GOi = FALSE or HASH{Bi } = sec , , T , n , 6, h} SIG HASH {Bh }. The message h6 = {Oh uh sent by h depends R h on messages sent and received in previous phases as well as some internal variables, all of which are shown above to be independent of b. The additional inputs to A since his last output are messages h6 , h H , shown above to be independent of b. Thus the messages i6 , i D, received by h H are independent of b. The messages h6 , h H , received by h H are shown above to be independent of b. The outputs and some internal variables are set differently depending on SUCCESSh and the messages sent and received before this phase. These are shown above to be independent of b, and so the relevant case is independent of b as well. Case 1: SUCCESSh = TRUE. The output Oh = (SUCCESS, Mh ) is shown above to be independent of b. Case 2: SUCCESSh = FALSE, and for all i GOi = TRUE and HASH{Bi } = HASH {Bh }.

47

 BLAMEh is set based only on messages sent and received up to this point and thus by the above is independent of b. Log h includes the output of SETUP - S and all messages sent and received by h and thus is independent of b by the above. The output Oh = (FAILURE, BLAMEh , h ) is shown above to be independent of b. Case 3: SUCCESSh = FALSE, and for some i GOi = FALSE or HASH{Bi } = HASH {Bh }. BLAMEh is set based only on messages sent and received up to this point and thus by the above is independent of b. Log h includes the output of SETUP - S and all messages sent and received by h and thus is independent of b by the above. The output Oh = (FAILURE, BLAMEh , h ) is shown above to be independent of b. Finally, we are able to prove that the messages, outputs, and failures of C 2 are independent of b. The above analysis shows that the probability of failure does not depend on b. This implies that the probability that the messages M and outputs O of honest members take their constant failure values independently of b as well. When C 2 does not fail, the above analysis shows that all messages and outputs from honest members are determined independently of b. Thus P r[M = m O = o F
2

= f |I = i b = 0] = P r[M = m O = o F

= f |I = i b = 1].

We use this independence from b of the challenge shufes messages, outputs, and failure to prove that the adversary has no advantage in Game 2. Lemma 13. (G2 ) = 0. Proof. To prove this, we show that the steps of the anonymity game surrounding the challenge shufe are independent of b and use the previous lemma for the challenge shufe itself. 1. In Step 1, the protocol executions are independent of b. 2. In Step 2, the all messages to the adversary have been independent of b, and so the users and messages A sends to C 2 for the challenge run are independent of b. 3. In Step 3, the challenger should assign the challenge messages to the correct challenge users, depending on b. However, we have modied the challenger to create Game 2 such that this is not necessary, and so we can omit this step. 4. During the challenge run in Step 4, C 2 rst executes SETUP - S using as input the honest members long-term signing keys, which are independent of b, as are the previous messages to A, and so the output (nR , K, L) of SETUP - S is independent of b. C 2 then calls C 2 with c inputs I = (, , mc 0 , m1 , {mh }hH \{, } , nR , K, ) and b. I is determined by previous messages from A and the outputs of SETUP - S. These have been shown to be independent of b, and thus I is as well. We can then apply Lemma 12 to conclude that the joint distribution of shufe failure and messages to A are independent of b. 48

5. If C 2 didnt fail, which as shown occurs independently of b, then C 2 executes Step 5 of the anonymity game by executing additional protocol executions. These depend on messages from A, and all messages to A have been shown independent of b. Thus these executions are independent of b. 6. The adversarys guess b in Step 6 depends on the messages to A and the possible failure of C 2 . These have been shown to be independent of b, and so b is independent of b. G2 (b) depends on F 2 and b. These have been shown to be independent of b, and thus P r[G2 (1) = 1] = P r[G2 (0) = 1].

Theorem 5. The GMP - SHUFFLE protocol maintains anonymity with k colluding members for any 0 k N 2. Proof. Let A be a probabilistic polynomial-time adversary. Let the change in advantage between Games i and j be ij = (Gj ) (Gi ) . By Lemma 9, the advantage of A in the anonymity game with GMP - SHUFFLE is 2(G0 ) 2( 01 + 12 + (G2 )). 01 is negligible by Lemma 10, 12 is negligible by Lemma 11, and (G2 )=0 by Lemma 13. Thus the advantage of A in the anonymity game with GMP - SHUFFLE is negligible. 5.5.2 The GMP-Bulk Protocol

We show that the adversarys advantage in winning the anonymity game with GMP - BULK is negligible. As in the shufe anonymity proof (Section 5.5.1), we take an adversary A playing against the anonymity-game challenger C and construct a sequence of games by successively modifying the challenger. We will show how any non-negligible difference in the games advantage between neighboring games will contradict assumed security properties of the cryptographic primitives. The nal game will be information-theoretically secure, that is, the output advantage will be zero. We incorporate the anonymity proof for the shufe by using that sequence of games (extended to GMP - BULK) as game subsequences modifying the challenger during the bulk protocols shufe phases. We dene Game 0, Game 1, and Game 2 by changing the behavior of C during the messagedescriptor shufe in Phase 3. The changes are essentially the same as those made in Game 0, Game 1, and Game 2, respectively, in the shufe anonymity proof (Section 5.5.1). We then similarly dene Game 3, Game 4, and Game 5 by applying the same sequence of changes to the blame shufe in Phase 7. We replace the encrypted seeds sent in the message descriptors of and with unrelated ciphertexts to dene Game 6. Finally, in Game 7, we replace the pseudorandom bit streams sent during data transmission with random streams. As before, let h1 , h2 , . . . , hN k be the honest users in the order they appear in the shufe. Let i and Z i indicate that challenger C i guesses that h C i be the challenger dened in Game i. Let Z1 1 2 should release her outer private key at some point as part of the message descriptor shufe (Phase 3) and the blame shufe (Phase 7), respectively. Let F i indicate whether or not the challenger failed in Game i. Let Gi indicate a game output for Game i. The challenge bit b is again an implicit input to the games challengers and associated random variables. 49

0 {0, 1} uniformly at random as a guess Game 0: We create a challenger C 0 that sets Z1 about if h1 should reveal an outer private key during the message-descriptor shufe of the challenge run in the bulk anonymity game. That is, C 0 behaves the same as the anonymity-game challenger except that he fails if his guess proves to be wrong at certain points during Phase 3 of the challenge 0 in place of Z 0 ) as those dening protocol run. These failure points are exactly the same (using Z1 C 0 for Game 0 of the shufe anonymity analysis (Section 5.5.1), and so we do not repeat them here. Again, when failure occurs, F 0 = 1, C 0 terminates, and the game output G0 is set to a uniformly random bit. In every other case, F 0 = 0, C 0 behaves exactly as C would. Game 1: We again reuse the changes described in the shufe anonymity analysis. We create challenger C 1 by applying the changes that dene C 1 for Game 1 of the shufe analysis to the challenger C 0 dened above. These changes are made to the Phase 3 shufe of the challenge run 1 , and in the bulk anonymity game. Everywhere Z 1 appears in these changes, we instead use Z1 c everywhere mb appears, we instead use the shufe input of (which is a message descriptor). These changes effectively replace a ciphertext containing the message descriptor of with one that contains a dummy message until it has been shufed by the rst honest member. Game 2: As in the shufe anonymity analysis, this game is created from Game 1 above in the 1 with Z 2 , with , and same way that Game 1 itself was created from Game 0, except replacing Z1 1 the shufe input of with the shufe input of . This effectively replaces a ciphertext containing the message descriptor of with one that contains a dummy message until it has been shufed by the rst honest member. Games 35: These games further modify the challenger by adapting and applying the sequence of changes given in the shufe anonymity analysis as was done to dene Games 02 above. This time, however, we apply the changes to the blame shufe (Phase 7) of the challenge protocol run. i , and the shufe inputs to and are accusations rather than In addition, the guess bit is denoted Z2 message descriptors. Game 6: We dene challenger C 6 from C 5 by changing the inputs to the message-descriptor shufe of the challenge run. During the generation of message descriptors (Phase 2), we replace the encrypted seeds S and S with the encryption of new random seeds. Specically,

1. For , we replace the encrypted seed it creates for in Case 1 of Phase 2 with an encryption of the new random seed s . That is, we set S = {s }y , where the encryption key is among those received in Phase 1a. Note that the original seed s is still created and used to generate the ciphertext C . 2. For , we replace the encrypted seed it creates for in Case 1 of Phase 2 with an encryption of the new random seed s . That is, we set S = {s }y , where the encryption key is among those received in Phase 1a. Again, note that the original seed s is still created and otherwise used as before. Then during data transmission (Phase 4), C 6 recognizes the seeds that match s and s among those received by and , respectively, and simply uses the original seeds to generate the necessary ciphertexts. More precisely, for , in Case 2 of Phase 4, whenever a value Si received by decrypts to a seed that the challenger recognizes is identical to s , sets Ci to the ciphertext C that was generated earlier from s . A similar action is taken for , where this time the challenger looks for decrypted seeds matching s and uses C for the ciphertext. Game 7: We construct challenger C 7 from C 6 by replacing some pseudorandomness with true 50

randomness during the challenge protocol run. For and , in Case 1 of Phase 2 (descriptor generation), the ciphertexts C and C , respectively, are chosen uniformly at random rather than being generated pseudorandomly. Note that these random ciphertexts are then used in the computation of C and C , respectively. Then in Case 2 of Phase 4 (data transmission), and use these random sequences as ciphertexts. That is, sends the random C generated in Phase 2 for every decrypted seed si that matches s . Similarly, sends the random C generated in Phase 2 for every decrypted seed si that matches s . The following lemma shows that, as in the shufe proof, the outputs advantage in Game 0 is 1/2 the advantage of A in the anonymity game: Lemma 14. 1 P r AC (0) = 1 P r AC (1) = 1 , 2 where the probability is taken over the randomness of both the adversary and the challenger. (G0 ) = Proof. The proof of this lemma is almost exactly the same as the proof of Lemma 9. We simply interpret each reference to a phase of the challenge shufe as instead referring to a phase of the message-descriptor shufe in the bulk protocol. We also replace Z 0 everywhere it appears with 0. Z1 The next lemma shows that, as in the shufe proof, the ciphertext changes from Game 0 to Game 2 can only change the advantage of the game output by a negligible amount. Lemma 15. (G2 ) (G0 ) is negligible. Proof. Games 1 and 2 are constructed by making essentially the same changes to the challengers behavior during the descriptor shufe that were made in Games 1 and 2 of the shufe anonymity analysis. Thus, the proof that these two sets of changes each only change the output advantage by a negligible amount is almost exactly the same as the proofs of Lemmas 10 and 11. In these proofs, a distinguisher D is constructed that simulates either member of a pair of adjacent games for the adversary, depending on the hidden bit of the distinguishing game. The proofs show that this distinguisher converts a non-negligible change in the game outputs advantage to a non-negligible advantage in the distinguishing game. Such an advantage would contradict the IND-CCA2 property of the cryptosystem. We slightly modify the argument of that sort in the proof of Lemma 10 to prove that the output advantage changes negligibly between Game 0 and Game 1. We construct a distinguisher DB that is the same as D in that proof with the following differences: 1. In Step 1 of D, DB instead executes the anonymity game up to the challenge run of the bulk protocol (rather than the shufe protocol). 2. DB then executes Phase 1 and Phase 2 of bulk protocol exactly, ending up with the inputs of honest members to shufe protocol mhi that are constructed during Phase 2. 3. DB continues with Step 2 of D. 4. DB continues with Steps 38 of D, replacing mb with m everywhere.

51

5. After Step 8 of the distinguisher is nished, the message-descriptor shufe (i.e. Phase 3) of the bulk protocol is over, and the DB uses the outputs of the honest members to execute the rest of the bulk protocol (Phase 4 Phase 7) as described in the protocol. By applying the subsequent arguments of Lemma 10 to DB (again substituting m for mb in the arguments), we can show that the game outputs advantage changes negligibly between Game 0 and Game 1. We can adapt the distinguisher construction and subsequent arguments of Lemma 11 in the same way (except using in place of and b in place of b) to show that the game outputs advantage changes negligibly between Game 1 and Game 2. Game 3 is created by applying the rst game transformation of the shufe proof to the blame shufe in Game 2, that is, by having the challenger guess about the revelation of outer private keys. Thus, as in the shufe proof, the game advantage decreases by a factor of 1/2:
2 Lemma 16. (G3 ) = 1 2 (G ), where the probability is taken over the randomness of both the adversary and the challenger.

Proof. As with Lemma 14, the proof of this lemma is almost exactly the same as the proof of Lemma 9. We apply that proof to this lemma by interpreting each reference to a phase of the challenge shufe as instead referring to a phase of the blame shufe in the challenge bulk round. As we are comparing Games 2 and 3 rather than the anonymity game and Game 0, everywhere they 3 . In addition, the appear we replace C with C 2 , AC (b) with G2 (b), C 0 with C 3 , and Z 0 with Z2 3 2 transcripts between A and C (i.e. TA,C 2 ) and between A and C (i.e. TA,C 3 ) may fall into one more case than the four given in that proof. The challenger may fail with an incorrect guess Z1 during the descriptor shufe. The proof of Lemma 14 shows that this failure occurs with probability 1/2 in Game 0, and in Game 2 this failure continues to occur with probability 1/2 and for the same reasons, namely that each transcript falls into exactly one of the four listed cases, and failure occurs 2 has a certain value. The proof of Lemma 9 can in each case when the independently random bit Z1 easily be modied to include this failure case, with the following modied conclusions: 1. Each transcript case occurs with the same probability for TA,C 2 and TA,C 3 . 2. Failure occurs in every case except for the added one (which always fails) with probability 1/2. 3. The distribution of transcripts in TA,C 3 conditional on F 3 = 0 is, in every case except the added one, the same as the distribution of transcripts in the same case in TA,C 2 . These imply that F 3 = 0 with probability 1/4 and that the conditional distribution of TA,C 3 given F 3 = 0 is the same as the distribution of TA,C 2 given that F 2 = 0. The game outputs G3 and G2 are the adversary output when the challenger does not fail and are uniformly random bits otherwise. Thus 1 P r G3 (0) = 1 P r G3 (1) = 1 = P r[G3 (0) = 1|F 3 = 0] P r[G3 (1) = 1|F 3 = 0] 4 1 = P r[G2 (0) = 1|F 2 = 0] P r[G2 (1) = 1|F 2 = 0] 4 1 = P r[G2 (0) = 1] P r[G2 (1) = 1] 2

52

Changing ciphertexts from the challenger from Game 3 to Game 5 has only a negligible effect on the output advantage, as in the analogous game transitions of the shufe proof: Lemma 17. (G5 ) (G3 ) is negligible. Proof. This lemma can be proven using the arguments of Lemma 15 applied to the blame shufe rather than the descriptor shufe. Those construct distinguishers and show that they convert a nonnegligible change in the game output between Games 3 and 4 or between Games 4 and 5 into a non-negligible advantage in the IND-CCA2 game. This would contradict the IND-CCA2 property of the cryptosystem. Game 6 is created from Game 5 by changing some PRNG seeds that are then encrypted and sent by the challenger. By the IND-CCA2 property of the encryption scheme, this can only have a negligible effect on the output advantage: Lemma 18. (G6 ) (G5 ) is negligible. Proof. To prove this lemma, we consider the two ciphertext changes in sequence: i) {s }y gets replaced by {s }y and ii) {s }y gets replaced by {s }y . For each change, we can construct a distinguisher that converts a non-negligible change in the game-output distribution into a nonnegligible advantage in the distinguishing game. Let Game 5a refer to the game that results from just the ciphertext replacement in (i). Let CD be the challenger in the distinguishing game and bD be the challenge bit. We construct a distinguisher D that simulates either Game 5 or Game 5a, depending on bD , as follows: 1. D simulates the anonymity-game challenger C 5 up to the challenge run of the bulk protocol. 2. To begin Phase 1 of the bulk protocol (key generation), D obtains the public encryption key KD from CD and sets y = KD . D generates the encryption key pairs (xh , yh ) for all other honest users. Then D continues with the rest of Phase 1a (session-key generation) followed by Phase 1b (key verication), acting as C 5 would. 3. D executes Phase 2 (descriptor generation) for as follows: Case 1: If key verication is successful (Case 1 of Phase 2), D executes the phase for as C 5 would up to the point at which S is assigned. At this point, D randomly chooses a new seed s , submits (s , s ) to CD , receives cbD as a response, and sets S = cbD . D executes the rest of the phase for as C 5 would. Case 2: If key verication fails (Case 2 of Phase 2), D executes the phase for as C 5 would. Case 3: This case will never execute for because has message mb to send. D executes Phase 2 for the other honest members as C 5 would. 4. D executes Phase 3 as C 5 would.

53

5. D executes Phase 4 (data transmission) for as follows: Case 1: If the descriptor shufe failed (Case 1 of Phase 4), D executes the phase for as C 5 would. Case 2: Otherwise the descriptors were successfully received (Case 2 of Phase 2). For each encrypted seed Si received by in a descriptor, if Si matches the encrypted seed S = cbD created by for , then D sets si to the seed s chosen by in Phase 2, rather than obtaining it by decrypting Si . Otherwise, D sends Si to CD for decryption, receiving s in response. If s = s , then set si = s , and otherwise set si = s. D completes the phase as C 5 would. D executes this phase for the other honest members as C 5 would. 6. D executes Phase 5 (acknowledgement submission) and Phase 6 (message recovery) as C 5 would. 7. D executes Phase 7 (blame) as C 5 would. It will never be required for D to produce the random bits used to produce S , which it would be unable to do, because only sends ciphertexts with correct hashes for slots with the descriptors of honest members. 8. D executes the rest of the anonymity game after the challenge run as C 5 would. 9. D uses G as its guess bD . We observe that, except with negligible probability, D simulates C 5 if bD = 0 (i.e. if cbD = {s }y ), and D simulates C 5a if bD = 1. Note that, depending on bD , D creates a message descriptor for that contains as a seed for either the encryption of s or of s . Moreover, if bD = 1, D correctly uses s for all encrypted seeds received by that match s , and, if bD = 0, the probability that receives an encryption of s and (incorrectly) uses s as the decryption is negligible because s is never used in the simulation up to that point and is chosen independently at random. In addition, the ciphertexts sent to the decryption oracle never match the forbidden text cbD = S because in those cases the decryptions are copied directly from the seed created by for . In every other way, C 5 and C 5a act the same, and D simulates their behavior. The output of D is the game output G(b), where b is the challenge bit of the simulated anonymity game. G(b) is set exactly as it is by the simulated challenger except with negligible probability, and thus the advantage of D is negligibly close to the change in G(b) for any b. That is, P r[ bD = 1|bD = 0] P r[ bD = 1|bD = 1] P r[G5 (b) = 1] P r[G5a (b) = 1] is negligible. Because the advantage in the distinguishing game is negligible by the IND-CCA2 property of the cryptosystem, the change in the output distribution between Game 5 and Game 5a for a given value of b must be negligible. This implies that the change in the output advantage is also negligible. Applying ciphertext replacement (ii) to Game 5a results in Game 6. Essentially the same argument as above (simply swapping and everywhere) shows that the output advantage changes negligibly as a result of this replacement. Thus the output advantage changes negligibly between Game 5 and Game 6.

54

We create Game 7 from Game 6 by replacing some pseudorandom streams with random streams. By the pseudorandomness of the PRNG, doing so has a negligible effect on the output advantage: Lemma 19. (G7 ) (G6 ) is negligible. Proof. Consider the changes made to C 6 in the following sequence: i) chooses the ciphertext C in Phase 2 randomly instead of pseudorandomly, and uses that ciphertext in Phase 4; and ii) chooses the ciphertext C in Phase 2 randomly instead of pseudorandomly, and uses that ciphertext in Phase 4. Let Game 6a be the game dened by applying (i) to Game 6. Game 7 is then (ii) applied to Game 6a. We can show that the game output changes negligibly for each pair in this short sequence by constructing a distinguisher that converts a change in the game output probability to the same advantage in the pseudorandomness game. Let CR be the challenger in the pseudorandomness game, and let bR be its challenge bit. Distinguisher D interacts with CR to simulate either Game 6 or Game 6a for the adversary, depending on bR . Let D behave as follows: 1. D executes the anonymity game as C 6 would up to the challenge run of the bulk protocol. 2. D executes Phase 1 as C 6 would. 3. In Phase 2, D receives r from CR . For member , D sets C = r in Case 1 and otherwise executes the phase for as C 6 would. D executes Phase 2 for all other honest members as C 6 would. 4. D executes Phase 3 as C 6 would. 5. In Phase 4, for member , D sets Cj = r for all decrypted seeds si that are identical to the seed s generated by . D otherwise executes Phase 4 for as C 6 would. D executes Phase 4 for all other honest members as C 6 would. 6. D executes Phase 5, Phase 6, and Phase 7 as C 6 would. 7. D executes the rest of the anonymity game after the challenge run. 8. D uses the game output of the simulated challenger as guess bR . We observe that if bR = 0 (i.e. r is pseudorandomly generated by CR from an unknown random seed s), then D simulates Game 6, and if bR = 1, then D simulates Game 6a. In particular, D can execute the blame phase without knowing the seed that is used to generate r, if any, because the encrypted seed included in the descriptor d is already an unrelated seed s . Also, the challenger creates the encrypted seeds in both games, and so any accusation can be correctly generated, although because only generates accusations for slots with its own descriptor d , and always produces correct ciphertexts when using d , it should in fact never be the case that generates an accusation involving the ciphertexts changed between Game 6 and Game 6a. The guess bit bR of D is thus G6 when bR = 0 and G6a when bR = 1. Therefore if the difference between P r[G6 (b) = 1] and P r[G6a (b) = 1] were non-negligible for some b, then D could achieve a non-negligible advantage in the pseudorandomness game. This would contradict pseudorandomness, and thus the change in the output advantage from Game 6 to Game 6a is negligible. A nearly identical argument, simply swapping and everywhere, shows that there is a negligible change in the game advantage from Game 6a to Game 7 as well. Thus, the change in the game advantage from Game 6 to Game 7 is negligible. 55

By Game 7, the adversary has the same view whether m0 belongs to or , and thus there is no advantage in the game output. In order to show this, we follow the approach of Lemmas 12 and 13, and we view the challenger C 7 as calling a subroutine C 7 to execute ANONYMIZE - B during the challenge run. This allows a natural decomposition of the proof, and it also us to express the fact that in addition to the messages to the adversary, the outputs of the bulk protocol are independent of b. Thus if, for example, the members decide later to come to a consensus about the results of the bulk protocol, that information wont break anonymity. C 7 takes as input the challenge bit c 7 b and I = (nR , nR1 , nR2 , K, , , , mc 0 , m1 , {mh }hH \{, } ). C either fails or returns output O = (Oh1 , . . . , ON k ), where Oh is the output of ANONYMIZE - B for member h. C 7 fails if and only if C 7 fails. In addition, we view C 7 as executing the descriptor and blame shufes by calling as a subroutine the challenger C 2 as dened in Section 5.5.1 for use in Lemma 12. C 7 uses as inputs to C 2 the same K , , , and that itself received. It uses nR1 as the round nonce input for the descriptor shufe (i.e. Phase 3) and nR2 as the round nonce input for the blame shufe (i.e. Phase 7). The member messages and fail ags are determined from its own inputs as described in the bulk protocol c1 1 1 description. For the descriptor shufe, we denote by mc 0 and m1 the challenge messages, by mh c2 1 the non-challenge messages, and by fh the fail ags. For the blame shufe, we denote by m0 and 2 2 2 mc 1 the challenge messages, by mh the non-challenge messages, and by fh the fail ags. We denote 1 , . . . , O1 2 2 2 by O1 = (Oh hN k ) the output of the descriptor shufe and by O = (Oh1 , . . . , OhN k ) 1 the output of the blame shufe. C 7 fails if and only if one of the two invocations of C 2 fails. Let M be the transcript of all messages between members during the protocol. Let F 7 be the event that C 7 fails. When F 7 = 1, O and M are dened to take a constant failure value. The following lemma shows that changing b does not change the joint distribution of M , O, and F 7 . Lemma 20. P r[M = m O = o F
7

= f |I = i b = 0] = P r[M = m O = o F

= f |I = i b = 1].

Proof. To prove this, we track the dependence on b of messages from C 7 to A, internal variables of C 7 , and outputs of C 7 . This analysis will show that the messages and outputs of C 7 follow the same distribution regardless of b. In order to do this despite the dependence of some variables on b, we will consider two parallel executions of the challenge round, one in which b = 0 and one in which b = 1. The messages, variables, and outputs that do not depend on b will indeed be the same in the two executions. The variables that do depend on b may have different states between the two executions, but the probability of those paired states will be the same. We consider these executions step-by-step as follows: Phase 1a: Encryption keys (xh , yh ) are generated independently of b. The message h1a from h H is independent of b by the above. The additional inputs to A since his last output are messages h1a , h H , shown above to be independent of b. Thus the messages i1a , i D, received by h H are independent of b. The messages h1a , h H , received by h H are shown above to be independent of b. 56

 Phase 1b:
e , n , 1b, h} SIG The message h1b = {Kh uh from h H contain keys received from R other members and thus is independent of b by the above.

The additional inputs to A since his last output are messages h1b , h H , shown above to be independent of b. Thus the messages i1b , i D, received by h H are independent of b. The messages h1b , h H , received by h H are shown above to be independent of b. Phase 2: We consider several cases for how challenge members form descriptors. These cases depend on the keys that honest members received in the previous phases, and thus by the above the applicable case does not depend on b. Case 1: All honest members received valid and matching keys in the previous phases. In this case, the descriptors d and d do depend on b, and so we compare their generation when b = 0 and when b = 1. We observe that the descriptor for the challenge member h {, } assigned m0 is created the same regardless of whether h is or . A seed is chosen uniformly at random for each member i, it is encrypted to produce Shi using the same set of keys (as assumed for this case), and the randomness of the encryption is saved as Rhi . Ciphertexts Chi are produced for all i G\{, } using the PRNG with the seed generated for i. The ciphertext Ch is chosen randomly, and Ch is chosen such that the XOR of all ciphertexts yields m0 . The descriptor is then created from the encrypted seeds, hashes of the ciphertexts, and the length of m0 . To emphasize that the creation of the descriptor depends on the message rather than its owner, we use the additional notation of sm0 i for the seeds, Rm0 i for the encryption randomness, Cm0 i for the ciphertexts, and dm0 for the descriptor. The descriptor for the challenge member assigned m1 is similarly generated, and we use similar user-independent notation for it and its components. Thus, for specic dm0 and dm1 , the probability that d = dm0 and d = dm1 when b = 0 is the same as the probability that d = dm1 and d = dm0 when b = 1. We thus let the former occur in the execution under consideration for b = 0 and the latter occur in the execution for b = 1. Case 2: Some honest member h received an invalid key or non-matching keys in the 1 = TRUE as an input to C 2 and thus cause previous rounds. In this case, C 7 will use fh 7 the shufe to fail. If Z1 = 0, the challenger has guessed wrong, and the challenger will 7 = 1, and so the descriptors of and fail. Assuming the challenger does not fail, Z1 are never needed (the dummy message is preserved throughout the shufe). Thus we assume that C 7 does not create them at all. Member h H \{, } creates her descriptor dh in a way that only depends on her input message and the keys she received in the previous rounds. It is shown above that neither of these depends on b, and so her descriptor does not depend on b. Phase 3:
1 for the shufe in this phase based on keys received in Each h H sets the fail ag fh previous rounds, and thus it is independent of b by the above.

57

1 C 7 calls C 2 . The inputs to C 2 are challenge users and , challenge messages mc 0 = c1 1 dm0 and m1 = dm1 , non-challenge messages mh = dh for h H \{, }, round 1 , and challenge bit b. As number nR1 , signing keys K , member ordering , fail ags fh 2 shown above, all of the inputs to C except b are independent of b. Thus with I set to all those inputs except b we can apply Lemma 12. We conclude that C 7 fails in this step with probability independent of b, that the messages sent are independent of b, and that the output O1 is independent of b.

The message h3 = {p , nR , 3, h}SIGuh from h H contains evidence of invalid or non-matching keys if any are received. Thus it depends only on messages received in previous rounds and is independent of b by the above. The additional inputs to A since his last output are messages h3 , h H , shown above to be independent of b. Thus the messages i3 , i D, received by h H are independent of b. The messages h3 , h H , received by h H are shown above to be independent of b. Phase 4: For each member h H , we consider two cases for the message she sends. Which case 1 . O 1 is shown above to be independent of b, applies depends on the shufe output Oh h and so the relevant case is independent of b.
1 = ( FAILURE , BLAME s1 , s1 ). h sends message Case 1: Oh h h s1 1 h4 = {FALSE, BLAMEs h , h , nR , 4, h} SIG uh , which is independent of b by the above. 1 = ( SUCCESS , M s1 ). h sends message Case 2 Oh h h4 = {TRUE, C(1)h , . . . , C(N )h , nR , 4, h}SIGuh . For h H \{, }, C(i)h is computed from the descriptors and keys received in earlier rounds, which are shown above to be independent of b. For h {, }, h uses as its ciphertext the value Cm0 h generated in Phase 2 for descriptors containing the encryption of a seed matching the seed that is encrypted in dm0 . h does similarly for descriptors with seeds matching the one in dm1 . Otherwise, h computes ciphertexts C(i)h from the descriptors and keys received in earlier rounds. Cm0 h and Cm1 h are created above independently of b, and the previous messages received by h are shown above to be independent of b. Thus, the message h4 from h is independent of b.

The additional inputs to A since his last output are messages h4 , h H , shown above to be independent of b. Thus the messages i4 , i D, received by h H are independent of b. The messages h4 , h H , received by h H are shown above to be independent of b. Phase 5: The message h5 = {Vh , nR , 5, h}SIGuh sent by h H depends on the descriptors di obtained as an output of the shufe, on GOi received from each member i, and on the ciphertexts Cij received from each member i. These messages and outputs are shown above to be independent of b, and thus h5 is independent of b as well.

58

 The additional inputs to A since his last output are messages h5 , h H , shown above to be independent of b. Thus the messages i5 , i D, received by h H are independent of b. The messages h5 , h H , received by h H are shown above to be independent of b. Phase 6: Member h H creates message mi using the GOj and the ciphertexts Cij received from each member j . Each of these is shown above to be independent of b, and so mi is also independent of b. Phase 7:
2 for the shufe in this phase based on ciphertexts Each h H sets the fail ag fh received in the messages j 4 and j 5 from every j . These messages are shown above to 2 is independent of b. be independent of b, and thus each fh

C 7 calls C 2 . The inputs to C 2 from C 7 are challenge users and , challenge c2 2 2 messages mc 0 and m1 (to be specied), non-challenge messages mh = Ah for h 2 , and H \{, }, round number nR2 , signing keys K , member ordering , fail ags fh 2 challenge bit b. We observe here that , , nR2 , K , , and the fh are shown above to be independent of b. We consider two separate cases for the blame shufe in order to show that all failures, messages, and outputs of the shufe are independent of b. Which case 2 and thus is independent of b. applies depends only on the fh
2 = FALSE for all h H . Case 1: fh c2 2 It is shown above that all inputs to C 2 are independent of b except mc 0 , m1 , 2 mh = Ah , h H \{, }, and b itself. Each accusation Ah , h H \{, }, 1 and the contents of the depends on the descriptor dh , the shufe output Oh j4 received by h from all j . These are shown above to be independent of b, and so Ah is independent of b as well. We claim that the accusation Am0 created by the member h0 {, } that is assigned m0 is created the same regardless of h0 . After showing this, we will be able to apply Lemma 12 to prove the anonymity of the shufe. Am0 depends on 1 , V , and d . Oh h0 h0 0 1 = ( FAILURE , BLAME s1 , s1 ) for some h {, }, then neither nor If Oh h h creates an accusation, and Am0 = 0a regardless of h0 . 1 = ( SUCCESS , M s1 ) for all h {, }. We observe that, Now suppose that Oh h although C 2 does not strictly execute ANONYMIZE - S, after Phase 3 of the shufe that challenger does simply execute ANONYMIZE - S for each h H , assuming that he does not fail. If C 2 had failed during the descriptor shufe, of course, we would not have reached this phase, and therefore we can assume that he did not. In addition, the outcome is the same as if the entire GMP - SHUFFLE had been run 2 = FALSE by assumption and the parameters K , , and n because all fh R1 used for ANONYMIZE - S are generated by SETUP - B in the same way that SETUP - S generates them. Thus, we observe that the proof of Lemma 2 applies to the descriptor shufe. We are therefore guaranteed that the outputs (SUCCESS, Mhs1 ), h {, }, are 1 = ( SUCCESS , M s1 ) = O 1 . identical. We can then assume that O If receives a j 4 with GOj = FALSE, then must as well. Otherwise, the equivocation would have been discovered and the shufe deliberately failed by all honest

59

members, contradicting our assumption for this case. The accusation for both members in this case is empty, and so we can say that Am0 = 0a regardless of h0 . If and receive GOj = TRUE in all j 4 , then any incorrect ciphertexts receives in j 4 must also be received by . Otherwise, again, all honest users would have noticed the equivocation and caused the blame shufe to fail, contradicting the case assumption. Thus, because and have the same sequence of descriptors, and because equality of hashes implies equality of the preimages by second-preimage resistance, we can conclude that and must receive all the same Cij . As stated 1 and the GO and C contained above, accusation Am0 depends only on dm0 , Oh j ij 0 in each j 4 received by h0 . We have shown that in this case all of these are equal for and , and thus Am0 is indeed created the same regardless of h0 . The above arguments apply to the accusation Am1 created by the user h1 {, } c2 2 that is assigned m1 . Therefore, with mc 0 = Am0 , m1 = Am1 , and I as the set of all inputs from C 7 to C 2 except b, we can apply Lemma 12. We conclude that C 2 fails during the blame shufe with probability independent of b, that the messages sent to A are independent of b, and that the output O2 is independent of b. 2 = 1 for some h H . Case 2: fh In this case, we simply view C 7 as calling C 2 with Ah = h for all h H . Because the shufe will fail, the challenger will fail if Z 2 is set to 0. Otherwise, Z 2 = 1, and the shufe effectively uses h as the input message for each h H . In this case, b has no effect on the messages of each user and therefore no effect on the shufe. Thus, C 2 fails during the blame shufe with probability independent of b, the messages sent to A during the shufe are independent of b, and the shufe output O2 is independent of b. 2 and the messages The message h7 = {p , nR , 7, h}SIGuh sent by h H depends on fh i5 and i4 received by h. These are shown above to be independent of b, and thus h7 is independent of b as well. The additional inputs to A since his last output are messages sent during the blame shufe and h7 , h H , all of which are shown above to be independent of b. Thus the messages i7 , i D, received by h H are independent of b. The messages h7 , h H , received by h H are shown above to be independent of b. For each h H , SUCCESSh and BLAMEh are set differently in several different cases. 2 and , which are shown above to be independent Which case applies depends on Oh h5 of b. Thus which case is applied is also independent of b. For each case, SUCCESSh 2 and BLAMEh depend at most on BLAMEs h ; on the messages i3 , i4 , and i7 sent and 2 ; and on the descriptor-shufe output O 1 . received by h; on the blame-shufe output Oh h These are all shown above to be independent of b, and thus SUCCESSh and BLAMEh are independent of b as well. Output messages Mh , h H , are created depending on SUCCESSh and the messages i4 sent and received by h. These are shown above to be independent of b, and thus Mh is independent of b as well. Log h , h H , depends on SUCCESSh , the output of SETUP - B, all messages sent and 1 and O 2 . These are all shown above to be received by h, and the shufe outputs Oh h independent of b, and thus h is independent of b as well. 60

 The output Oh of GMP - BULK, h H , depends on SUCCESSh , Mh , BLAMEh , and k . These are shown above to be independent of b, and thus Oh is independent of b as well. We have thus shown that, given input I = i, for every execution of C 7 when b = 0 there is an execution when b = 1 that occurs with the same probability and for which (i) F 7 is the same, (ii) M is the same, and (iii) O is the same. Lemma 21. (G7 ) = 0. Proof. To prove this, we show that the steps of the anonymity game surrounding the challenge run are independent of b and use the previous lemma for the challenge run itself. 1. In Step 1, pre-challenge rounds of the bulk protocol are executed, which do not depend on b. 2. In Step 2, A sends C 7 the challenge participants and , the challenge messages mc 0 and c m1 , and the non-challenge messages mh , h H \{, }, which must be independent of b because all previous inputs to A were shown above to be independent of b. 3. Step 3 of the anonymity game is for the challenger to assign the messages of the challenge users according to b. However, we leave these variables undened, as we have modied the challenger to create Game 7 such that they are not necessary. 4. The challenge run is executed during Step 4. We observe that C 7 rst executes SETUP - B. This protocol takes only the long-term signing keys as input, and therefore its output (nR , nR1 , nR2 , K, ) is independent of b. Next C 7 calls C 7 with inputs b and c I = (nR , nR1 , nR2 , K, , , , mc 0 , m1 , {mh }hH \{, } ). I has been shown to be independent of b. Therefore, by applying Lemma 20, we can conclude that C 7 fails independently of b, and if it does not fail any messages M to A and outputs O are also independent of b. 5. In Step 5, the challenger executes further rounds of the protocol. The adversarys inputs up to this point have been shown to be independent of b, and thus these executions do not depend on b. 6. In Step 6, A outputs guess b. All inputs to the adversary have been shown to be independent of b, and thus b is independent of b. The game output G7 (b) only depends on F 7 and b. These have both been shown to be independent of b, and therefore P r[G7 (1) = 1] = P r[G7 (0) = 1].

Taken together, the preceding lemmas show that the adversary has a negligible advantage in the anonymity game: Theorem 6. The GMP - BULK protocol maintains anonymity with k colluding members for any 0 k N 2. Proof. Let A be a probabilistic polynomial-time adversary. We denote the change in advantage between games i and j as ij = (Gj ) (Gi ) . Using Lemmas 14 and 16, the advantage of A in the anonymity game with GMP - BULK is at most 2 02 + 2 35 + 56 + 67 + (G7 ) . By Lemma 21 this is 2 02 + 4 35 + 4 56 + 4 67 . This quantity is negligible by Lemmas 15, 17, 18, and 19. 61

Related Work

DISSENT s shufe protocol builds directly on an anonymous data collection protocol by Brickell and Shmatikov (Brickell and Shmatikov 2006b), adding DoS resistance via new go/no-go and blame phases. DISSENTs bulk protocol is similarly inspired by DC-nets (Chaum 1988), which are computationally efcient and provide unconditional anonymity. DC-nets traditionally require nondeterministic reservation schemes to allocate the anonymous channels communication bandwidth, however, and are difcult to protect against anonymous DoS attacks by malicious group members. Strategies exist to strengthen DC-nets against DoS attacks (Waidner and Ptzmann 1989; Golle and Juels 2004), or to form new groups when an attack is detected (Sirer et al. 2004). DIS SENTs use of a shufe protocol to set up a deterministic DC-nets instance, however, cleanly avoids these DoS vulnerabilities while providing the additional guarantee that each member sends exactly one message per protocol run, a useful property for holding votes or assigning 1-to-1 pseudonyms. Mix networks (Chaum 1981) offer high-latency but practical anonymous communication, and can be adapted to group broadcast (Perng, Reiter, and Wang 2006). Unfortunately, for many mixnetwork designs, anonymity is vulnerable to trafc analysis (Serjantov, Dingledine, and Syverson 2003) and performance is vulnerable to DoS attacks (Dingledine and Syverson 2002; Iwanik, Klonowski, and Kutylowski 2004). Cryptographically-veriable mixes (Neff 2001; Furukawa and Sako 2001; Adida 2006) are a possible solution to DoS attacks and a potential replacement for our shufe protocol. These algorithms require exotic and complex cryptography, however, bringing efciency costs and implementation and verication challenges. Low-latency designs can provide fast and efcient communication supporting a wide variety of applications, but they typically provide much weaker anonymity than DISSENT. For example, onion routing (Goldschlag, Reed, and Syverson 1999; Dingledine, Mathewson, and Syverson 2004), a well-known and practical approach to general anonymous communication on the Internet, is vulnerable to trafc analysis by adversaries who can observe streams going into and out of the network (Syverson, Tsudik, Reed, and Landwehr 2000). Similarly, Crowds (Reiter and Rubin 1999) is vulnerable to statistical trafc analysis when an attacker can monitor many points across the network. Herbivore (Goel, Robson, Polte, and Sirer 2003) provides unconditional anonymity, but only within a small subgroup of the total group of participants. k -anonymous transmission protocols (von Ahn, Bortz, and Hopper 2003) provide anonymity only when most members of a group are honest. We thus observe a tradeoff between security, efciency, and possible applications. Furthermore, many cryptographic attacks have been discovered against specic anonymity protocols. These protocols are often complex and contain subtle aws in design, security proofs, or security denitions. For example, many attacks have been identied against mix-network schemes, some against schemes that offered proofs of security. A simple yet powerful attack against one scheme (Park, Itoh, and Kurosawa 1994) trivially breaks an honest members anonymity if an attacker can create a ciphertext related to that members ciphertext (Ptzmann 1994; Ptzmann and Pzmann 1990). An attack on the integrity of a scheme claimed to be probably secure (Jakobsson 1998) was given by Mitomo and Kurosawa (2000). A corrupted mix server can alter intermediate ciphertexts, affecting the corresponding output messages, without being detected. Several attacks on the anonymity and robustness of another scheme (Golle, Zhong, Boneh, Jakobsson, and Juels 2002) claimed secure were presented by Wikstr om (2003). These attacks exploited previously identied (Ptzmann 1994; Ptzmann and Pzmann 1990; Desmedt and Kurosawa 2000) general design aws as well

62

as the ability of mix servers to use incorrect and specially-prepared inputs. Abe and Imai (2003) described two anonymity attacks on mix-net designs (Jakobsson and Juels 2001; Golle, Zhong, Boneh, Jakobsson, and Juels 2002), possible when members collude with a server and even with completely-honest mix servers. Later, the authors pointed out (Abe and Imai 2006) that some aws are related to weak security denitions. Even newly proposed schemes still succumb to previous attacks. A recent work of Khazaei, Terelius, and Wikstr om (2012) points out aws in the design of Allepuz and Castello (2010) that facilitate attacks against anonymity and integrity, some of which are based on previously-described attacks (Ptzmann 1994). These attacks show that obtaining a provably secure anonymous communication protocol is a surprisingly complex task. It requires a considerable amount of effort and careful attention to every design detail of a protocol. Indeed, only relatively recently has a framework for rigorous security proofs been available for mix networks (Wikstr om 2004).

Conclusion and Future Work

DISSENT is a novel, provably secure protocol for anonymous and accountable group communication. DISSENT allows a well-dened group of participants to exchange variable-length messages anonymously, while resisting the trafc analysis and anonymous DoS attacks effective against mixnetworks, DC-nets, and onion routing. DISSENT improves upon previous shufed-send primitives by adding accountabilitythe ability to trace misbehaving nodesand by eliminating the message padding requirements of earlier schemes. DISSENT guarantees anonymity, integrity, and accountability, and has been shown practical for anonymous communication within moderate-size groups. We have presented an improved version of this protocol that xes several aws in the original design. We have precisely dened its security properties and provided detailed security proofs. Future work includes exploring ways to achieve scalability in order to accommodate large groups, as well as interactivity to make DISSENT suitable for latency-sensitive applications.

APPENDIX
Here we describe in more detail some of the security aws discovered in the DISSENT protocol of Corrigan-Gibbs and Ford (2010). Flaws were discovered affecting each of the desired security criteria: integrity, anonymity, and accountability. We also briey mention the technique we adopted to x each problem. By following a rigorous proof methodology for the improved protocol, we can have high condence that these xes have not not introduced problems of their own. Note that the terminology and notation used here is that of Corrigan-Gibbs and Ford (2010).

Anonymity
Ciphertext replay attack in shufe Flaw: The adversary can replay a ciphertext Ci of some user i from an earlier run of the shufe by submitting Ci as his own ciphertext. Then the adversary looks for the inner ciphertext Ci that appeared at the end of the anonymization phase (Phase 3) in both this run and the earlier run. The adversary can conclude that the message contained in that inner ciphertext, which was successfully decrypted in the earlier run, were sent by i. 63

Fix: New outer encryption keys are generated in each run of the shufe. Message descriptor replay attack in the bulk protocol Flaw: The adversary can replay the message descriptor di of some user i received in an earlier run of the bulk protocol by submitting it as his own descriptor. di contains an encrypted seed for i that does not generate a ciphertext with a hash matching the included hash. In the previous run, user i was looking for a slot with descriptor matching di and used a precomputed ciphertext for it instead of using the included seed. In this run, i is not looking for it, and because the hash of the ciphertext wont match the one included in di , i will send an empty ciphertext. This identies i as the owner of the message revealed during the slot containing di in the previous run. Fix: New encryption keys for the seeds in the message descriptors are generated in each run of the bulk protocol. Ciphertext equivocation attack in the bulk protocol Flaw: The adversary can target user i as the suspected owner of a slot (j ) by sending an jk to i in Phase 3 and sending correct ciphertexts to all other members. incorrect ciphertext C Then if a valid accusation comes out of the blame phase (Phase 5), i must be the owner of the slot, that is, i = j . Fix: Rebroadcast the ciphertexts before the blame shufe, and then have users that observe ciphertext equivocation break the blame shufe and then send evidence of equivocation to exonerate themselves and expose the equivocation member. Adversary copies encrypted seeds during the bulk protocol Flaw: An adversary in the last position of the shufe can copy the ciphertext containing a message descriptor into his own slot. An honest member only looks for one message descriptor matching her own, and therefore the owner of the copied descriptor will use the encrypted seed in the second slot containing her descriptor, the ciphertext wont match the hash, and so she will send an empty ciphertext. This identies herself as the owner of the slot containing the rst copy of the descriptor, which does have its message revealed. Relatedly, it appears technically possible for an adversary to create a wholly new descriptor that contains the encrypted seed that a slot owner creates for herself in her own descriptor. IND-CCA2 doesnt appear to have a type of non-malleability that would prevent this kind of copying. Thus simply looking for all copies of a members descriptor isnt enough, as the adversary could potentially target a member by copying out her encrypted seed from her encrypted message descriptor into a totally different descriptor. The member who uses different ciphertexts for the same seeds is the owner of the (original non-modied) descriptors. Fix: Have members look for all copies of their encrypted seed, and use the same precomputed ciphertext in each of those slots.

Accountability
Ciphertext duplication attack in the shufe

64

Flaw: An adversary in the rst position of shufe can use as his own ciphertext submission the ciphertext that an honest member submits into the shufe. The shufe fails when duplicate ciphertexts are observed, and both the honest and dishonest members are exposed. This violates accountability, which prohibits exposing honest members. Fix: Members must rst commit publicly to their ciphertext submission using non-malleable commitments and including their identity (e.g. their shufe position) in the commitment. Equivocation in proceeding to blame in the shufe Flaw: If all GOi = TRUE in the verication phase (Phase 4), but dishonest j pretends to honest k that j received GOi = FALSE from i by only sending blame data in the last phase (i.e. executing Phase 5b), while sending his private key wj to all other members (i.e. executing Phase 5a with respect to them), then it is not clear if liveness assumption implies that k can eventually get enough blame data from the other members (who see everything go correctly, proceed to Phase 5a, and nish the protocol) to expose a faulty member. Fix: The key release and blame phases (Phase 5a and 5b) are now unconditionally run in sequence. A member must justify in the blame phase not sending out aprivate key in the key-release phase with enough evidence to expose another member.

Integrity
Ciphertext equivocation attack in the bulk protocol Flaw: The adversary can send a bad ciphertext to just one member, who, if not the owner, will never receive a valid accusation and so will complete successfully without all honest members messages. Fix: As described earlier as the x to an anonymity attack, we rebroadcast the ciphertexts before the blame shufe, and then we have users that observe ciphertext equivocation break the blame shufe and then send evidence of equivocation to exonerate themselves and expose the equivocating member.

References
Abe, M. and H. Imai (2003). Flaws in some robust optimistic mix-nets. In ACISP. Abe, M. and H. Imai (2006). Flaws in robust optimistic mix-nets and stronger security notions. IEICE Trans. Fundam. Electron. Commun. Comput. Sci.. Adida, B. (2006). Advances in cryptographic voting systems. Ph. D. thesis, Cambridge, MA, USA. Allepuz, J. P. and S. G. Castello (2010). Universally veriable efcient re-encryption mixnet. In Electronic Voting. GI. Bellare, M., A. Desai, D. Pointcheval, and P. Rogaway (1998). Relations among notions of security for public-key encryption schemes. Advances in Cryptology CRYPTO 98. Brickell, J. and V. Shmatikov (2006a). Efcient anonymity-preserving data collection. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 65

Brickell, J. and V. Shmatikov (2006b). Efcient anonymity-preserving data collection. Castro, M. and B. Liskov (1999, February). Practical byzantine fault tolerance. In OSDI. Chaum, D. (1981, February). Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM . Chaum, D. (1988, January). The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology. Clarke, I., O. Sandberg, B. Wiley, and T. W. Hong (2000, July). Freenet: A distributed anonymous information storage and retrieval system. In Workshop on Design Issues in Anonymity and Unobservability. Corrigan-Gibbs, H. and B. Ford (2010). Dissent: Accountable anonymous group messaging. In Proceedings of the 17th ACM Conference on Computer and Communications Security. Davenport, D. (2002, April). Anonymity on the Internet: why the price may be too high. Communications of the ACM 45(4), 3335. Desmedt, Y. and K. Kurosawa (2000). How to break a practical mix and design a new one. In EUROCRYPT. Dingledine, R., N. Mathewson, and P. Syverson (2004). Tor: the second-generation onion router. In SSYM04: Proceedings of the 13th conference on USENIX Security Symposium. Dingledine, R. and P. Syverson (2002, March). Reliable MIX cascade networks through reputation. In Financial Cryptography. Dolev, D., C. Dwork, and M. Naor (2000). Nonmalleable cryptography. SIAM J. Comput.. Douceur, J. R. (2002, March). The Sybil attack. In 1st International Workshop on Peer-to-Peer Systems. Furukawa, J. and K. Sako (2001, August). An efcient scheme for proving a shufe. In CRYPTO. Goel, S., M. Robson, M. Polte, and E. G. Sirer (2003, February). Herbivore: A Scalable and Efcient Protocol for Anonymous Communication. Technical Report 2003-1890, Cornell University. Goldschlag, D., M. Reed, and P. Syverson (1999, February). Onion routing for anonymous and private internet connections. Communications of the ACM 42(2), 3941. Goldwasser, S., S. Micali, and R. L. Rivest (1995). A digital signature scheme secure against adaptive chosen-message attacks. Golle, P. and A. Juels (2004, May). Dining cryptographers revisited. Eurocrypt. Golle, P., S. Zhong, D. Boneh, M. Jakobsson, and A. Juels (2002). Optimistic mixing for exitpolls. In Asiacrypt 2002, LNCS 2501. Haeberlen, A., P. Kouznetsov, and P. Druschel (2007, October). PeerReview: Practical accountability for distributed systems. In 21st SOSP. Iwanik, J., M. Klonowski, and M. Kutylowski (2004, September). DUO-Onions and HydraOnions failure and adversary resistant onion protocols. In IFIP CMS. Jakobsson, M. (1998). Flash mixing. EUROCRYPT.

66

Jakobsson, M. and A. Juels (2001). An optimally robust hybrid mix network. In In Principles of Distributed Computing - PODC 01. Khazaei, S., B. Terelius, and D. Wikstr om (2012). Cryptanalysis of a universally veriable efcient re-encryption mixnet. In International conference on Electronic Voting Technology/Workshop on Trustworthy Elections. Lamport, L. (1998). The part-time parliament. TOCS. Mitomo, M. and K. Kurosawa (2000). Attack for ash MIX. In In Advances in Cryptology ASIACRYPT 2000, LNCS, pp. 192204. Springer-Verlag. Neff, C. A. (2001, November). A veriable secret shufe and its application to e-voting. In ACM CCS. Park, C., K. Itoh, and K. Kurosawa (1994). Efcient anonymous channel and all/nothing election scheme. In EUROCRYPT. Perng, G., M. Reiter, and C. Wang (2006). M2: Multicasting mixes for efcient and anonymous communication. In 26th ICDCS, pp. 5959. Ptzmann, B. (1994). Breaking an efcient anonymous channel. In EUROCRYPT. Ptzmann, B. and A. Pzmann (1990). How to break the direct RSA-implementation of mixes. In EUROCRYPT. Reiter, M. K. and A. D. Rubin (1999). Anonymous web transactions with crowds. Communications of the ACM 42(2), 3248. Rogaway, P. and T. Shrimpton (2004). Cryptographic hash-function basics: Denitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In Fast Software Encryption - FSE04. Serjantov, A., R. Dingledine, and P. Syverson (2003). From a trickle to a ood: Active attacks on several mix types. Information Hiding. Sirer, E. G. et al. (2004, September). Eluding carnivores: File sharing with strong anonymity. In ACM SIGOPS EW. Stein, E. (2003). Queers anonymous: Lesbians, gay men, free speech, and cyberspace. Harvard Civil Rights-Civil Liberties Law Review. Stinson, D. R. (2005). Cryptography: Theory and Practice, Third Edition (Discrete Mathematics and Its Applications). Chapman & Hall/CRC. Stone, B. and M. Richtel (2007). The hand that controls the sock puppet could get slapped. New York Times. Syverson, P., G. Tsudik, M. Reed, and C. Landwehr (2000, July). Towards an Analysis of Onion Routing Security. In Design Issues in Anonymity and Unobservability. Teich, A., M. S. Frankel, R. Kling, and Y. Lee (1999, May). Anonymous communication policies for the Internet: Results and recommendations of the AAAS conference. Information Society. von Ahn, L., A. Bortz, and N. J. Hopper (2003). k-anonymous message transmission. In 10th CCS.

67

Waidner, M. and B. Ptzmann (1989, April). The dining cryptographers in the disco: Unconditional sender and recipient untraceability with computationally secure serviceability. In Eurocrypt. Wallace, J. D. (1999, December). Nameless in cyberspace: Anonymity on the internet. Cato Brieng Paper No. 54. Wikstr om, D. (2003). Five practical attacks for optimistic mixing for exit-polls. In Selected Areas in Cryptography. Wikstr om, D. (2004). A universally composable mix-net. In TCC. Yale Law Journal (1961, June). The constitutional right to anonymity: Free speech, disclosure and the devil. Yale Law Journal 70(7), 10841128.

68