Source-linked AI summary
Accountable Anonymous Group Messaging
Henry Corrigan-Gibbs, Bryan Ford
TL;DR
Anonymous messaging must protect participants without allowing members to spam, block messages, or create unlimited Sybil identities. Dissent combines a cooperative shuffle with preplanned DC-nets-style bulk transfer to provide accountable anonymity and support unbalanced message loads. A prototype demonstrates practicality for medium-sized, delay-tolerant groups, while large-scale, interactive, and coercion-resistant settings remain limited.
Problem
Existing anonymous messaging protocols weaken accountability, leaving groups vulnerable to denial-of-service and Sybil attacks while accountable voting protocols do not efficiently support general anonymous messaging.
Method
Dissent cooperatively shuffles message descriptors and pseudorandom seeds, then uses them in prearranged DC-nets-style bulk transfers with one message slot per member.
Results
A working prototype tested up to 44 nodes and handled large balanced and unbalanced loads in about 3.5× the time of non-anonymized TCP messaging.
Takeaways & Limitations
Dissent is practicable for anonymous, accountable messaging in medium-sized groups and delay-tolerant applications.
Takeaways & Limitations
Dissent may not scale to large groups, its shuffle latency can preclude interactive messaging, and its coercion resistance is limited under the stated traffic-observation model.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Dissent addresses the tension between strong anonymous participation and the need to prevent anonymous disruption in small, private groups. It combines shuffled sending, accountable anonymity, and efficient handling of unbalanced message loads, with a prototype showing practicality for delay-tolerant use.
- Motivation and contribution: Dissent provides provable integrity, anonymity, and accountability against strong traffic analysis and compromised members.It is presented as an accountable anonymous messaging protocol for small, widely distributed groups.
- Protocol contribution: Dissent supports arbitrary-size messages and unbalanced loads, including cases where one member sends substantial data while others send nothing.This extends shuffled-send functionality beyond fixed-size or balanced-message settings.
- Accountability: The protocol’s shuffle adds go/no-go and blame phases that trace malicious members disrupting the protocol without compromising anonymity.These phases address untraceable denial-of-service attacks in the underlying data-mining protocol.
- Protocol contribution: Dissent replaces DoS-prone slot reservation with a prearranged schedule giving every member exactly one message slot per round.The design builds on DC-nets and uses a shuffle protocol to distribute pseudorandom seeds for the scheduled transmissions.
- Limitations: Dissent is not intended for large-scale open-access messaging or file sharing, and its accountability assumes a closed group whose members cannot simply rejoin after expulsion.The serialized shuffle also imposes startup delay, limiting latency-sensitive applications.
- Evaluation: A prototype tested groups up to 44 nodes and handled large balanced and unbalanced loads in about 3.5× the time of non-anonymized TCP messaging.With 100ms inter-node delays, distributing messages up to 16MB among 16 nodes incurred 1.4 minutes of shuffle and startup latency.
2. PROTOCOL OVERVIEW
Dissent implements anonymous shuffled send through a shuffle stage followed by bulk transfer, preserving one-message-per-member correspondence while supporting arbitrary message sizes and applications such as voting and pseudonym creation. Its security goals cover integrity, anonymity, and accountability, but the shuffle remains costly when group size or descriptor length grows.
- Communication model: Dissent assumes a closed, known group whose members can anonymously send variable-length messages to members or non-members.The model also supports secret ballots and pseudonyms created under group policy.
- Shuffled send: Each run collects one message from every member, randomly permutes the messages, concatenates them in shuffled order, and sends the sequence to the target.Members with nothing to send can submit zero-length messages, enabling single-sender and multiple-sender service.
- Applications: One shuffled-send run can provide anonymous ballots or establish exactly one pseudonymous signing key per member, limiting unlimited Sybil identities.Dissent supports ballots of arbitrary type, format, and size, which members can count and independently verify.
- Security goals: The protocol’s security goals are integrity, anonymity against up to N−2 colluding members, and accountability through third-party-verifiable proof of misbehavior.Integrity requires either all honest members’ messages or knowledge that the run failed; accountability requires exposing at least one faulty member after an unsuccessful run.
- Protocol operation: The shuffle protocol equalizes message lengths, layers encryption, serially decrypts and shuffles ciphertexts, and uses go/no-go and blame phases to expose corruption.The bulk protocol instead shuffles message descriptors containing lengths, hashes, encrypted seeds, and ciphertext-validation hashes.
- Limitations and bulk transfer: The shuffle incurs O(NL) extra communication when only one member sends and a serial delay that grows when N or L is large.The bulk protocol is designed to send large, variable-length messages more efficiently than the fixed-length shuffle alone.
3. SHUFFLE PROTOCOL
The shuffle protocol builds an anonymized permutation through layered encryption, verification, and either decryption or blame. It preserves integrity and anonymity under collusion while making protocol disruption traceable, with O(N^2L) normal-case communication.
- Protocol construction: Each member encrypts a fixed-length datum under secondary and primary public keys before submitting it for anonymous shuffling.The protocol relies on IND-CCA2-secure encryption, signatures, hashes, saved randomness, and pseudorandom generators.
- Protocol construction: N serial anonymization steps permute ciphertexts and remove one primary encryption layer per member before broadcasting the final vector.Members sign phase messages and chain tamper-evident log hashes, while invalid or duplicate ciphertexts trigger blame.
- Verification and completion: Verification requires every member to confirm that its ciphertext appears in the common vector and to agree on its hash before decryption.A shared session nonce, participant keys, and member ordering are agreed before the run.
- Verification and completion: After unanimous verification, members release secondary private keys and remove the remaining encryption layers to recover a permutation of all submitted data.Each released key is checked against its public key; an incorrect key sends the protocol to blame.
- Security properties: The protocol preserves integrity and anonymity against up to N−2 colluding members, while accountability ensures successful completion or exposure of faulty members.Anonymity is defined through an indistinguishability game, and incorrect or equivocated messages can be tied to provable misbehavior.
- Complexity: O(N^2L) is the normal-case total communication cost, while unsuccessful blame can require O(N^3L); latency is O(N^2L) and computation is O(N^3 + N^2L) overall.An attacker can trigger at most O(N) blame runs before faulty members are exposed and removed.
4. BULK PROTOCOL
Dissent’s bulk protocol uses shuffled message descriptors and prearranged DC-net transmission to deliver variable-length messages while preserving integrity, anonymity, and accountability. Its communication is efficient for large, unbalanced loads, with optimal asymptotic efficiency in the single-sender case under the stated attack model.
- Message preparation: Each member creates encrypted pseudorandom ciphertexts from per-recipient seeds, XORs them with its message, and publishes hashes and encrypted seeds in a descriptor.The descriptor includes the message length, message hash, ciphertext hashes, and encrypted seeds.
- Descriptor shuffle: A shuffle randomly permutes one fixed-length descriptor from each member, establishing a prearranged slot for every message.Each member recognizes its own descriptor after the permutation and transmits the ciphertext associated with each slot.
- Recovery and blame: The target reconstructs each message by XORing received ciphertexts, ignores empty or hash-mismatched ciphertexts, and triggers a blame phase when corruption occurs.Valid accusations reveal the member whose seed or ciphertext caused the corruption; otherwise the sender may have corrupted or withheld a useful accusation.
- Security properties: The protocol preserves message integrity because shuffled descriptors contain hashes that allow the target, or all members, to verify recovered messages.The cleartext message hash is redundant for the target but supports verification when one node combines ciphertexts.
- Security properties: Anonymity holds because the shuffle hides the sender-to-slot permutation and pseudorandom one-time-pad bits reveal nothing to attackers.This remains true even when an attacker controls all but two honest members, provided the shuffle’s anonymity holds.
- Complexity: O(N^2) + Ltot bits per node is the normal-case communication complexity, while unsuccessful runs can require O(N^3) + Ltot bits because of blame.When Ltot dominates and only one member sends incompressible data, the protocol is asymptotically optimal under the attack model.
5. USAGE CONSIDERATIONS
The wrapper protocol adapts Dissent to practical group operation by anonymizing initiation, tolerating unavailable members, and managing accountability and liveness. Its temporary signing-key design supports repudiability, but traffic visibility can still defeat coercion resistance.
- Protocol initiation: Periodic protocol initiation by every member lets users send spontaneously without making the sender identifiable through the initiator’s traffic.A run may also be led by a non-anonymous outsider when group policy permits.
- Membership and quorum: Each run uses an available participant set MR within long-term membership M, with a minimum quorum Q limiting anonymity loss from malicious exclusion.If at most f ≤ Q − 2 nodes are faulty, honest participants retain at least (Q − f)-anonymity regardless of MR.
- Membership and quorum: Members can demand inclusion of reachable peers excluded by a prospective leader, forwarding messages when necessary as a condition of participation.This provides an additional defense against maliciously narrowing the participating set.
- Repudiability: Permanent signing keys create an accountability trail but can let members prove their messages to third parties, conflicting with repudiability and coercion resistance.The wrapper instead uses fresh temporary signing keys for each run.
- Repudiability: Temporary signing keys permit tracing misbehavior within a run without leaving proof that a member used a particular key, because authenticated exchanges and messages can be forged after the run.This provides repudiability against attackers requiring third-party-verifiable proof of responsibility.
- Liveness: If a node goes offline or withholds a required message, the leader can restart the run without persistently suspected or exposed nodes, while members retry under another leader if needed.Closure remains a corner-case liveness challenge because a malicious member may withhold a final message after learning others’ results.
6. PROTOTYPE IMPLEMENTATION
The prototype evaluation measures Dissent’s normal-case performance under controlled Emulab conditions, including balanced and unbalanced loads, message sizes, and group sizes. It shows substantial startup and computation costs but practical handling of large, uneven messages.
- Implementation and setup: The prototype uses Python and standard cryptographic primitives, and evaluates controlled simulated wide-area conditions on Emulab.Tests used x86 PCs, Ubuntu 7.04, 5Mbps links, and 100ms node-to-node latency; the topology is not claimed representative.
- Implementation and setup: The prototype measures only normal-case protocol costs because it omits secure public-key infrastructure, blame phases, and the wrapper protocol.Messages are signed and verified, but accountability mechanisms are not implemented in the prototype.
- Performance evaluation: 31 minutes is required for one node to anonymously send 16MB to 15 others, 3.6× longer than unauthenticated, non-anonymized TCP broadcast.The authors characterize this overhead as a reasonable price for strong anonymity.
- Performance evaluation: The full protocol handles balanced and unbalanced loads with similar performance for a given total message length, despite higher startup delay than shuffle alone.Figure 3 compares these load patterns among 16 nodes; the full protocol is more graceful under imbalance.
- Performance evaluation: The shuffle cost remains constant as message size grows and becomes negligible relative to bulk transfer.Figure 4 separates runtime into shuffle and bulk components.
- Performance evaluation: Unbalanced loads increase computation costs because the sending node XORs N −1 streams, and the tested shuffle runtime grows much faster with group size than bulk transfer.The N 2 shuffle scaling effect is only slight for the small groups tested.
7. RELATED WORK
Related systems provide pieces of anonymous communication, voting, or scalability, but differ from Dissent in message flexibility, accountability, traffic-analysis resistance, or group size. Dissent combines shuffled sending with accountable, variable-length group messaging for smaller private groups.
- Anonymous messaging systems: Dissent’s shuffle adds go/no-go and blame phases to make denial-of-service attackers traceable, while its bulk protocol adapts DC-nets for accountable transfer.Traditional DC-nets use nondeterministic reservation schemes and are difficult to protect against anonymous DoS attacks.
- Anonymous messaging systems: Mix-networks offer scalable anonymous communication but are vulnerable to traffic analysis and denial-of-service attacks.Crowds is more computationally efficient than mix networks but remains vulnerable to statistical traffic analysis when many network points are monitored.
- Voting and shuffles: Anonymous voting protocols often support only fixed-length ballots, limiting their direct use for general variable-length anonymous messaging.The related voting problem requires publicly known ballot contents with unknown authorship.
- Voting and shuffles: Verifiable cryptographic shuffles can be verified offline but require more complex calculations and repeated independent shuffles for randomness under compromised members.Dissent instead uses readily available cryptographic primitives.
- Alternative anonymity schemes: Ring signatures lack traffic-analysis protection, while k-anonymous transmission requires a large fraction of honest group members.These schemes therefore provide different security trade-offs from Dissent.
- Scalable systems: Tor and Herbivore scale to larger groups and permit interactive communication, but do not provide Dissent’s strong anonymity or accountability guarantees.Tor is vulnerable to traffic analysis, whereas Herbivore provides unconditional anonymity only within a small subgroup.
8. CONCLUSION
Dissent enables accountable anonymous exchange of variable-length messages within known groups while addressing traffic analysis, anonymous DoS, and padding limitations. The implementation supports its practicality for medium-sized participant groups.
- Conclusion: Dissent provides anonymous and accountable group communication for well-known participants exchanging variable-length messages.The conclusion frames the protocol as suitable for medium-sized groups rather than unrestricted deployment.
- Conclusion: Dissent adds traceability for faulty nodes and removes message-padding requirements that limited earlier shuffled-send schemes.The conclusion also reports practical deployment concerns and proposed solutions.