Technical Note Programming Techniques and Data Structures R. Rivest Editor Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms David L. Chaum University of California, Berkeley 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 untraceble return address. The technique can also be used to form rosters of untraceable digital pseudonyms from selected applica- tions. Applicants retain the exclusive ability to form digital signatures corresponding to their pseudonyms. Elections in which any interested party can verify that the ballots have been properly counted are possible if anonymously mailed ballots are signed with pseudonyms from a roster of registered voters. Another use allows an individual to correspond with a record-keeping organi- zation under a unique pseudonym which appears in a roster of acceptable clients. Key Words and Phrases: electronic mail, public key cryptosystems, digital signatures, traffic analysis, secu- rity, privacy CR Categories: 2.12, 3.81 Introduction Cryptology is the science of secret communication. Cryptographic techniques have been providing secrecy Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. This work was partially supported by the National Science Foun- dation under Grant MCS 75-23739 and by the Air Force Office of Scientific Research under Contract F49620-79-CO 173. Author's present address: Computer Science Division, Electrical Engineering and Computer Sciences Department, University of Cali- fornia, Berkeley, California 94720. (415) 642-1024. © 1981 ACM 0001-0782/81/0200--0084 $00.75. of message content for thousands of years [3]. Recently, some new solutions to the "key distribution problem" (the problem of providing each communicant with a secret key) have been suggested [2, 4], under the name of public key cryptography. Another cryptographic prob- lem, "the traffic analysis problem" (the problem of keep- ing 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. Baran has solved the traffic analysis problem for networks [1], but requires each participant to trust a common authority. In contrast, systems based on the solution advanced here can be compromised only by subversion or conspiracy of all of a set of authorities. Ideally, each participant is an au- thority. 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 K -1 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 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 crypto- graphic 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 K-I(K(X)) = K(K-~(X)) = X. A message X is sealed with a public key K so that only the holder of the private key K-1 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 K-~(C, X) -- Y. Anyone can verify that Y has been signed by the holder of K -a 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: 84 Communications February 1981 of Volume 24 the ACM Number 2(1) No one can determine anything about the corre- spondences between a set of sealed items and the corresponding set of unsealed items, or create for- geries 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 partic- ipant prepares a message M for delivery to a participant at address A by sealing it with the addressee's pubfic 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: Ki(R1, K~(Ro, M), .4) ~ Ka(Ro, 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(Ro, 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
View Full Document
Unlocking...