[p2p-hackers] Idea for new class of anonymous algorithms

[Paul Campbell]

I've been mulling over an idea for a new class of anonymous communication
algorithms.

Currently, they fall into one of two classes:

First, there's the Dining Cryptographer's version. This one makes information
theoretical security proofs about security but it has a huge downside. The
downside is that roughly O(N^2) bits have to be exchanged to transmit a single
bit between a group of N nodes. There's a variation recently proposed
(although I forgot where the paper is) that reduces this down to O(N) bits for
each bit. The difference is that in the original protocol, each node is
expected to respond consistently to all neighbors. In the new version, it may
broadcast something differently to different selected neighbors.

Also, there's a factor of "2" in most of these protocols...that the most
information that can be transmitted is asymptotically 2(N^2). However, the
protocol breaks down to being essentially a communication protocol across a
channel that is subject to interference. There are plenty of tree-based
collision resolution algorithms that will decrease this down to about 1/0.6.

The second group of algorithms is typical of the "mix nets". Here, the idea
is that the packet follows a chain of proxies who rebroadcast it until the
path through the proxies is sufficiently trustworthy and convoluted enough to
avoid detection.

Here, I'm half-thinking of a third possibility. Network codes all one to
broadcast using O(N) packets (which is the best that can be done). Network
codes can also be used to prevent intermediate nodes from being able to read
the packet stream (so-called "weakly secure" coding). Combining these two
means that network codes allow for a dining cryptographer-like solution except
that the upper limits on coding rates should be O(N) packets to broadcast
a single packet, which matches the intuitive "theoretical" minimum.

Anyways...I'm still happy with the results from the non-theoretical world of
mix nets. The overhead can be as small as a few nodes. There's no O(n ln x )
this and O(n ln x) that.