probability 1/n for some n. However, we have explicitly chosen not to explore such optimizations at this time, since our goal here is to examine an extreme point in the design space—where the attributability of each and every packet is enforced. For the same reasons, we have not yet explored protocol-specific fate-sharing optimizations (such as only signing and verifying TCP SYN packets). Such optimizations could dramatically reduce overhead, albeit in exchange for some increased risk of nonattributability (such as via TCP connection hijacking).

evaluation

Having described and evaluated Clue’s security properties, we now turn to quantifying the overhead of our implementation’s basic security operations and measure its effect on TCP performance. We present these benchmarks to demonstrate the feasibility of our approach. We do not evaluate all aspects of Clue, leaving full consideration of revocation to future work.

Our user-level software prototype provides acceptable performance when using the optimizations described earlier. Clue adds about 30ms of end-to-end delay to sending a packet. For interactive applications like SSH, this extra delay is insignificant to users. Clue achieves a bulk TCP throughput of 17.5Mbps, which is greater than that enjoyed by the average wide-area Internet user. A typical Internet user browsing the Web using Clue would experience roughly the same performance as without using Clue.

Experimental setup. For our experiments, we use three hosts in a sender-delay-receiver configuration. The delay host runs Linux 2. 6 with a hardware configuration of dual- 2.8GHz Pentiums with 2GB of RAM and the NIST Net emulation package10 to introduce link delay. The sender is a dual- 3.4GHz Pentium with 4GB of RAM, and the receiver runs dual- 3.0GHz Pentiums with 16GB of RAM. Both sender and receiver run the Click-based implementation of Clue (discussed earlier) over Linux 2. 6, using the default values for send and receive buffer sizes.

For all experiments, we use the d277699-175-167 parameter file prepackaged with PBC, yielding a group signature scheme with strength rough-

Without a
plausible threat
of accountability,
the normal social
processes that
disincentivize
criminal behavior
cannot function.

ly equivalent to a standard 1,024-bit RSA signature. 8 The BBS scheme outputs signatures 195B long using this parameter file.

Microbenchmarks. We start by measuring the overhead of the basic cryptographic operations Sign and Verify and their variants, as described earlier. The table here outlines the average time taken across 100 iterations of these operations on the receiver. The first column of results for “ 1 packet” are overheads when executing on a single 1,277B packet as input; we chose 1,277, since the combination of the packet, 195B for basic BBS signature, 8B for timestamp, and an extra 20B for windowed signing optimization yield a 1,500B packet. The second column, “ 8 packets,” are results with eight packets as input; one of Clue’s optimizations amortizes overhead across windows of multiple packets. In either case, the per-packet overhead is sufficiently small (10ms–30ms total) to be unnoticeable in interactive traffic but substantial enough to have a significant effect on bulk TCP performance.

The precomputation optimization for the sender separates signature computation from signing the packet. The “precomp sign” result measures the step that remains on the critical path—signing using a set of precomputed values—and shows that almost all overhead of Sign comes from generating message-independent cryptographic values (the “ precomputation” step), not from computing the message-dependent part of the signature or signing the packet itself. In our bulk-transfer experiments, we show that removing signature computation from the critical path of sending packets results in significant increase in throughput. Similarly, the row labeled “verify” represents the average time to verify a single signed packet of the same size; in our Clue implementation, verification is about 2.5x slower than signing.

The remaining two rows in the table measure the performance of Clue’s incremental verification scheme designed to defend against the flood of invalid packets described earlier. The “incremental verify” row is the time required to verify a valid packet signature using this scheme, essentially identical to the original verification