# Proactively Accountable Anonymous Messaging in Verdict - 2013

###### tags: `Tag(HashCloak - DC Net Readings)`
Authors: Henry Corrigan-Gibbs, David Isaac Wolinsky, Bryan Ford

Paper: https://dedis.cs.yale.edu/dissent/papers/verdict-tr.pdf

Definitions:

### Table of Contents
[toc]

:::info
>Abstract: Among anonymity systems, DC-nets have long held attraction for their resistance to traffic analysis attacks, but practical implementations remain vulnerable to internal disruption or “jamming” attacks, which require timeconsuming detection procedures to resolve.

We present Verdict, the first practical anonymous group communication system built using proactively verifiable DC-nets: participants use public-key cryptography to construct DC-net ciphertexts, and use zero-knowledge proofs of knowledge to detect and exclude misbehavior before disruption. We compare three alternative constructions for verifiable DC-nets: one using bilinear maps and two based on simpler ElGamal encryption. While verifiable DC-nets incur higher computational overheads due to the public-key cryptography involved, our experiments suggest that Verdict is practical for anonymous group messaging or microblogging applications, supporting groups of 100 clients at 1 second per round or 1000 clients at 10 seconds per round. Furthermore, we show how existing symmetric-key DC-nets can “fall back” to a verifiable DC-net to quickly identify misbehavior, speeding up previous detections schemes by two orders of magnitude.
:::

## Ch 1: Introduction
> A right to anonymity is fundamental to democratic culture, freedom of speech [3, 48], peaceful resistance to repression [41], and protecting minority rights [47].

Dining cryptographers networks [13] (DC-nets) promise security even against traffic analysis attacks, and recent systems such as Herbivore [26, 46] and Dissent [15, 54] have improved the scalability of DC-netstyle systems. However, these systems are still vulnerable to internal disruption attacks in which a misbehaving member anonymously “jams” communication, either completely or selectively.

Dissent includes a retrospective blame procedure that can eventually exclude disruptors, but at high cost:
* tracing a disruptor in a 1,000- member group takes over 60 minutes [54], and the protocol makes no communication progress until it restarts “from scratch.”
* An adversary who infiltrates such a group with f colluding members can “sacrifice” them one at a time to disrupt all communication for f contiguous hours at any time—long enough time to cause a communications blackout before or during an important mass protest, for example.

Verdict, a novel but practical group anonymity system, thwarts such disruptions while maintaining DCnets’ resistance to traffic analysis.
* At Verdict’s core lies a verifiable DC-net primitive, derived from theoretical work proposed and formalized by Golle and Juels [27], which requires participating nodes to prove proactively the well-formedness of messages they send.
* The first working system we are aware of to implement verifiable DC-nets

Verdict supports three alternative schemes for comparison: a pairing scheme using bilinear maps similar to the Golle-Juels approach, and two schemes based on ElGamal encryption in conventional integer or elliptic curve groups.

Verdict incorporates this verifiable core into a client/server architecture like Dissent’s [54], to achieve scalability and robustness to client churn.

> As in Dissent, Verdict maintains security as long as at least one of the participating servers is honest, and participants need not know or guess which servers are honest.

Due to their reliance on public-key cryptography, verifiable DC-nets incur higher computation overheads than traditional DC-nets, which primarily use symmetric-key cryptography (e.g., AES). We expect this CPU cost to be acceptable in applications where messages are usually short (e.g., chat or microblogging), where costs are dominated by network delays, or in groups with relatively open or antagonistic membership where disruption risks may be high.

Under realistic conditions, we find that Verdict can support groups of 100 users while maintaining 1-second messaging latencies, or 1000-user groups with 10-second latencies. In a trace-driven evaluation of full-system performance for a microblogging application, Verdict is able to keep up with symmetric-key DCnets in groups of up to 250 active users.

In contrast with the above “purist” approach, which uses expensive public-key cryptography to construct all DC-net ciphertexts, Verdict also implements and evaluates a hybrid approach that uses symmetric-key DC-nets for data communication when not under disruption attack, but leverages verifiable DC-nets to enable the system to respond much more quickly and inexpensively to disruption attacks.

Dissent uses a verifiable shuffle [38] to broadcast an accusation anonymously; this shuffle dominates the cost of identifying disruptors. By replacing this verifiable shuffle with a verifiable DC-nets round, Verdict preserves the disruption-free performance of symmetric-key DC-nets, but reduces the time to identify a disruptor in a 1000-node group by two orders of magnitude, from 20 minutes to 26 seconds.

This paper’s primary contributions are:
* The first working implementation and experimental evaluation of verifiable DC-nets in a practical anonymous communication system.
* Two novel verifiable DC-nets constructions using standard modular integer and elliptic curve groups, offering an order of magnitude lower computational cost than the original pairing approach [27]
* A hybrid system design that preserves performance of symmetric-key DC-nets, while reducing disruption resolution costs by two orders of magnitude, and
* Experimental evidence suggesting that verifiable DCnets may be practical for realistic applications, such as anonymous microblogging.

