Untraceable Electronic Mail, Return addresses, and Digital Pseudonyms
David L. Chaum
University of California, Berkeley
Abstract
A technique based on public key cryptography is presented that allows
an electronic mail system to hide who a participant communicates with
as well as the content of the communication - in spite of an unsecured
underlying telecommunication system. The technique does not require a
universally trusted authority. One correspondent can remain anonymous
to a second, while allowing the second to respond via an untraceable
return address.
Key Words and Phrases: electronic mail, public key cryptosystems,
digital signatures, traffic analysis, security, privacy
Introduction
Cryptology is the science of secret communication. Cryptographic
techniques have been providing secrecy of message content for
thousands of years [3]. Another cryptographic problem, "the traffic analysis
problem" (the problem of keeping confidential who converses with whom,
and when they converse), will become increasingly important with the
growth of electronic mail. This paper presents a solution to the
traffic analysis problem that is based on public key cryptography.
The following two sections introduce the notation and assumptions.
Then the basic concepts are introduced for some special cases
involving a series of one or more authorities. The final section
covers general purpose mail networks.
Notation
Someone becomes a user of a public key cryptosystem (like that of
Rivest, Shamir, and Adleman [5]) by creating a pair of keys K and
Inv(K) from a suitable randomly generated seed. The public key
K is made known to the other users or anyone else who cares to know
it; the private key Inv(K) is never divulged. The encryption of
X with key K will be denoted K( X ), and is just the image of X under
the mapping implemented by the cryptographic algorithm using key K.
The increased utility of these algorithms over conventional algorithms
results because the two keys are inverses of each other, in the sense
that
Inv(K)( K( X ) ) = K( Inv(K)( X ) ) = X.
A message X is "sealed" with a public key K so that only the
holder of the private key Inv(K) can discover its content. If
X is simply encrypted with K, then anyone could verify a guess
that Y = X by checking whether K( Y ) = K( X ). This threat can be
eliminated by attaching a large string of random bits R to X
before encrypting. The sealing of X with K is then denoted
K( R, X ). A user "signs" some material X by prepending a large
constant C (all zeros, for example) and then encrypting with its
private key, denoted Inv(K)( C, X ) = Y. Anyone can verify that
Y has been signed by the holder of Inv(K) and determine the
signed matter X, by forming K( Y ) = C, X and checking for C.
Assumptions
The approach taken here is based on two important assumptions:
(1) No one can determine anything about the correspondences between a
set of sealed items and the corresponding set of unsealed items, or
create forgeries without the appropriate random string or private key.
(2) Anyone may learn the origin, destination(s), and representation of
all messages in the underlying telecommunication system and anyone may
inject, remove, or modify messages.
Mail System
The users of the cryptosystem will include not only the correspondents
but a computer called a "mix" that will process each item of mail
before it is delivered. A participant prepares a message M for
delivery to a participant at address A by sealing it with the
addressee's public key Ka, appending the address A, and then
sealing the result with the mix's public key K1. The left-hand
side of the following expression denotes this item which is input to
the mix:
K1( R1, Ka( R0, M ), A ) --> Ka( R0, M ), A.
The --> denotes the transformation of the input by the mix into the
output shown on the right-hand side. The mix decrypts its input with
its private key, throws away the random string R1, and outputs the
remainder. One might imagine a mechanism that forwards the sealed
messages Ka( R0, M ) of the output to the addressees who then decrypt
them with their own private keys.
The purpose of a mix is to hide the correspondences between the items
in its input and those in its output. The order of arrival is hidden
by outputting the uniformly sized itemsin lexicographically ordered
batches. By assumption (1) above, there need be no concern about a
cryptoanalytic attack yielding the correspondence between the sealed
items of a mix's input and its unsealed output - if items are not
repeated. However, if just one item is repeated in the input and
allowed to be repeated in the output, then the correspondence is
revealed for that item.
Thus, an important function of a mix is to ensure that no item is
processed more than once. This function can be readily achieved by a
mix for a particular batch by removing redundant copies before
outputting the batch. If a single mix is used for multiple batches,
then one way that repeats across batches can be detected is for the
mix to maintain a record of items used in previous batches. (Records
can be discarded once a mix changes its public key by, for example,
announcing the new key in a statement signed with its old private
key.) A mix need not retain previous batches if part of each random
string R1 constains something - such as a time-stamp - that is only
valid for a particular batch.
If a participant gets signed receipts for messages it submits to a
mix, then the participant can provide substantial evidence that the
mix failed to output an item properly. Only a wronged participant can
supply the receipt Y (= Inv(K1)( C, K1( R1, Ka( R0, M ), A ))), the
missing output X (= Ka( R0, M ), A ), and the retained string R1, such
that K1( Y ) = C, K1( R1, X ). Becasue a mix will sign each output
batch as a whole, the absence of an item X from a batch can be
substantiated by a copy of the signed batch.
The use of a "cascade", or series of mixes, offers the advantage that
any single constituent mix is able to provide the secrecy of the
correspondence between the inputs and the outputs of the entire
cascade. Incrimination of a particular mix of a cascade that failed
to properly process an item is accomplished as with a single mix, but
only requires a receipt from the first mix of the cascade, since a mix
can use the signed output of its predecessor to show the absence of an
item from its own input. An item is prepared for a cascade of n mixes
the same as for a single mix. It is then successively sealed for each
succeeding mix:
Kn( Rn, K( R, ... , K2( R2, K1( R1, Ka( R0, M ), A ))...)) -->.
The fist mix yields a lexicographically ordered batch of items, each
of the form
K( R, ... , K2( R2, K1( R1, Ka( R0, M ), A ))...) -->.
The items in the final output batch of a cascade are of the form
Ka( R0, M ), A, the same as those of a single mix.
Return Addresses
The techniques just described allow participant x to send anonymous
messages to participant y. What is needed now is a way for y to
respond to x while still keeping the identity of x secret from y. A
solution is for x to form an untraceable return address
K1( R1, Ax), Kx, where Ax is its own real address, Kx is a public key
chosen for the occasion, and R1 is a key that will also act as a
random string for purposes of sealing. Then, x can send this return
address to y as part of a message sent by the techniques already
described. (In general, two participants can exchange return
addresses through a chain of other participants, where at least one
member of each adjacent pair knows the identity of the other member of
the pair.) The following indicates how y uses this untraceable return
address to form a response to x, via a new kind of mix:
K1( R1, Ax ), Kx( R0, M ) --> Ax, R1( Kx( R0, M )).
This mix uses the string of bits R1 that it finds after decrypting the
address part K1( R1, Ax ) as a key to re-encrypt the message part
Kx( R0, M ). Only the addressee x can decrypt the resulting output
because x created both R1 and Kx. The mix must not allow address
parts to be repeated - for the same reason that items of regular mail
must not be repeated. This means that x must supply y with a return
address for each item of mail x wishes to receive. Also notice that
conventional as opposed to public key cryptography could be used for
both encryptions of M.
With a cascade of mixes, the message part is prepared the same as for
a single mix, and the address part is as showin in the following
input:
K1( R1, K2( R2, ..., K( R, Kn( Rn, Ax ))...)), Kx( R0, M ) -->.
The result of the first mix is
K2( R2, ..., K( R, Kn( Rn, Ax ))...), R1( Kx( R0, M )) -->,
and the final result of the remaining n-1 mixes is
Ax, Rn( R ... R2( R1( Kx( R0, M )))...).
Untraceable return addresses allow the possiblity of "certified" mail:
They can provide the sender of an anonymous letter with a receipt
attesting to the fact that the letter appeared intact in the final
output batch. The address A that is incorporated into a certified
letter is expanded to include not only the usual address of the
recipient, but also an untraceable return address for the sender.
When this return address appears inthe output batch of the final mix,
it is used to mail the sender a signed receipt which inlucdes the
message as well as the address to which it was delivered. The receipt
might be signed by each mix.
Summary and Conclusion
A solution to the traffic analysis problem has been presented that
allows any single intermediary to provide security for those messages
passing through it. In addition, the solution allows messages to be
sent or received pseudonymously. Through the notion of a roster of
pseudonyms, it also provides some new and interesting kinds of limited
anonymity.
References
1. Baran, P. On distributed communications: IX security secrecy and
tamper-free considerations. Memo RM-3765-PR, Rand Corp., Santa
Monica, CA, Aug. 1964.
2. Diffie, W. and Hellman, M.E. New directions in cryptography. IEEE
Trans. Information Theory IT-22, 6 (Nov. 1976), 644-654.
3. Kahn, D. The Code Breakers, The Story of Secret Writing.
Macmillan, New York, 1967.
4. Merkle, R.C. Secure communications over insecure channels. Comm.
ACM 21, 4 (Apr. 1978), 294-299.
5. Rivest, R.L., Shamir, A., and Adleman, L. A method for obtaining
digital signatures and public-key cryptosystems. Comm. ACM 21, 2 (Feb.
1977), 120-126.