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

[Bryan Turner]

Paul,

	Please include your bibliography, I've read most of the anonymous
communication literature but your descriptions aren't matching up with what
I recall.

	If you haven't seen [1,2] already, you should definitely take a
look.  They are k-anonymous message channels, with decent overhead
(typically O(k) messages per round).  The problem seems to be, as with
Dining Cryptographers, the nodes who constantly broadcast junk, or misbehave
in the protocol.  This never reveals the information or participants, but it
can stop progress of the protocol.  Both papers solve cheaters with some
ad-hoc, suboptimal designs.

	I'm not sure I follow your discussion on Network Codes, are you
referring to the new rateless coding schemes [3], or a different use of the
term?  If you're referring to [3], the intermediate nodes do have enough
information (cryptographically speaking) to reveal information about the
communication patterns.  You might be able to merge Network Codes with
Secure Multiparty Sums to get something cryptographically secure..

--Bryan
bryan.turner at pobox.com

[1] k-Anonymous Message Transmission
    Louis von Ahn, Andrew Bortz, Nicholas J. Hopper
    http://citeseer.ifi.unizh.ch/690390.html

[2] A New k-Anonymous Message Transmission Protocol
    Gang Yao, Gengguo Feng
    http://dasan.sejong.ac.kr/~wisa04/ppt/9A2.pdf

[3] Network Coding
    http://tesla.csl.uiuc.edu/~koetter/NWC/

-----Original Message-----
From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-bounces at zgp.org] On
Behalf Of Paul Campbell
Sent: Sunday, September 18, 2005 2:49 AM
To: p2p-hackers at zgp.org
Subject: [p2p-hackers] Idea for new class of anonymous algorithms

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.