3 ms·

Apologies in advance for the wall of text, but the first half is basically just a summary of their protocol for people who don't want to try to identify where t

by wgd 13y ago

Apologies in advance for the wall of text, but the first half is basically just a summary of their protocol for people who don't want to try to identify where the actual information resides (it appears to be http://dedis.cs.yale.edu/2010/anon/pres/120104-dissent.pdf http://dedis.cs.yale.edu/2010/anon/pres/120104-dissent.pdf). As I understand it, the basic idea is that there is a network made up of N clients and M servers, with the clients (and potentially servers) identifiable in some external fashion (IP addresses or GPG keys or whatever, it's unimportant to the protocol) and we want to make it possible for any of the clients to broadcast a message without anyone being able to tell which client it came from. So what happens is each client and each server generate a Diffie-Hellman key which is associated with their actual external identity. Then each client establishes a unique secret with each server (and vice versa, naturally). These unique secrets are used to produce N times M unique bitstreams using PRNGs (so each client has a bitstream corresponding to every server that exists, and each server has a bitstream corresponding to each client that exists). Then each client XORs together the bitstreams from the unique secret it shares with each server, and each server does the same thing for each client's shared secret. Now there are N + M bitstreams, with the nice property that if you XOR together all of them they all cancel out (because every client-server pairing occurs in the bitstream from that client and the bitstream from that server). Furthermore, if one client also XORs some data into the bitstream that they publish, no one else can tell, it still contains a bunch of indistinguishable-from-noise data to everyone else who might look. But then when we XOR together all N + M bitstreams, we end up with everything cancelling out except for that extra data that one client added. So then the Dissent protocol pulls in another construct, and uses something called MIX to shuffle a set of public keys generated by the peers, and uses these public keys to establish a transmission order, essentially reimplementing TDMA (Time-Domain Multiple Access) in a digital domain with signatures. In my opinion as a hobbyist interested in this stuff, the whole "everyone produces a bitstream and they magically evaporate leaving behind only the data everyone transmitted" thing is almost magically cool. The time-domain multiplexing is less cool, and my EE background compels me to wonder if a meaningful analogue to CDMA or OFDM could be developed. Well, obviously they could be developed the real question is "could they be useful?". It's also sort of interesting how the fact that we can't ever be allowed to know when a given peer is transmitting means that the design becomes more "continuous", with data being transmitted by everyone at all times so that the real transmissions can be disguised. I wonder if the theoretical perfectness could be loosened somewhat to allow only, say, 10% of peers to have to be transmitting at any given time (in the long run this could make it possible to identify a transmitter uniquely, but not so quickly that it wouldn't be useful still). Unfortunately, the second bullet-point (accountability) goes close to unfulfilled. And I feel like it sort of has to, since any method which could determine where malicious data comes from can also be used to undermine the anonymity of the system for everyone else. There's a kind of accountability, which is that the peers themselves can be associated with a public identity without anyone being able to tell which peer produced a given message, even in theory, but it doesn't extend to any system with open registration, because it doesn't handle the "sock puppet" problem at all. But personally I think the sock puppet problem is pretty much un-silver-bullet-able. The best we can probably ever hope to do for "general purpose" uses is probably a combination of a cryptographic proof-of-work algorithm, public-key signatures to allow (though not force) persistent identity, and some sort of reputation system.

wgd 13y ago
I've been thinking more about the whole "better multiplexing" issue for a bit now, and I suspect that some sort of http://en.wikipedia.org/wiki/Carrier_sense_multiple_access_with_collision_detection http://en.wikipedia.org/wiki/Carrier_sense_multiple_access_w... type of solution is ideal for this use case. Because if you think about it, two transmitters at once is not an unrecoverable failure mode, in fact it's easier to handle here than in, say, the original ethernet standard, because with packet-based internet stuff we can do things like changing the data rate on the fly in response to collisions. Currently the system I'm imagining works as follows: Every T seconds a new packet is initiated, and fancy spanning tree relaying or whatever is used, and eventually everyone has the XOR of all server and client versions of the packet, which happens to be the XOR of whatever various clients happened to include into their packet. Now the additional information for a client who chooses to add that will be the payload plus a checksum value (which must not be homomorphic under the XOR operation). If one client transmits, the checksum passes, and everyone is happy. If multiple clients transmit, they collide, and the checksum does not pass, and each transmitter knows this and waits a random backoff time (number of packets) before trying again. But in addition, a collision is often a signal that the packet rate is too low, so collisions also cause the packet period T to decrease (and lack of messages will cause it to increase, naturally). So I think the basic "matrix of shared secrets" construct can be extended to allow low-overhead (for values where "low" means "on the order of 3x") communications, because dynamically varying the period between packets and allowing anyone to try transmitting during any packet time will tend to mean that when no one is transmitting bandwidth drops to a very low level (I could easily believe 16-byte idle packets every 5 seconds for something where absolutely low latency isn't a requirement).
- ohmygodel 13y ago
  Two problems with unscheduled communications: 1. It allows the adversary to disrupt communications by continuously sending junk. Solving this problem was a major goal of Dissent not adequately handled by previous designs based on Dining Cryptographers networks. 2. Without a schedule telling everybody when to send something, the first guy to talk is obviously the sender, destroying anonymity.

by wgd 13y ago

wgd 13y ago

I've been thinking more about the whole "better multiplexing" issue for a bit now, and I suspect that some sort of http://en.wikipedia.org/wiki/Carrier_sense_multiple_access_with_collision_detection http://en.wikipedia.org/wiki/Carrier_sense_multiple_access_w... type of solution is ideal for this use case. Because if you think about it, two transmitters at once is not an unrecoverable failure mode, in fact it's easier to handle here than in, say, the original ethernet standard, because with packet-based internet stuff we can do things like changing the data rate on the fly in response to collisions. Currently the system I'm imagining works as follows: Every T seconds a new packet is initiated, and fancy spanning tree relaying or whatever is used, and eventually everyone has the XOR of all server and client versions of the packet, which happens to be the XOR of whatever various clients happened to include into their packet. Now the additional information for a client who chooses to add that will be the payload plus a checksum value (which must not be homomorphic under the XOR operation). If one client transmits, the checksum passes, and everyone is happy. If multiple clients transmit, they collide, and the checksum does not pass, and each transmitter knows this and waits a random backoff time (number of packets) before trying again. But in addition, a collision is often a signal that the packet rate is too low, so collisions also cause the packet period T to decrease (and lack of messages will cause it to increase, naturally). So I think the basic "matrix of shared secrets" construct can be extended to allow low-overhead (for values where "low" means "on the order of 3x") communications, because dynamically varying the period between packets and allowing anyone to try transmitting during any packet time will tend to mean that when no one is transmitting bandwidth drops to a very low level (I could easily believe 16-byte idle packets every 5 seconds for something where absolutely low latency isn't a requirement).

ohmygodel 13y ago
Two problems with unscheduled communications: 1. It allows the adversary to disrupt communications by continuously sending junk. Solving this problem was a major goal of Dissent not adequately handled by previous designs based on Dining Cryptographers networks. 2. Without a schedule telling everybody when to send something, the first guy to talk is obviously the sender, destroying anonymity.