Dissent - an anonymous communication protocol for small closed communities

Foreword

To understand the work of dissent, we must recall the classic work of David Chaum (the founder of the ideas of the practical implementation of network anonymity), published in 1988 and the protocol of "dining cryptographers (dining cryptographers)".

Imagine that three cryptographers came to dinner at a restaurant. After they sat down at the table, the waiter informs them that some anonymous well-wisher had paid for their dinner in advance.
')
Cryptographers know that this well-wisher could be one of them, but, in addition, they could be the NSA. They want to find out if one of them really paid for lunch, or whether it was the work of the NSA. But at the same time they are very tactful. If one of them pays, they will respect the right to anonymity and will not find out who paid. But they will be interested to receive an answer to the question in the following form: “did someone pay them or did the NSA do it?”. To do this, an anonymous broadcast of one bit of information is required.
Every cryptographer throws a coin. And it shows the result (tail or tail) to its neighbor on the right. Thus, there are three coin tosses, and each cryptographer knows the result of two of them. Further, each of them speaks the following information out loud: he saw the same two results, or different, but with one exception: the one who paid for lunch says the opposite, i.e. if he sees two different results, he says “the same”, if he sees two identical results, he says “different”.

If the number of differences at the table is odd, then dinner is paid for by one of the cryptographers, if even - then the NSA. Moreover, if the lunch was still paid by the cryptographer, then the other two cannot, on the basis of the statements made by all, know that it was him.

However, this protocol is not practical. As the number of participants increases, the throughput drops exponentially. Due to collisions, an attempt to simultaneously send messages to transfer one byte can be spent from 2n to 2 ^ n bytes, where n is the number of participants.
Therefore, this protocol has not had any practical application for a long time, although for many years attempts have been made to improve it (protocols "cryptographers at the disco", etc.).

Work review

Henry Corrigan-Gibbs and Bryan Ford from Yelles University (USA) provided open access to the draft version of Accountable Anonymous Group Messaging - “Anonymous Group Messages with Responsibility”, which developed Chaum’s idea and attempted to solve the related problems.

This study focuses on providing anonymous messaging in small private online groups. It is understood that group membership is closed and known to group members. Participants can send messages to each other, to the whole group or not to a member of the group in such a way that the recipient will know that someone from the group sent the message, but no member of the group sent the message. Group members can also use secret group voting bulletins or create aliases to collaborate with other members. At the same time, users become responsible (accountable), but not at the expense of compromising anonymity and allowing some authorized or majority of voters to reveal the anonymity of unpopular users, but due to the fact that a malicious user is deprived of the opportunity to interfere with the implementation of the group protocol.

For example, a malicious user should be unable to damage and block other users' messages, overwhelm a group with spam, throw in newsletters, or create an unlimited number of Sybil-aliases.

The researchers presented the first protocol of this kind, satisfying these conditions, called Dissent (Dining-cryptographers Shuffled-Send Network). Dissent provides proven integrity, anonymity and accountability in the face of threats to powerful traffic analysis methods and the presence of compromised participants. An experimental prototype demonstrates its effectiveness in sending messages, for which delay is insignificant, among small but widespread groups. In contrast to mix and DC networks, Dissent uses shuffled send (shuffled send primitive), making it possible for each group member to send exactly one message per round and making it possible to vote with a nickname assignment to bind the nickname to group members. . Unlike cryptographic check shuffles, Dissent uses only widely available crypto primitives and handles messages of arbitrary length under load imbalance so effectively that one participant can leak a multi-gigabyte document while others have nothing to send.

Two stages of Dissent - mixing and accumulation. The mixing protocol is based on the works of Brikel and Shmatikov on mixing messages of fixed length from each and an anonymous transfer to all members of the group. To prevent DoS attacks, go / no-go and “conviction” techniques are used to track dishonest protocol participants.

The accumulation protocol is based on informationally theoretically persistent DC networks, but includes a shuffling phase to eliminate DoS attacks. In each round, all group members transmit pseudo-random initial values ​​available to each, obtained through the shuffling protocol, so the XOR of all bit streams of participants gives the union of all messages sent by them of different lengths in a certain permutation. The cryptographic hashes transmitted at the mixing stage allow participants to verify the correctness of protocol steps, the integrity of messages, and provide protection against DoS attacks.

Of course, Dissent has limitations. It is not suitable for large-scale messaging in an open access environment or for file-sharing networks, although it can be used as a separate building block for them. Dissent is effective in small closed groups and ineffective in large groups. Dissent is also not a general-purpose voting system, as it provides only a limited form of protection against coercion. Delays in the shuffle protocol also make it impractical to use in applications sensitive to such delays. The researchers tested the Dissent working prototype in Emulab on groups of up to 44 participants connected by emulated transmission channels. Anonymous distribution of messages up to 16 MB in size by 16 nodes gives a delay of 100 milliseconds between nodes, Dissent shuffling and other starting procedures create a delay of 1.4 minutes, but taking into account the use of both balanced and unbalanced downloads with large messages, it takes 3.5 times longer than required non-anonymous TCP transfer to all group members. Depending on the size of the group, Dissent allows you to send anonymous messages of 1 MB in less than a minute for a group of four participants, 4 minutes for a group of 20 nodes and 14 minutes for a group of 40 nodes.

source code dissent on github