New protocol for cryptographically strong, "accountable anonymous messaging"

[Bryan Ford]

A student and I here at Yale have recently been developing an experimental protocol for cryptographically strong anonymous messaging within a small online group or "virtual organization."  We believe the protocol is (provably) resistant to both traffic analysis and anonymous denial-of-service or disruption by malicious or compromised group members, and supports applications requiring an exact 1-to-1 correspondence of members to messages in a given round, such as voting or assigning 1-to-1 pseudonyms.  In its current form the protocol is intended only for small decentralized groups and is not scalable to large groups or providing "mass anonymity" as in Mixminion or Tor, and the protocol is suited only for non-interactive messaging or bulk file transfer due to high startup latencies, although we have some ideas for addressing these limitations in the future.  We have placed a preliminary draft of the protocol (with some experimental results from a very preliminary and incomplete implementation) at the URL below, and would like to solicit analysis and feedback from interested cryptographers or distributed systems folks.

Thanks,
Bryan

Accountable Anonymous Group Messaging
http://arxiv.org/abs/1004.3057

Users often wish to participate in online groups anonymously, but misbehaving users may abuse this anonymity to spam or disrupt the group. Messaging protocols such as Mix-nets and DC-nets leave online groups vulnerable to denial-of-service and Sybil attacks, while accountable voting protocols are unusable or inefficient for general anonymous messaging. 
We present the first general messaging protocol that offers provable anonymity with accountability for moderate-size groups, and efficiently handles unbalanced loads where few members have much data to transmit in a given round. The N group members first cooperatively shuffle an NxN matrix of pseudorandom seeds, then use these seeds in N "pre-planned" DC-nets protocol runs. Each DC-nets run transmits the variable-length bulk data comprising one member's message, using the minimum number of bits required for anonymity under our attack model. The protocol preserves message integrity and one-to-one correspondence between members and messages, makes denial-of-service attacks by members traceable to the culprit, and efficiently handles large and unbalanced message loads. A working prototype demonstrates the protocol's practicality for anonymous messaging in groups of 40+ member nodes.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com