## 2 Background and Motivation

### 2.1 Anonymity with Strong Adversaries
A number of political journalists could form a Verdict communication group. Any participating journalist may then anonymously broadcast the documents to the entire group of journalists, such that no member of the group can determine which journalist sent the documents. Even if a government agency plants agents within a group of journalists and observes all network traffic during a protocol run, the agency remains unable to learn the source of the leak.

Existing systems such as Tor, which are practical and scalable but vulnerable to known traffic analysis attacks [17, 19, 34], cannot guarantee security in this context.

> For example, if a US journalist posts a leak to a US website, via a Tor connection whose entry and exit relays are in Europe, then an eavesdropper capable of monitoring transatlantic links [33] can de-anonymize the user via traffic analysis [19, 37]. Prior anonymity systems attempting to offer resistance to traffic analysis, discussed in Section 7, suffer from poor performance or vulnerability to active denial-of-service attacks.

### 2.2 DC-nets Overview
> DC-nets \[13\] provide anonymous broadcast within a group of participants, who communicate lock-step in a series of rounds.

In a given round, each group member contributes an equal length ciphertext that, when combined with all other members’ ciphertexts, reveals one or more cleartext messages. All group members know that each message was sent by some group member—but do not know which member sent each message.


* In its simplest form, illustrated in Figure 1, we assume one group member wishes to broadcast a 1-bit message anonymously.
* To do so, every pair of members flips a coin, secretly agreeing on the random outcome of that coin flip.
* An N-member group thus flips N(N − 1)/2 coins in total, of which each member observes the outcome of N − 1 coins.
* Each member then XORs together the values of the N − 1 coins she observes, additionally the member who wishes to broadcast the 1-bit message XORs in the value of that message, to produce that member’s DC-nets ciphertext.
* Each group member then broadcasts her 1-bit ciphertext to the other members.
* Finally, each member collects and XORs all N members’ ciphertexts together.

Since the value of each shared coin is XORed into exactly two members’ ciphertexts, all the coins cancel out, leaving only the anonymous message, while provably revealing no information about which group member sent the message.

### 2.3 Practical Generalizations

As a standard generalization of DC-nets to communicate L-bit messages, all members in principle simply run L instances of the protocol in parallel.
* Each pair of members flips and agrees upon L shared coins, and each member XORs together the L-bit strings she observes with her optional L-bit anonymous message to produce L-bit ciphertexts, which XOR together to reveal the L-bit message.
* For efficiency, in practice each pair of group members forms a cryptographic shared secret—via DiffieHellman key agreement, for example—then group members use a cryptographic pseudo-random number generator (PRNG) to produce the L-bit strings.

As a complementary generalization, we can use any finite alphabet or group in place of coins or bits, as long as we have:
* a suitable combining operator analogous to XOR
* a way to encode messages in the chosen alphabet
* and a way to generate complementary pairs of one-time pads in the alphabet that cancel under the chosen combining operator.

For example, the alphabet might be 8-bit bytes, the combining operator might be addition modulo 256, and from each pairwise shared secret, one member of the pair generates bytes $B_1$,...,$B_k$ from a PRNG, while the other member generates corresponding two’s complement bytes $−B_1$,...,$−B_k$.

### 2.4 Disruption and Verifiable DC-nets
> A key weakness of DC-nets is that a single malicious insider can easily block all communication. An attacker who transmits arbitrary bits—instead of the XORed ciphertext that the protocol prescribes—unilaterally and anonymously jams all DC-net communication.

Even in a system like Dissent that can eventually trace and exclude disruptors, an adversary with multiple colluding dishonest group members may still be able to slow or halt communication for long enough to ruin the service’s usability for honest participants. If the group’s membership is open enough to allow new disruptive members to join more quickly than the tracing process operates, then these infiltrators may be able to shut down communication permanently.

Verifiable DC-nets \[27\] leverage algebraic groups, such as elliptic curve groups, as the DC-nets alphabet. Using such groups allows for disruption resistance, by enabling members to prove the correctness of their ciphertexts’ construction without compromising the secrecy of the shared pseudo-random seeds.

> Using a hybrid approach that combines a traditional DC-net with a verifiable DC-net, Verdict can achieve the messaging latency of a traditional XOR-based DC-net while providing the strong disruption-resistance of verifiable DC-nets.

## 3 Verdict Architecture Overview
> In this section, we describe the individual components of Verdict and how they combine to form the overall anonymous communication system.

### 3.1 Deployment and Adversary Model
> Verdict builds on Dissent \[53, 54\] and uses the multiprovider cloud model illustrated in Figure 2 (a) to achieve scalability and resilience to ordinary node and link failures.

