Receiver Anonymityvia Incomparable Public KeysBrent R. Waters Edward W. Felten Amit SahaiDepartment of Computer SciencePrinceton University{bwaters,felten,sahai}@cs.princeton.eduABSTRACTWe describe a new method for protecting the anonymity ofmessage receivers in an untrusted network. Surprisingly, ex-isting methods fail to provide the required level of anonymityfor receivers (although those methods do protect senderanonymity). Our method relies on the use of multicast,along with a novel cryptographic primitive that we call anIncomparable Public Key cryptosystem, which allows a re-ceiver to efficiently create many anonymous “identities” foritself without divulging that these separate “identities” ac-tually refer to the same receiver, and without increasing thereceiver’s workload as the number of identities increases. Wedescribe the details of our method, along with a prototypeimplementation.Categories and Subject DescriptorsE.3 [Data]: [Data Encryption]General TermsSecurityKeywordsAnonymity, PGP, Public Key Cryptography, Privacy1. INTRODUCTIONAnonymity is a desirable property in many communica-tion systems. Although several good methods exist to pro-tect the anonymity of message senders, there appears to beno existing method that fully protects receiver anonymity.We address this problem by presenting a system that pro-tects receiver anonymity for a wide range of message-passingapplications.Prior research has focused on how receiver anonymity canbe compromised because of the contents of a message orbecause of how a message is routed. However, receiveranonymity can also be compromised by the actual contentsPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.CCS’03, October 27–31, 2003, Was hington, DC, U SA.Copyright 2003 ACM 1-58113-738-9/03/0010 ...$5.00.of the public key used to encrypt messages. If several sendersshare the same public key to encrypt messages to be sent foran anonymous receiver, then they can infer that they are in-deed sending to the same receiver. They can then aggregatethe information they each have on that receiver to furthercompromise his anonymity. To achieve receiver anonymitya receiver must be able to create several truly anonymousidentities that will allow for a sender to both encrypt androute messages to him. These identities must be incom-parable in the sense that the two cannot be identified asbelonging to the same individual.1.1 RequirementsOur goal is to provide a way for senders to transmit mes-sages to receivers, but without anyone — including thesenders — being able to determine which message is destinedfor which receiver, or even being able to determine whetherany two messages are destined for the same receiver. Wewant to keep this information secret not only from outsiders,but also from message senders, since the sender is often thevery person from whom the receiver most wants to concealhis identity.We assume that adversaries can see both the contents ofmessages and where those messages are routed.We define three requirements that must be met for re-ceiver anonymity to be realized. The first requirement isthat if any conspiracy of senders and eavesdroppers is askedto determine the receiver of a particular message, they cando no better than random guessing.In practice, we cannot prevent receivers from replying tomessages, or from divulging information about their iden-tities in these replies. Whenever a receiver replies to amessage, some small amount of information about that re-ceiver’s identity will probably leak. (For example, Rao andRohatgi [16] describe how a surprisingly large amount ofinformation about authorship can be extracted from textdocuments.) If the receiver is providing some service to thesender or vice versa, some leakage of this type may be anecessary consequence of that service. Since we cannot pre-vent this type of leakage, our goal is to make sure that theadversary cannot get any useful information other than this.This type of information leakage motivates the second re-quirement of anonymity: each receiver must be able to cre-ate a large number of anonymous identities, such that anymessage sent to any of these identities will go to that re-ceiver, but nobody else will be able to tell that those anony-mous identities correspond to the same receiver. This re-quirement is important in an environment where senders canlearn a little information about each receiver; by preventing112the senders from learning that they are talking to the samereceiver, we prevent them from aggregating the informationthey have about that receiver.This second requirement implies that anonymous identi-ties must be incomp arable, so that an adversary who seestwo or more identities cannot tell whether they correspondto the same receiver. Practicality also requires that manymessages can be sent to the same anonymous identity with-out compromising the receiver’s anonymity.The third requirement is that the solution be reasonablyefficient. Some of the obvious approaches to the problemfail for efficiency reasons. For example, schemes that use aseparate private key for each potential sender are too ineffi-cient, as they require the receiver to try each of the possibleprivate keys when a message arrives1.As described in Section 2, none of the existing systems forreceiver anonymity can fully meet these criteria.1.2 Our SolutionOur solution meets all of the requirements mentionedabove. We prove its cryptographic properties, under thestandard assumption that the Decisional Diffie-Hellman prob-lem is hard. We also describe an implementation.In our solution, each message is sent to a multicast group.All members of the multicast group try to decrypt the mes-sage, but only one of them will succeed. The other membersof the group, having failed to decrypt the message, simply ig-nore it. The adversary can, of course, tell that the intendedreceiver is one of the members of the multicast group, sothis provides anonymity only within the multicast group.However, if the multicast group is large enough this will beacceptable in practice. (This aspect of our solution is notnovel, and the remainder of our
View Full Document
Unlocking...