Re: New directions in anonymity (needed)

[tcmay@netcom.com (Timothy C. May)]

Mike Ingle wrote:
> 
> There has been a lot of talk about anonymity and the best ways of providing
> it recently. Anonymity now is about where cryptography was before Diffie and
> Hellman's paper, or untraceable transactions before Chaum. To use it, you
> have to trust someone, or at least a group of people.
> 
> 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.

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.

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.

The process can be made information-theoretically secure, with
one-time pads used instead of ciphers. But, as Mike Ingle points out
here, the process can be compromised if _enough collusion_ exists. Ah,
but so can all known systems!

Digital money is not untraceable if you're the only person in the
universe (or in _your_ uhiverse...same difference) who is using it, or
if the banks, shops, and other customers are in collusion, leaving you
as the one and only user. (Proof: The banks and shops are not actually
using digital cash, leaving the "mark"--pun intended--as the only
person merrily spending digital cash. Ergo, all purchases made with
digital cash are traceable to this mark. I can imagine contrived
situations in the early days of digital cash when this kind of set-up
occurs.) 

My intuition is that any cryptographic situation in which an
individual/entity can be "isolated" so that all other individuals and
entities, and all connections, can be compromised (added to the set of
colluders) will be "broken." How else could it be?

Anyway, I think DC Nets are every bit as secure as e-cash is.
Obviously the security depends on a bunch of things, but the concept
of anonymous communication is not weaker in any fundamental way than
is digital cash. Full collusion by everyone who is not "you" causes
big problems with any cryptographic system that I know of.

(Stuff about reply blocks elided. I agree that more work is needed to
understand attacks on reply block methods. However, I'm not at all
convinced that "tracking back" is any different from the conventional
approach of demanding input-output mappings at each level, by
subpoenaing the remailer's records, etc. But I'll think about this
some more and maybe comment at another times.)

> 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.

This gets to the important point of _proving_ vs. _suspecting_. To
make this concrete, consider that 10,000 people may download the
entire contents of, say, "alt.anonymous," a message pool newsgroup
created largely for the publication of anonymous messages.

The Internetpol may _suspect_ that one of these 10,000 readers is the
person to whom the messatge is intended, but cannot _prove_ it. Even
if the list of readers is down around 100, I know of no legal systems
that would accept this as proof. (There are many issues here, and many
more detailed scenarios. For example, over the course of time, as
readership changes but some readers remain readers, patterns may
emerge from the noise. And there are issues of bandwidth. I am not too
worried about running out of bandwith soon, since an awful lot of text
messages can fit into just a single one of the MPEG or JPEG images
that flood the *.pictures newsgroups...and these *.picutures
newsgroups are sent to and locally stored on tens of thousands of
machines....) 

> 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.)

> has a large file. A message comes in and is combined into this file. Another
> message comes in with a key to retrieve data. The server processes the
> retrieval key against this large file and comes up with an output, which it
> returns to the person doing the retrieving. This output contains the input
> message, transformed in such a way that even the server cannot match it
> to the input that produced it. This is what we need.

But how is this any less "suspcious" in terms of pointing to the
receiver than is the more general and easier process of simply
retrieving the file from the server? Why would doing some sort of
computation on the distant server make the act of access any less
incriminating.? If 100 people all retrieve the file, they're the
"suspects," despite nothing being provable. And if those 100 people
first tell the server to do some particulary transformation, they're
still equally suspect. (Unless they tell the server to use a chain of
remailers to do the retransmission to them, which is different from my
understanding here, and is in fact the "anonymous anonymous ftp" we've
long talked of.) And if fewer than the 100 people actually send the
message, then of course the list of suspect is even smaller. (The
advantages of passive, do-nothing broadcast are lost, a net lose.)

> It would require three keys: an encryption key, a selection key, and a
> decryption key. The sender uses the recipient's encryption key to encrypt
[stuff elided]

Be careful also not to assume the server is trustable, as I gather it
is presumed to be here. (Doing the transformations, and all.)

> A method like this would permit anonymity without trust, much as public key
> allows secrecy without trust and digicash allows transaction privacy without
> trust. Is there any way to do it? There are functions like the Fourier
> transform that can distribute data over a large file, but the inverse
> function gives you back the same data. We need the not-so-inverse function
> to give back a different piece of data, but one that can be converted, by a
> private key, into the original, which the server never sees.

I expect broadcast models, or anonymous anonymous ftp models, to be
more sophisticated than simple "publish everything in alt.anonymous"
strategies. That is, multiple routes, multiple places, hierarchies,
etc. All involve trade-offs in time, space, security, cost,
convenience.

Some methods may involve splitting files into multiple pieces for
independent retrieval. However, I am not really convinced that the
alleged problems are solved this way.

The point about "which the server never sees" is confusing to me.
Surely the server _could_ see the transformed data if he wanted to, as
he was the one who did the remote transformation (as I understand
Mike's scheme). (If the scheme involves a server which can do
transformations but not see the output, then this is a much harder
problem, dealing with models of computation, secure hardware, etc.)

(The idea of a sealed box which executes a model in which no records
are kept, etc., is of course Chaum's original 1981 concept of a
digital mix. No "key" need be sent by the recipient if in fact the box
executes the proper mix function, keeps no records, is not
compromised, etc. If Mike is suggesting that his "server" behave more
like a true digital mix and thus not be as dependent as on human
trust, then of course this is a good idea. We need more mix-like
boxes, for our remailings. This has nothing to with the broadcast
model per se, dealing as it does with the general mix issue.)

In any case, what difference does it make if the server sees the data
or file? He surely can track his internal CPU processes and know which
incoming file was sent out, and to which address! (Just the remailer
in-out mapping problem again, which has always been unconcerned with
the internal contents of files.)

Sorry for the length here.

--Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
                       | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
Cypherpunks list: majordomo@toad.com with body message of only: 
subscribe cypherpunks. FAQ available at ftp.netcom.com in pub/tc/tcmay