In this model, a communication group consists of mostly unreliable clients, and a few servers we assume to be highly available and wellprovisioned. Servers in a group should be administered independently—each furnished by a different anonymity provider, for example—to limit risk of all servers being compromised and colluding against the clients. The servers may be geographically or topologically close, however—possibly even hosted in the same data center, in locked cages physically and administratively accessible only to separate, independent authorities.
> Personal Note: Seems to follow what would be expected of different client teams (in ETH2.0.

Clients directly communicate, at a minimum, with a single upstream server, while each server communicates with all other servers. This topology, shown in Figure 2 (b), reduces the communication and computation burden on the clients, and enables the system to make progress regardless of client churn.

To ensure anonymity, clients need not assume that any particular server is trustworthy—a client need not even trust its immediately upstream server. Instead, clients trust only that there exists at least one one honest server, an assumption previously dubbed anytrust \[53, 54\], as a trust analog to anycast communication.

Verdict, like Dissent, achieves security under the anytrust assumption through the DC-nets key-sharing model shown in Figure 2 (c). Each client shares a secret with every server, rendering client ciphertexts indecipherable without the cooperation of all servers, and hence protecting a client’s anonymity even if its immediately upstream server is malicious


### 3.2 Security Goals
> Verdict’s goal is to offer anonymity and disruption resistance in the face of a strong adversary who can potentially monitor all network links, modify packets as they traverse the network, and compromise a potentially large fraction of a group’s participating members.

We say that a participant is honest if it follows the protocol exactly and does not collude with or leak secret information to other nodes

A participant is dishonest otherwise.
> Dishonest nodes can exhibit Byzantine behavior—they can be arbitrarily incorrect and can even just “go silent.”

The system is designed to provide anonymity among the set of honest participants, who remain online and uncompromised throughout an interaction period, and who do not compromise their identity via the content of the messages they send. We define this set of honest and online participants as the anonymity set for a protocol run.

If a group contains many colluding dishonest participants, Verdict can anonymize the honest participants only among the remaining subset of honest members: in the worst case of a group containing only one honest member, for example, Verdict operates but can offer that member no meaningful anonymity.

Similarly, Verdict does not prevent long-term intersection attacks \[30\] against otherwise-honest participants who repeatedly come and go during an interaction period, leaking information to an adversary who can correlate online status with linkable anonymous posts.

Like any distributed system, Verdict may be vulnerable to more general network-level Denial-of-Service (DoS) attacks as well, particularly against the servers that are critical to the system’s availability and performance. Such attacks are important in practice, but not specific to anonymous communication systems.

## 4 Protocol Design
> Verdict consists of two major components: the messaging protocol, and the cryptographic primitive clients and servers use to construct their ciphertexts.

### 4.1 Core Verdict Protocol
> Figure 3 summarizes the steps comprising a normal-case run of the Verdict protocol.


As in Dissent, Verdict’s anonymity guarantee relies on Chaum’s original security analysis \[13\], in which an honest node’s anonymity set consists of the set of honest nodes that remain connected in the secretsharing graph after removing links to dishonest nodes.

Since each client shares a secret with every server, and we assume that there exists at least one honest server, this honest server forms a “hub” connecting all honest nodes.

The ciphertext- and proof-generation processes assume that communication in the DC-net is broken up into time slots (akin to TDMA), such that only one client, the slot's owner, is allowed to send an anonymous message in each time slot. The owner of a slot is the client who holds the private key corresponding to a pseudonym public key assigned to the slot. To maintain the slot owner’s anonymity, no one must know which client owns which transmission slot.


Figure 4 shows an example DC-net transmission schedule with three slots, owned by pseudonyms A, B, and C. Each slot owner can transmit one message per messaging round, and the slot ordering in the schedule remains the same for the duration of the Verdict session.

### 4.2 Verifiable Ciphertexts in Verdict
> While Verdict’s anonymity derives from the same principles as Dissent’s, the key difference is in the “alphabet” with which Verdict generates DC-net ciphertexts, and in the way Verdict combines and checks those ciphertexts.

Dissent uses a symmetric-key cryptographic pseudo-random number generators (PRNG) to generate shared secrets, and uses bitwise XOR to combine them and later to reveal the plaintext message. While efficient, the symmetric-key approach offers no way to check that any node’s ciphertext was generated correctly until the final cleartext messages are revealed. If any node corrupts a protocol round by sending an incorrect ciphertext, Dissent can eventually identify that node only via a complex retroactive blame procedure.

Verdict, in contrast, divides messages into chunks small enough to be encoded into elements of algebraic groups, such as Schnorr \[44\] or elliptic curve groups, to which known proof-of-knowledge techniques apply.

Thus, any Verdict ciphertext is generated on behalf of the holder of some particular pseudonym keypair.

In particular, a ciphertext correctness proof attests that either:
* The ciphertext is an encryption of any message, and the producer of the ciphertext holds the private part of the pseudonym key for this slot; or
* The ciphertext is an encryption of a null cover message, which, when combined with other cover ciphertexts and exactly one actual encrypted message ciphertext, will combine to reveal the encrypted message.

Only the pseudonym key owner can produce a correctness proof for an arbitrary message following the first alternative above, while any node can generate an “honest” cover ciphertext—and the proof by construction reveals no information about which alternative the proof generator followed.

In Verdict, each client computes and attaches a cryptographic correctness proof to each ciphertext it sends to its upstream server, and each server in turn attaches a correctness proof to the server-side ciphertext it generates in Phase 3 of each round (Figure 3).

> Verdict currently treats server-side failures of all types, including invalid server ciphertexts, as “major events” requiring administrative action, and simply halts the protocol with an alert until such action is taken.

### 4.3 Scheduling Pseudonym Keys
To assign ownership of transmission slots to clients in such a way that no one knows which client owns which slot, Verdict applies an architectural idea from Dissent \[54\].

* At the start of a Verdict session, each of the N clients secretly submits a slot owner pseudonym key to a verifiable shuffle protocol \[38\] run by the servers.

* The public output of the shuffle is the N pseudonym keys in permuted order—such that no one knows which node submitted which pseudonym key other than their own.

* Verdict participants then use each of these N pseudonym keys to initialize N concurrent instances of the core Verdict DC-net with each instance becoming a slot in a verifiable DC-net transmission schedule.

**Scheduling Policy**
Not every client will necessarily want to transmit an anonymous message in every messaging round. In addition, clients may want to transmit messages of different lengths. To make Verdict more efficient in these cases, Verdict allows clients to request a change in the length of their messaging slot (e.g., so that a client can send a long message in a single messaging round) and to temporarily “close” their transmission slot (if a client does not expect to send a message for several rounds). Clients issue these requests by prepending a few bits of control data to the anonymous message they send in their transmission slot.

### 4.4 Hybrid XOR/Verifiable DC-Nets
While the verifiable DC-net design may be needed in scenarios in which disruptions are frequent, the publickey cryptography involved imposes a much higher computational cost than traditional XOR-based DC-nets.

To offer better performance in groups with fewer or less frequent disruptions, Verdict has a “hybrid” mode of operation that uses the fast XOR-based DC-net when there are no active disruptors in the group, and reverts to a verifiable DC-net in the presence of an active disruptor.

This hybrid Verdict DC-net marries the relatively low computational cost of the XOR-based DC-net with the low accountability cost of the verifiable DC-net.

To set up a hybrid DC-net session:
* all protocol participants first participate in a pseudonym signing key shuffle, as described above in Section 4.3. At the conclusion of the shuffle, all nodes initialize two DC-net slots for each of the N clients: one traditional Dissent-style DC-net, and one verifiable Verdict DC-net.
* When the group is not being disrupted, clients transmit in their Dissent DC-net slot, allowing nodes to take advantage of the speed of Dissent’s XOR-based DC-net.
* When nodes detect the corruption of a message in the Dissent DC-net, the client whose message was corrupted reverts to transmitting in its verifiable DC-net slot.
* This client can use the verifiable slot to transmit anonymously the “accusation” necessary to identify the disruptor in the Dissent accusation process \[54, Section 3.9\].

The Verdict DC-net replaces the expensive verifiable shuffle necessary for nodes to exchange the accusation information in Dissent.

> In this way, Verdict offers the normal-case efficiency of XOR-based DC-nets while greatly reducing the cost of tracing and excluding disruptors.

### 4.5 Client Churn
> In realistic deployments clients may go offline at any time, and this problem becomes severe in large groups of unreliable clients exhibiting constant churn.

To prevent slow or unresponsive clients from disrupting communication, the servers need not wait in Phase 2 for all downstream clients to submit ciphertexts. Instead, servers can wait for a fixed threshold of t ≤ N clients to submit ciphertexts, or for some fixed time interval τ.

> Servers might also use some more complicated window closure policy, as in Dissent \[54\]: e.g., wait for a threshold of clients and then an additional time period before proceeding.

There is an inherent tradeoff between anonymity and the system’s ability to cope with unresponsive clients. If the servers close the ciphertext submission window too aggressively, honest but slow clients might be unable to submit their ciphertexts in time, reducing the anonymity of clients who do manage to submit messages.

### 4.6 Limitations and Future Enhancements
> This section outlines some of Verdict’s current limitations, deployment issues, and areas for future work.

**Group Evolution**
This section outlines some of Verdict’s current limitations, deployment issues, and areas for future work.
> We consider group management policy to be orthogonal to this paper’s communication mechanisms.

**Sybil Attacks**
If it is too easy to join a group, dishonest participants might flood the group with Sybil identities \[20\], giving an anonymous slot owner the impression that she has more anonymity than she actually does.

**Membership Concealment**
Verdict considers the group roster, containing the public keys of all participants, to be public information: concealing participation in the protocol is an orthogonal security goal that Verdict currently does not address

We are exploring the use of anonymous authentication techniques \[24, 31, 43\] to enable Verdict clients to “sign on” and prove membership in the group without revealing to the Verdict servers (or to the adversary) which specific group members are online at any given time.

**Unresponsive Servers**
Verdict currently assumes that the servers supporting a group are well-provisioned and highly reliable, and the system simply ceases communication progress in the face of any server’s failure.

* Before the protocol run, every server uses a publicly verifiable secret sharing scheme \[45\], to distribute shares of its per-session secret key
* The scheme is configured such that any quorum of M − h + 1 shares is sufficient to reconstruct the secret.
* Thus, at least one honest server must remain online and contribute a share for a secret to be reconstructed.

**Blame Recovery**
The current Verdict prototype can detect server misbehavior, but it does not yet have a mechanism by which the remaining servers can collectively form a new group “roster” with the misbehaving nodes removed.
> Slashing would remove dishonest nodes?

We expect off-the-shelf Byzantine Fault Tolerance algorithms \[12\] to be applicable to this group evolution problem. Using BFT to achieve agreement, however, requires a stronger security assumption: in a group with f dishonest servers, there must be at least 3 f + 1 total servers. We sketch a possible BFT-based group evolution approach here:

The BFT cluster’s shared state in this case is the group “roster,” containing the session nonce and a list of all active Verdict clients and servers, identified by their public keys. The two operations in this BFT system are:
* EVOLVE GROUP(nonce, node index, proof), a request to remove a dishonest node (identified by node index) from the group roster.
* GET GROUP(), which returns current the group roster.

If, at some point during the Verdict session, a Verdict node concludes that the protocol has failed due to the dishonesty of node d, this honest node makes an EVOLVE GROUP request to the BFT cluster and waits for a response. The honest BFT servers will agree on a new group roster with the dishonest node d removed and the Verdict servers will begin a new instance of the Verdict protocol with the new group roster. Clients use GET GROUP to learn the new group roster.

## 5 Verifiable DC-net Constructions
> The Verdict architecture relies on a verifiable DC-net primitive that has many possible implementations. In this section, we first describe the general interface that each of the cryptographic constructions must implement— which could be described as a “Verdict ciphersuite API”—then we describe the three specific experimental schemes that Verdict currently implements

### 5.1 Verifiable DC-net Primitive API
The core cryptographic primitive consists of a set of six methods. Each of these six methods takes a list of protocol session parameters (e.g., group roster, session nonce, slot owner’s public key) as an implicit argument:
* Cover Create: Given a client session secret key, return a valid client ciphertext representing “cover traffic,” which do not contain actual messages.
* Owner Create: Given a client session secret key, the slot owner’s pseudonym secret key, and a plaintext message m to be transmitted anonymously, return a valid owner ciphertext that encodes message m.
* Client Verify: Given a client public key and a client ciphertext, return a boolean flag indicating whether the client ciphertext is valid.
* Server Create: Given a server private key and a set of client ciphertexts, return a valid server ciphertext.
* Server Verify: Given a server public key, a set of valid client ciphertexts, and a server ciphertext, return a flag indicating whether the server ciphertext is valid.
* Reveal: Combine N client ciphertexts and M server ciphertexts, returning the plaintext message m.

However these methods are implemented, they must obey the following security properties, stated informally:
* Completeness: An honest verifier always accepts a ciphertext generated by an honest client or server.
* Soundness: With overwhelming probability an honest verifier rejects an incorrect ciphertext, such as an owner ciphertext formed without knowledge of the owner’s pseudonym secret key.
* Zero-knowledge: A verifier learns nothing about a ciphertext besides the fact that it is correctly formed.
* Integrity: Combining N valid client ciphertexts, including one ciphertext from the anonymous slot owner, and M valid server ciphertexts, reveals the slot owner’s plaintext message.
* Anonymity: A verifier cannot distinguish a client ciphertext from the anonymous slot owner’s ciphertext. Appendix C offers a game-based definition of anonymity.

### 5.2 ElGamal-Style Construction
> The first scheme builds on the ElGamal public-key cryptosystem \[21\].

In ElGamal, a public/private keypair has the form (B,b) = $(g^b ,b)^1,$ and plaintexts and ciphertexts are elements of an algebraic group $G^2$.

We refer to this as the “ElGamal-style” construction because its use of an ephemeral public key and encryption by multiplication structurally resembles the ElGamal cryptosystem. Our construction does not exhibit the malleability of textbook ElGamal encryption, however, because a proof of knowledge of the secret ephemeral public key is attached to every ciphertext element.

**Client Ciphertext Construction**
Given a list of server public keys ($B_1$,...,$B_M$), a client constructs a ciphertext by selecting an ephemeral public key Ri = g ri at random and computing the ciphertext element:

If the client is the slot owner, the client sets m to its secret message, otherwise the client sets m = 1.

The client must somehow prove that the ciphertext tuple ($R_i$ ,$C_i$) was generated correctly.
> We adopt the technique of Golle and Juels \[27\] and use a non-interactive proof-of-knowledge of discrete logarithms \[11\] to prove that the ciphertext has the correct form.

If the slot owner’s pseudonym public key is Y, the client’s ephemeral public key is Ri , and the client’s ciphertext element is Ci , the client generates a proof:


The tuple  serves as the client’s ciphertext. As explained in Section 4.1, all participants sign the messages they exchange for accountability.

**Server Ciphertext Construction**
Given a server public key  and a list of ephemeral client public keys ($R_1$,...,$R_N$), server j generates its server ciphertext as:

The server proves the validity of its ciphertext by creating a non-interactive proof of knowledge that it knows its secret private key $b_j$ and that its ciphertext element $S_j$ is the product of the ephemeral client keys raised to the exponent −$b_j$:


**Message Reveal**
To reveal the plaintext message, a participant computes the product of N client ciphertext elements and M server ciphertext elements:

Each factor  where $r_i$ is client i’s ephemeral secret key and $b_j$ is server j’s secret key, is included exactly twice in the above product—once with a positive sign in the client ciphertexts and once with a negative sign in the server ciphertexts. These values therefore cancel, leaving only the plaintext m.

**Drawbacks**
> Since the clients must use a new ephemeral public key for each ciphertext element, sending a plaintext message that is L group elements in length requires each client to generate and transmit L ephemeral public keys. The proof of knowledge for this construction is L+O(1) group elements long, so a message of L group elements expands to 3L+O(1) elem

### 5.3 Pairing-Based Construction
> A major drawback of the ElGamal construction is that, due to the need for ephemeral keys, every ciphertext is three times as long as the plaintext it encodes. des. Golle and Juels \[27\] use bilinear maps to eliminate the need for ephemeral keys. Our pairing-based construction adopts elements of their technique, while avoiding their reliance on a trusted third party, a secret-sharing scheme, and a probabilistic transmission scheduling algorithm.

A symmetric bilinear map $\hat{e}$ maps two elements of a group $G_1$ into a target group  $G_2$. A bilinear map has the property that: $\hat{e}(aP,bQ)$ = $\hat{e}(P,Q)^a$$^b$.

To be useful, the map must also be nondegenerate (if P is a generator of $G_1$, $\hat{e}(P,P)$ is a generator of $G_2$) and efficiently computable \[8\]. We assume that the decision bilinear Diffie-Hellman assumption \[7\] holds in $G_1$.

> Since pairing allows a single pair of public keys to generate a sequence of shared secrets, clients need not generate ephemeral public keys for each ciphertext element they send. This optimization leads to shorter ciphertexts and shorter correctness proofs.

**Client Ciphertext Construction**
For a set of server public keys ($B_1$,...,$B_M$), a public nonce τ ∈ $G_1$ computed using a hash function, and a client public key  a pairing-based client ciphertext has the form: 
> As before, if the client is not the slot owner, the client sets m = 1.

Each client can produce a proof of the correctness of its ciphertext by executing a proof of knowledge similar to one used in the ElGamal-style construction:

While the ElGamal-style scheme requires 3L + O(1) group elements to encode L elements of plaintext, a pairing-based ciphertext requires only L+O(1) group elements to encode an L-element plaintext.

**Server Ciphertext Construction**
Using a server public key , a public round nonce τ, and client public keys (A1,...,AN), a server ciphertext has the form:

The server proof of correctness is then:

**Message Reveal**
To reveal the plaintext, the servers take the product of all client and server ciphertexts:

**Drawbacks**
The main downside of this construction is the relatively high computational cost of the pairing operation. Computing the pairing operation on two elements of G1 can take an order of magnitude longer than a normal elliptic curve point addition in a group of similar security level, as Section 6.2 below will show.

### 5.4 Hashing-Generator Construction
> Our hashing-generator construction pursues a “best of both worlds” combination of the ElGamal-style and pairing-based constructions.

This construction has short ciphertexts, like the pairing-based construction, but avoids the computational cost of the pairing-based scheme by using conventional integer or elliptic curve groups.

To achieve both of these desired properties, the hashing-generator construction adds some protocol complexity, in the form of a session set-up phase.

**Set-up Phase**
In the set-up phase, each client i establishes a Diffie-Hellman shared secret $r_i$$_j$ with every server j using their respective public keys  and  by computing $r_i$$_j$ =  using a key derivation function KDF.

The hashing-generator construction requires a process by which participants compute a sequence of generators $g_1$,...,$g_L$ of the group G, such that no participant knows the discrete logarithm of any of these generators with respect to any other generator.

> In other words, no one knows an x such that $g^x_i$ = $g_j$ , for any i, j pair.

In practice, participants compute this sequence of generators by hashing a series of strings, (e.g., the round nonce concatenated with “1”, “2”, “3”, . . . ), to choose the set of generating group elements.

At the end of the set-up phase, every client i can produce a sequence of shared secrets with each server j using their shared secret $r_i$$_j$ and the L generators: 

**Client Ciphertext Construction**
To use the hashinggenerator scheme to create a ciphertext, the client uses its shared secrets $r_i$$_1$,...,$r_i$$_M$ with the servers, and generator $g_ℓ$ for the given protocol round to produce a ciphertext:

> As before, m = 1 if the sender is not the slot owner.

To prove the validity of a ciphertext element, the client executes the following proof of knowledge, where Y is the slot owner’s pseudonym public key, $r_i$ = $\sum^M_{j=1}$ $r_i$$_j$, and $R_i$$_j$ is the commitment to the secret shared between client i and server j:


**Server Ciphertext Construction**
Server j's ciphertext for the e ℓth message exchange round is similar to the client ciphertext, except with negated exponents:


The server proves correctness of a ciphertext by executing a proof of knowledge, where $r_j = \sum_{i=1}^N$ $r_{ij}$

PoK{$r_j$: ($\Pi{^N_{i=1}R_{ij}}$) = $\hat{g}^{r_j}$$\land$$S_j$ = $g_ℓ$$^{-r_j}$}

**Message Reveal**
The product of the client and server ciphertexts reveals the slot owner’s plaintext message m:

m = ($\Pi^N_{i=1}$$C_i$)($\Pi^M_{j=1}$$S_i$)

**Failed Session Set-up**
> A dishonest client i might try to disrupt the protocol by publishing a corrupted commitment R′$_{ij}$ that disagrees with server j’s commitment R${ij}$ to the shared secret r${ij}$ = KDF(g$^{a_i}$$^{b_j}$ ).

If the commitments disagree, the honest server can prove its innocence by broadcasting the Diffie-Hellman secret P$_{ij}$ = g$^{a_i}$$^{b_j}$ along with a proof that it correctly computed the Diffe-Hellman secret using its public key $B_j$ and the clients public key $A_i$.

PoK{b$_j$ : ρ$_{ij}$ = A$^{b_j}_i$$\land$ $B_j$ = g$^{b_j}$}

If the server is dishonest, the client can produce a similar proof of innocence. Any user can verify this proof, and then use g$^{a_i}$$^{b_j}$ to recreate the correct commitment R$_{ij}$ Once the verifier has the correct commitment R$_{ij}$, the verifier can confirm either that the client in question published an invalid commitment or that the server in question dishonestly accused the client.

**Long Messages**
To encode longer plaintexts efficiently, participants use a modified proof-of-knowledge construction that proves the validity of L ciphertext elements (C$_{i,1}$ through C$_{i,L}$) at once:

PoK{r$_i$y : (($\Pi$$^M_{j=1}$R$_{ij}$ = $\hat{g}^{r_i}$)$\land$($\land$$^L_{ℓ=1}$C$_{i,ℓ}$ = g$^{r_i}_ℓ$)) $\lor$ Y = g$^y$}

Servers can use a similarly modified proof of knowledge. This modified knowledge proof is surprisingly compact: the length of the proof is constant in L, since the length of the proof is linear in the number of proof variables (here, the only variables are r$_i$ and y).

> The total length of the tuple ($C$$_i$,PoK) using this proof is L+O(1).

**Lazy Proof Verification**
In the basic protocol, every server verifies the validity proof on every client ciphertext in every protocol round. To avoid these expensive verification operations, servers can use lazy proof verification: servers check the validity of the client proofs only if they detect, at the end of a protocol run, that the anonymous slot owner’s message was corrupted.

Lazy proof verification is possible only using the pairing-based or hashing generator ciphertext constructions.

## 6 Evaluation
> This section describes our Verdict prototype implementation and summarizes the results of our evaluations.

### 6.1 Implementation
We implemented the Verdict protocol:
* in C++ using the Qt framework as an extension to the existing Dissent prototype \[54\].
* using OpenSSL 1.0.1 for standard elliptic curve groups
* Crypto++ 5.6.1 for big integer groups
* and the Stanford Pairing-Based Cryptography (PBC) 0.5.12 library for pairings \[50\
* Unless otherwise noted:
* the evaluations use 1024-bit integer groups
* the 256-bit NIST P-256 elliptic curve group \[39\]
* and a pairing group in which G1 is an elliptic curve over a 512-bit field (using PBC’s “Type A” parameters) \[32\]

> We collected the macrobenchmark and end-to-end evaluation results on the DeterLab \[18\] testbed.
> https://github.com/DeDiS/Dissent.

### 6.2 Microbenchmarks
To compare the pure computational costs of the different DC-net schemes, Figure 5 shows ciphertext generation and verification throughput measured at a variety of block sizes, running on a workstation with a 3.2 GHz Intel Xeon W3565 processor.


Figure 5 shows that ciphertext verification is slightly faster than ciphertext generation. This is because generating the ciphertext and zero-knowledge proof requires more group exponentiations than proof verification does.

The hashing-generator construction, which is the fastest scheme tested, encrypts 20 KB of client plaintext per second.

The slowest, paring-based construction encrypts around 3 KB per second.

The fastest verifiable scheme is still over an order of magnitude slower than the traditional (unverifiable) XOR-based scheme, which encrypts 600 KB of plaintext per second.

The hashing generator scheme performs best because it needs no pairing operations and requires fewer group exponentiations than the ElGamal construction.

The three constructions also vary in the size of ciphertexts they generate (Figure 6).

While the pairing based scheme and the hashing-generator schemes encrypt length L plaintexts as ciphertexts of length L + O(1), the ElGamal-style scheme encrypts length L plaintexts as length 3L + O(1) ciphertexts.
> As discussed in Section 5.2, for every plaintext message element encrypted, ElGamal-style ciphertexts must include an ephemeral public key and an additional proof-ofknowledge group element.

### 6.3 Accountability Cost
> Figure 7 presents three graphs: (a) the time it takes to set up a transmission schedule via a verifiable shuffle, prior to DC-net communication, (b) the time required to execute a single DC-net protocol round in each scheme, and (c) the time required to identify a disruptor.

The graphs compare four protocol variants: Dissent, Verdict, Verdict with lazy proof verification, and the Dissent+Verdict hybrid DC-net.


Network latency comprises the majority of the time for a messaging round when using the Dissent and the hybrid Dissent+Verdict DCnets—messaging rounds take between 0.6 and 1.4 seconds to complete in network sizes of 8 to 1,024 clients.

In contrast, Verdict becomes computationally limited at 64 clients, taking approximately 2.5 seconds per round. Verdict (lazy) improves upon this by becoming computationally limited at 256 clients, requiring approximately 3 seconds per messaging round.

> As Figure 7 shows, the messaging round time in the hybrid Dissent+Verdict DC-net is as fast as in Dissent, but the hybrid scheme reduces Dissent’s time to detect misbehavior by roughly two orders of magnitude.

### 6.5 Anonymous Web Browsing
> Dissent demonstrated that accountable DC-nets are fast enough to support anonymous interactive Web browsing in local-area network deployments \[54\].

This configuration emulates, for example, a group of users in an Internet cafe browsing the Internet anonymously.

* In our simulation on DeterLab \[18\], 8 servers and 24 clients communicate over a network of 24 Mbps links with 20 ms node-to-node latency.
* To simulate a Web browsing session, we recorded the sequence of requests and responses that a browser makes to download home page content (HTML, CSS files, images, etc.) from the Alexa “Top 100” Web pages \[2\].
* We then replayed this trace with the client using one of four anonymity overlays:
* no anonymity
* the Dissent DC-net
* the Verdictonly DC-net
* and the Dissent+Verdict hybrid DC-net
* The simulated client sends the upstream (request) traffic through the anonymity network and servers broadcast the downstream (response) traffic to all nodes.

Figure 9 charts the time required to download all home page content using the four different network configurations.



These experiments show that Verdict adds no overhead to Dissent’s XOR-based DC-net in the absence of disruption. In addition, these experiments illustrate the flexibility of verifiable DC-nets, which can be used either as a “workhorse” for anonymous communication or more selectively in combination with traditional XOR-based DC-nets; we suspect that other interesting applications will be discovered in the future.

## 7 Related Work
* Chaum recognized the risk of anonymous disruption attacks in his original formulation of DC-nets \[13\], and proposed a probabilistic tracing approach based on traps, upon which Waidner and Pfitzmann expanded \[52\].
* Herbivore \[26, 46\] sidestepped the disruption issue by forming groups dynamically, enabling nodes to leave disrupted groups and form new groups until they find a disruption-free group.
* k-anonymous message transmission \[1\] also achieves disruption resistance by partitioning participants into small disruption-free groups. A crucial limitation of the k-anonymity system is that an honest client is anonymous only among a small constant (k) number of nodes.
> In contrast, Verdict clients in principle obtain anonymity among the set of all honest clients using the system.
* Dissent \[15, 54\] uses verifiable shuffles \[10, 38\] to establish a transmission schedule for DC-nets, enabling groups to guarantee a one-to-one correspondence of group members to anonymous transmission slots.
* Golle and Juels \[27\] introduced the verifiable DC-net concept and formally developed a scheme based on bilinear maps, forming Verdict’s starting point.
* Crowds \[42\], LAP \[29\], Mixminion \[17\], Tarzan \[23\], and Tor \[19\], provide anonymity in large networks, but these systems cannot protect against adversaries that observe traffic \[4, 37\] or perform active attacks \[9\] on a large fraction of network links.
* Verdict maintains its security properties in the presence of this type of strong adversary. A cascade of cryptographically verifiable shuffles \[25, 38\] can offer the same security guarantees that Verdict does, but these shuffles generally require more expensive proofs-of-knowledge.

## 8 Conclusion
Verdict is a new anonymous group messaging system that combines the traffic analysis resistance of DC-nets with disruption resistance based on public-key cryptography and knowledge proofs. Our experiments show that Verdict may be suitable for messaging in groups of hundreds to thousands of users, and can be combined with traditional XOR-based DC-nets to offer good normalcase performance while reducing the system’s vulnerability to disruption events by two orders of magnitude.