Re: New directions in anonymity (needed)

[anonymous-remailer@shell.portal.com]

> From: tcmay@netcom.com (Timothy C. May)
> Date: Sun, 5 Feb 1995 23:43:39 -0800 (PST)
> 
> Mike Ingle wrote:
> > All of our anonymous systems boil down to only two techniques: indirection
> > and broadcast. Indirection is sending a message through one or more
> > intermediate nodes to conceal its point of origin. Broadcast is sending a
> > message to multiple recipients to conceal the intended recipient.
> 
> First, I think it important to clearly distinguish between "sender
> anonymity," where the physical identity or sending site is hidden, and
> "receiver anonymity," where the same is true of the receiving site.

  I agree and will call them s anonymity, and r anonymity cause I am
too lazy to type much.

> Chaumian digital mixes--what you Americans call "remailers"--mainly
> solves the sender anonymity problem. Message pools, or broadcast to a
> group or site that includes the receiver, mainly deals with receiver
> anonymity. The combination of the two deals with both.

  I'll call the combo of "sender -> remail network -> pool ->
reciever" by the term "repool" in this message.

> Both are solved elegantly with the Dining Cryptographer's Protocol,
> about which much is written on this list every few months. Messages
> are "sent" in an Ouija-board fashion and received by the person who
> can successfully decrypt a public message sent over the system.

  Not so.  Though Chaum's DC protocol does give s/r anonymity, it does
so at a large cost.  Much larger than the repool protocol.

> > Broadcast is exactly as secure as it is nonscalable. If you
> > broadcast to 100 people, an attacker's uncertainty is one in
> > 100. The security grows linearly with the overall bandwidth. For
> > cryptographic-level security, it would need to grow exponentially
> > with bandwidth.

  I think this is exactly the right aproach.  So, lets look at the
cost of ataining anonymity.  For U people to communicate M bits (total
-- 2 people each sending 2 bits is M==4) s/r anonymously takes O(U*M)
bits multicast bandwidth for Chaum's DC protocol, but the repool
protocol uses only O(h*M) bits narowcast bandwidth plus O(M) bits
multicast bandwidth (Where h is the average number of remailer hops,
expected to be a constant wrt U and M, smaller than U, and much smaller
than M).

  Chaum's DC protocol also assumes an _interactive_ speed multicast
network.  Ouch!  The multicast internet protocol does help addresses
this problem, but it isn't widely available.  IRC is perhaps a bit
more expensize, more widely available, but lower bandwidth than
multicast IP packets.

> [...]
> > Anonymity needs something fundamentally new, something comparable to public
> > key for cryptography or blind signatures for digital cash. Suppose a server
> 
> I think you ought to carefully look at Chaum's work on Dining
> Cryptographers. It does all this. (It ain't perfect, and it ain't been
> implemented in practical terms, a la a "Pretty Good Dining
> Cryptographers," but it's at least as basic a concept as the other
> things are....some might say that all are variations on the same theme.)

  Chaum's DC protocol achieves U way s/r anonymity for U times the
work of sending a message.  Chaum's DC protocol provides s anonymity
as conditional as the cryptosystem achieves privacy (i.e.
uncomditional for one time pads, and dependant on 'strong
cryptosystems' assumption for the 'conventional' DC net).  Like the
repool protocol, it provides unconditional r anonymity.

  The repool protocol achieves U way s/r anonymity for no more than h
times the work of sending a message.  The repool protcol (by use of a
pool) provides unconditional (U-way) r anonymity, but (due to using
remailers) only provide conditional (U-way) s anonymity (conditional
on there existing at least one trusted remailer in the chain, and on
the existance of strong cryptosystems).  The repool protocol also
suffers from TA attacks like those sugested by Wei (at least as
currently implemented).

  What we would like is for the work to scale sub-linearly (ideally
exp(-U)) with the number of users U.  Said another way, we would like
U to scale faster than linearly as a function of the work (ideally
exp(W)).  If the effort of a protocol scales linearly (or worse) with
U, I don't think it will become widely employed.  Even better would be
a system which provided s/r anonymity without using multicast
bandwidths at all.  Btw, what is the cost of multicast v.s. narowcast
(say SMTP bassed) today on the net?

  Noyb