Vision Paper: Enabling Privacy for the Paranoids Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-Molina Krishnaram Kenthapadi, Nina Mishra, Rajeev Motwani Utkarsh Srivastava, Dilys Thomas, Jennifer Widom Stanford University Stanford, CA 94305 fgagan,bawa,pganesan,hector,kngk,nmishra,rajeev,usriv,dilys,[email protected] Abstract conduct business with that organization if the pub- lished policies were consistent with the individual’s P3P [27, 32] is a set of standards that al- expectations. lowcorporationstodeclaretheirprivacypoli- cies. HippocraticDatabases[4]havebeenpro- Example Consider an individual, Alice, who wants posedtoimplementsuchpolicieswithinacor- to sign up for a DealsRus service on the web. Deal- poration’s datastore. From an end-user in- sRus requires Alice’s email address to inform her of dividual’s point of view, both of these rest upcomingdeals. DealsRusrecognizestheprivacycon- on an uncomfortable philosophy of trusting cerns of its clients and has placed its P3P policies on corporations to protect his/her privacy. Re- their web-site. Alice is privacy-savvy and is using a cent history chronicles several episodes when browserwhichisP3Penabled. Beforegivingheremail such trust has been willingly or accidentally address, Alice’s browser would fetch the P3P policy violated by corporations facing bankruptcy from the DealsRus web-site. For instance, DealsRus courts, civil subpoenas or lucrative mergers. may state that email addresses will only be used for We contend that data management solutions currentpurpose(\completionandsupportoftherecur- for information privacy must restore controls ring subscription activity") and the recipients of such in the individual’s hands. We suggest that data will be restricted to ours (\DealsRus and/or en- enabling such control will require a radical tities actingastheiragentsorentities forwhomDeal- re-thinkonmodeling,release/acquisition,and sRus are acting as an agent") but not unrelated third management of personal data. parties. IfAliceishappywiththispolicy,thenshecan give DealsRus her email address. 1 Introduction Critique With the P3P framework, thus, Alice has Information Privacy is concerned with imposing lim- totrustthat(a)theorganizationhasclearlystatedits its on collection and handling of personal information policies, that(b) the organizationwillactually adhere suchascreditandmedicalrecordsbystateandprivate to the policies, and that (c) the organization has the organizations. These are early days for Information meanstoimplementthepoliciesintransitandstorage. Privacy, and norms and laws that impose restrictions All three aspects raise troubling issues: Even though ontheuseofpersonalinformationcollectedbyorgani- DealsRus has used legal language vetted by P3P, the zationsarebeingworkedoutasasolution. Technology endusermayfeelinundatedwithlegalesewhoseexact is being devised to assist the implementation of such practicality is open to interpretation [21, 25, 30, 36]. laws. Forinstance,whatexactlydoescurrentpurposemean? Perhaps it is within the ambit of current purpose for Status The Platform for Privacy Preferences DealsRus to spam their customer’s mailboxes? And (P3P) [27, 32] is a set of standards that allow orga- what doesit mean nottogiveemailaddressestothird nizations to declare their privacy policies. Recently, parties but restrict recipients to ours? Perhaps Deal- Hippocratic Databases [4] were envisioned to provide sRus has many wholly-owned subsidiaries which can support for an organization’s privacy policies within use the addresses? Does DealsRus provide adequate the organization’sdatastore. Thus,inthisframework, protection for personal data to prevent easy access to an organization would post its privacy policies, using data by intruders? And what would happen if Deal- agreed-upon language, and an individual would only sRusdeclaresbankruptcy,orchangesmanagement,or changesit policies, orits recordsare subpoenaed by a D No Integration: Alice’s email address value makes court? it impossible for DealsRus to acquire more infor- mation about Alice from third parties while using Inherency P3P and Hippocratic Databases put the her email address as the integration (join) key. onus of safeguarding privacy in the hands of organi- Obviously, our control wish-list is a fantasy to say zations that are often themselves guilty of trespass the least. Evenif DealsRuswould agreeto askAlice’s or sloppiness. Indeed, recent history chronicles sev- permission each time her email address was going to eral episodes where corporations have violated, ei- be used, Alice may not want to be interrupted all the therdeliberatelyoraccidentally,theircustomer’strust time. Andevenifitwerefeasibletoauditanorganiza- when they faced mergers, bankruptcy, courts or hack- tion’s business processes, DealsRus would never allow ers [2, 19, 23, 34]. Even if the underlying datastoreat its proprietary processes to be made public. And so DealsRus follows Hippocratic principles, if the rules on and so forth. the datastore is told to follow by DealsRus manage- In this paper, we illustrate through examples a se- ment are not the \ethical" ones (as far as Alice is riesofscenarioswhereanindividualcanretainlimited concerned), then the Hippocratic guarantees will be control over her information (Section 2). We claim of little use to Alice. that these examples are representative of a small set of \information types", and that for each such type, Thesis We contend that there is a better way to ap- onecandeviseageneralpurposesetofmechanismsto proach privacy, and that is to enable individuals to retain control (Section 3). We then propose to gather retain \control" over their information. At all times, thesetofmechanismsthatcoverallinformationtypes the individual should be able to \choose freely under in one framework which we call P4P: Paranoid Plat- what circumstances and to what extent they will ex- form for Privacy Preferences (Section 4). posethemselves,theirattitudes,andtheirbehavior,to Wecallthisframework\paranoid"becauseindivid- others" [41]. The desired \level of control" may vary: uals that use it are less trusting of organizationsthan for instance, in some cases, the individual may only individuals who use the P3P framework. We caution want that misuse of her information be auditable. In that ourframeworkis stillin its formativestages,and other cases, she may want to prevent access to infor- many of our concepts are still not well-de(cid:12)ned. Thus, mationtocertainorganizationsorforparticulartasks. at this point, we are only presenting the vision of our In any case, however, it should be the individual who framework, with the hopes that others in the commu- pro-actively decides what the level of control is. nity will help us re(cid:12)ne it, formalize it, and debug it. We believe that a case can also be made to orga- 2 Retaining Control { Initial Examples nizations to leave control in the hands of individuals. In particular,governmentsarepassing new legislation We claim that it is possible to approximate the ide- (e.g., California law SB1386, e(cid:11)ective July 1, 2003) alized control we have sketched using a variety of that forces organizations to inform individuals when- application-dependent techniques. Let us illustrate evertherehasbeenaprivacybreach,andmakesorga- what we mean using a couple of examples: email ad- nizationsliableforimproperuseofinformation. Given dresses and credit card numbers. Note that all of the the high overhead of securing data, and potentially techniques we will exploit in these examples are well- high liability costs, organizations could be persuaded known. As we will see after the examples, our goal to leave control to owners of the information. will be to synthesize general mechanisms out of the well-known individual techniques. Plan How can an individual retain controlat the ap- 2.1 Email Address propriatelevelonceshehasreleasedinformationtoan organization? Returning to our example, Alice would To retain control over her email address, Alice con- \retain control"if structs a trusted software agent that manages her A Permission: Every time DealsRus wanted to use emailaddress. (SeeFigure1.) Onlytheagentisgiven Alice’s email address, it would contact Alice to Alice’s true email address, say aly@aliceHost. When check if this particular use were approved; Alice wishes to give her email address to DealsRus, B No Copies: Alice delivers her email address in a theagentgeneratesanewaddress,sayaly1@agentHost, \magic"read-onlyfashionthatmakesitimpossible where agentHost is the computer where the agent for DealsRus to make copies; runs. When DealsRus receives aly1@agentHost (either C Supervision: Alice is allowed to supervise how from Alice or from the agent), it uses that address DealsRus actually uses the one copy of her ad- for communication with Alice. That is, an email to dress, e.g., DealsRus will make its business pro- aly1@agentHost is received by the agent, and will be cessestransparenttoAlice allowingherto seehow forwardedtoaly@aliceHostdepending onwhat restric- her information is being used; and tions Alice speci(cid:12)ed when the email was created. C If the intended use of the addressspans a limited timeoralimitednumberofinteractions(e.g.,per- hapsAlice issimply tryingto(cid:12)nd outwhat deals 1 2 are available this week), then by implementing a 3 5 4 timeout or a limited-use restriction Alice can en- sure her address is not used for other tasks later Alice Alice’s intimeorfortasksthatrequiremoreinteractions. Agent (Approximates Supervision goal.) D If DealsRus wishes to use Alice’s address in some DealsRus new way, it is likely that it will have to re- Figure 1: Alice interacts with DealsRus through her quest permission from Alice (or her agent), as agent. Alice(1)requestsand(2)obtainsanewtempo- aly1@agentHost is likely to be invalid. (Approx- raryemailaddressfromheragent,whichis(3)released imates Permission goal.) to DealsRus. Henceforth, DealsRus can only (4) send E If Alice usesdi(cid:11)erent emailaddressesfor eachor- messagestothe agentatthe releasedtemporaryemail ganization she interacts with, DealsRus will be addresswhichare(5)forwardedtoAliceafterchecking unable to use Alice’s address as an integration for speci(cid:12)ed restrictions. key to obtain more information about her from Alice speci(cid:12)es restrictions to the agent to give her third-party organizations. (Approximates No In- some control over how aly1@agentHost can be used. tegration goal.) For example: As we can see, for the particular case of email ad- 1 Timeout: The email aly1@agentHost is only valid dresses, Alice can retain a fair amount of control, and for a period of time. After that time, the agent does not have to trust as much the organizations she will refuse to forward messages to Alice. deals with. Furthermore, organizations do not have 2 Limited Use: The agent will only forward some to change their procedures; they handle email just as maximum number of messages. they did before. 3 Restricted Source: The agent will only forward a message if it comes from a pre-speci(cid:12)ed source. AdoptionandChallengesNoticethattheagentcan 4 Invalidation: Alice can at any time explicitly in- be implemented in a varietyof ways. The agentcould struct the agent to stop forwardingmessages. be part of Alice’s desktop email software, or it could 5 Isolation: The email aly1@agentHost is only re- beathirdpartythatprovidesthetemporaryemailad- leased to DealsRus. Other organizations will get dressgenerationandemailforwardingservice. Indeed, di(cid:11)erent email addresses. www.mailshell.comandwww.spamgourmet.comprovide How does Alice gain by trusting an agent? Alice such a third-party facility today with Timeout and now has to trust only one entity, as opposed to every Limited Use options respectively (also see the Lucent organization that receives her address under the P3P PersonalizedWeb Assistant project [15]). framework. Furthermore, if the agent code is pub- The temporary email addresses must be generated lic, Alice can see precisely what actions the agent will carefully. It should not be possible to infer the true take under di(cid:11)erent circumstances. This operational address from the temporary one. Similarly, succes- descriptionof the agent’s\privacyrules"canbemuch siveemailaddressesobtainedbyAlice should trulybe more precise that any legal/natural-language descrip- independent from each other. Moreover, Alice should tion that an organizationprovides under P3P. notbetheonlyindividualusingthe\@agentHost"ad- The forwarding restrictions enforced by the agent dresses. How can we design an agent that resides on do not provide all the control we wanted in our ideal- Alice’s desktop to meet such constraints? Perhaps a ized wish list, but they do provide a very useful level P2P-based email service could be designed along the of control for Alice. In particular: lines of [7, 35] in which Alice’s agent can participate and hide in a \crowd" of other agents. A DealsRus can distribute copies of aly1@agentHost A trusted third party can hide Alice in its \crowd" to other organizations, but a restricted-source of users. However, scaling with the number of users limitation can prevent the other organizations will be a challenge for such a provider. Recall that fromgettingthroughtoAlice. (ApproximatesNo each user might wish to create a new email address Copies goal mentioned earlier.) for each organization that he/she deals with. Each B If DealsRus gives aly1@agentHost to other orga- such account might have a unique set of restrictions. nizations, the agent will have proof of this ac- Receiving,(cid:12)lteringandforwardingemailswith lowla- tion, since the address aly1@agentHost was only tency might be a challenge. giventoDealsRus. (AlsoapproximatesNoCopies An interesting solution is for the third-party agent goal.) to encode the restrictions in the email address itself. That is, the agent can encrypt the restrictions using permission from Bob (or his agent), as the origi- its public key [20], and include them as part of the nalpseudonumislikelytobeinvalid(Approximate address. When email is received on an address, the Permission). agent can decipher the restrictions (using its private E If Bob uses di(cid:11)erent pseudonums for each organi- key) and enforce the rules. Such a scheme trades-o(cid:11) zation he interacts with, ShopsRus will be unable disk-accessesfor runtime processing. to use Bob’s credit card number as an integration key to obtain more information about him from 2.2 Credit Card Number third-partyorganizations. (ApproximatesNoInte- gration goal.) The above ideas can be extended to the handling of creditcardnumbersaswell. Anagentcanensurecon- Adoption Indeed, some credit card companies have trolofanindividual,sayBob,overtheuseofhiscredit begun o(cid:11)ering a subset of the above functionalities card. However, since credit is extended to Bob by his (e.g., one-time use credit card numbers [6, 22]). The bank, weneed toplace the agenteither atBob’sbank technology was hailed as a \landmark event by the or between the bank and the organizations that use industry" and promptly adopted by online merchants Bob’s credit card number. If the agent is not at the who have to bear the brunt of credit-card fraud, un- bank, it would have to appear to the organizations as like o(cid:15)ine merchants in which case the liability is as- abankthatcanhandlecharges,whichmaybedi(cid:14)cult sumedbythebankthatissuedthe card. Forexample, to achieve. Thus, let us assume that the bank plays thetravel-sitewww.expedia.comrecordeda(cid:12)scalthird- the role of trusted agent for Bob. quarterchargeofsixmillionUSdollarsin2000tocover The interaction between Bob and an organization, the cost of fraudulent transactions! The above anec- sayShopsRus, is analogousto that between Alice and dotessuggestthatorganizationswill indeedbewilling DealsRus. Neither Bob nor his agent gives out Bob’s to leave control in the hands of individuals if appro- truecreditcardnumber. Instead,ShopsRusreceivesa priate technology is devised. unique, temporary credit card number, which we will call a pseudonum. The agent manages the mapping 3 Retaining Control { Generalizing to between this pseudonum and Bob’s credit card num- \Information Types" ber. The agent may also enforces restrictions on the Canwegeneralizetheseconcepts,sothatanindividual use of the pseudonum in a variety of ways: can retain control over other \types" of information? 1 Timeout: The time of validity or number of It turns out that email addresses and credit cards are charges; the easiesttocontrolastheyrepresenta\servicehan- 2 Limited Use: The total amount that may be dle" for a work(cid:13)ow path that terminates at the indi- chargedto the pseudonum; vidual. Anagentcaneasilyplaceitselfinthispathand 3 Restricted Source: The sites that may make provide limited control on how the service is invoked. charges, or the types of purchases that may be Indeed, this is why we already have deployments that made to the pseudonum; seek to exercise control in ways described earlier. 4 Invalidation: Bob can at any time explicitly in- Inthissection,weconsiderfourtypesofpersonalin- struct his bank to stop honoring charges on the formationthatareubiquitoustoday: (a)LocalIdenti- pseudonum. (cid:12)ers,(b)Foreign-KeyIdenti(cid:12)ers,(c)ValuePredicates, 5 Isolation: A unique pseudonum is released to and (d) Multi-Source Value Predicates. We will see ShopsRus. Other organizations will get di(cid:11)erent thatitwillbehardertoretainthesamedegreeofcon- pseudonums. trol as with service handles, and organizations may Aswith hisemail,Bobretainssomelevelofcontrol haveto dramaticallychangethe waythey handle per- as to how his credit card is used. sonalinformation. Nevertheless,wearecautiouslyop- A ShopsRus can distribute copies of the pseudonum timistic that a collection of techniques can be devised toother organizations,but arestricted-sourcelim- thatmayleadtothesynthesisofageneralframework. itation prevents other organizationsfrom charging Bob’s credit (Approximate No Copies). 3.1 Local Identi(cid:12)ers B If ShopsRus gives the pseudonum to other organi- zations, the agent has proof of this action, since In many cases, organizations demand from its users the pseudonum was only given to ShopsRus (Ap- identi(cid:12)cation numbers like social security numbers proximate No Copies). (SSN) in the United States, or national identi(cid:12)cation C If the intended use of the address spans a limited numbers in other countries. For instance, the (cid:12)rst timeorcredit,thenwithanappropriaterestriction thing that many mail-order or on-line stores ask for Bob ensures that his credit is not used for other is a telephone number, since that is how they locate tasks later (Approximate Supervision). their customer’s records. In many cases, these num- D If ShopsRus wishes to charge Bob’s credit for a bers are only used as keys in the local database, and new deal, it is likely that it will have to request nothing else. Simple Protocol It is easy for an agent to hide the LabsRus true identity of an individual, say Carol. The agent generates a unique, private identi(cid:12)er for Carol, which 1 could be for example, a random 256 bit string. The organization,DealsRus receives this private identi(cid:12)er, and uses it as a primary key for Carol. The agent of courseremembersallofCarol’sidenti(cid:12)ers,sowhenever 2 Carolneedsto contactDealsRus, the properidenti(cid:12)er canbeissued. Andasinourpreviousexamples,Carol retains control over her identity: DealsRus does not David David’s knowCarol’struephonenumberorSSN,soanyabuses Agent of the private identi(cid:12)er are limited in scope. DealsRus may only be willing to accept identi(cid:12)ers Dr. Bones that looklikeSSNs orphonenumbers. Insuchacase, Carol’sagentmustmaptherandomidenti(cid:12)erintoone Figure 2: LabsRus interacts with Dr. Bones through that conforms to what DealsRus expects. David’s agent. (1) LabsRus sends David’s reports to hisagent. (2)ThereportsareforwardedtoDr. Bones ChallengesThereareafewpracticalissuesthatmust by the agent. be considered for such indirect identi(cid:12)cation numbers to work with today’s deployed systems. There is a not do anything too bad with them. chance that some other individual will generate the sameprivateidenti(cid:12)erasCarol. Organizationsmayal- 3.2 Foreign-Key Identi(cid:12)ers readyhaveproceduresinplaceforduplicateidenti(cid:12)ers. For example, two family members who share a phone Insomecases,anindividual’sidenti(cid:12)ersareusedmore may be buying goods at the same mail-order store. than just as local identi(cid:12)ers. The organization may Even SSNs are known not to be really unique identi- need to use them as foreign-keys to allow a legiti- (cid:12)ers,andcon(cid:13)ictsdohappen. Thebottomlineisthat mate (individual approved) integration or retrieval of organizations need to be prepared to deal with dupli- records from other organizations. cate user-generatedidenti(cid:12)ers,andshouldhaveapro- To illustrate, say David is a patient at Dr. Bones’ tocol in place to ask the userfor a di(cid:11)erent one. Such clinic, and had sometests done at LabsRus. (See Fig- protocolsarealreadycommonatweb-siteswhereusers ure2.) ThepatientinformationsystemthatDr. Bones selecttheirID:iftheIDistaken,thesitespromptsthe usesidenti(cid:12)es David byi1, alocal identi(cid:12)ergenerated user for a di(cid:11)erent ID. by David’s agent. Similarly, LabsRus identi(cid:12)es David A potential scheme to ensure uniqueness is the fol- by i2, a di(cid:11)erent local identi(cid:12)er. When David gets a blood test at LabsRus, he requests that the results be lowing. Carol can provide her agent with a particular sent to Dr. Bones’ clinic. Thus, LabsRus needs a way (uniqueandsecret)dataitem,sayherSSN.Theagent willthengenerateallidenti(cid:12)ersforCarolbasedonthis to send records for i2 that are received as records for dataitemandtheorganization’sname,e.g.,byusinga i1 at Dr. Bones’ clinic. one-wayhashfunctionlikeSHA-1[14]. Theidenti(cid:12)ers Simple Protocols There areat least two ways to do that are generated can be shown to have good cryp- this mapping: tographic properties: independence, uniqueness, and non-invertibility. A LabsRus can ask David’s agent for David’s iden- Real identi(cid:12)ers such as phone numbers have the tity with Dr. Bones. If the agent gives LabsRus advantage that they are more readily remembered i1, then LabsRus can communicate directly with by users. Thus, when Carol personally phones the Dr. Bones. However,LabsRusnowknowsDavid’s DealsRus help line, it will be a lot easier for her to identitywithDr. Bones,andcouldmisuseitlater remember her phone number rather than the ran- on. David would not know of any future sharing domly generated identi(cid:12)er. Or perhaps Carol has al- of information between LabsRus and Dr. Bones, lowed her phone to automatically provide her num- andhencelosecontrolofhispersonalinformation. ber to the callee (a feature known as caller-id in the B LabsRus can route the blood test results to Dr. United States), in which case DealsRus will immedi- BonesthroughDavid’sagent. Onewaytodothis ately know who is calling. This example illustrates a is as follows: David instructs his agent to antici- classic privacy-convenience trade-o(cid:11) which cannot be pate blood test results from LabsRus that are to avoided: If Carol wants privacy, then she is better o(cid:11) be routed to Dr. Bones. When LabsRus has the givingoutagent-generatedidenti(cid:12)ers,andalwaysrely- results,itsendsamessagetoDavid’sagentwhich ing on the agent for interactionswith outside entities. includes: If Carol wants convenience, then she can give out her personal identi(cid:12)ers, and hope that organizations do 1 David’s local identi(cid:12)er i2; 2 David’s blood test results; a series of predicates that serve to identify Ellen’s 3 A signature that can be used to prove that age y uniquely (e.g., p1 : (y == 58)? true : false, only LabsRus could have generated the given p2 : (y == 59)? true : false, etc.) The only way to test results; avoid this problem is to have DealsRus disclose the nature of the predicates by making the source SQL At this point, David’s agent removes the i2 iden- code visible to scrutiny by Ellen and her agent. This ti(cid:12)erandthe signatureof LabsRusfromthe mes- way Ellen can understand the nature of the informa- sage. Theagentlogsthe signatureasproof of the tion that is being given to ShipsRus. For example, if authenticity of the report, if needed later. The p is the predicate given earlier that checks if age is agentthen addsthe i1 identi(cid:12)erandforwardsthe greater than 60, Ellen will know that she is disclos- results to Dr. Bones. ing the fact that she is or is not a senior citizen to Notice that in [B], LabsRus remains unaware of ShipsRus. David’s doctor who receivesthe reports. Dr. Bones is The second issue is that Ellen may cheat and not unaware of the place where the tests were performed. give her true age. Of course, cheating may have later Thus, David again retains some control over his in- repercussionsforEllen. Forexample,shemayruninto formation. Anytime an organization wants to contact troublewhensheshowsupforthecruisewith asenior another organization to share David’s information, it discount ticket and looking like a teenager! We note must go through David’s agent. that Ellen could cheat by giving a false age even if ShipsRus were to ask Ellen for her age directly. ChallengesIn this scenario,it is clearthat organiza- Notary Protocol Is there anything that could be tions will have to change the way they operate. That done to prevent cheating by Ellen? For instance, say is, they need to be aware that following foreign keys ShipsRus does not trust Ellen, but does trust some needs to be done though agents, and not directly as other organizationthat can actasa notary andvouch they do today. We also observe that the above is still for Ellen’s age, like Dr. Bones o(cid:14)ce. Can we devise a sketch and a rigorous protocol needs to be de(cid:12)ned a protocol that enables Ellen to compute a ShipsRus that will allow such foreign-key mappings to be used predicate, whose result is vouched for by Dr. Bones? via a trusted agent without leaking any personal in- We present a weak version of the notary protocol formation. For example, how can David’s agent be that requires Ellen to trust Dr. Bones not to divulge assuredthatLabsRusisnothidinginformationwithin her information. With this protocol, the P3P guaran- the test reports that reveals David’s and its identity? teesarethebestwecanhopefor. LetussaythatEllen discloses her age to Dr. Bones, e.g., by having a med- 3.3 Value Predicates ical examination or by showing her birth certi(cid:12)cate. In our next example, say Ellen is purchasing a cruise ThereisnowayBoneswillvouchforEllen’sagewith- fromShipsRus, andthe site asksherforherage. Let outknowingtheage,sowecannotavoiddisclosingthe us assume that ShipsRus has a legitimate need for information. Ellen’s age y. Perhaps ShipsRus o(cid:11)ers a senior citi- Ellen’s agent must also disclose the mapping be- zen discount to individuals with an age over 60 years tweentheidenti(cid:12)erEllenusedatDealsRus,i1 andthe who take the cruise. We can model this situation by identi(cid:12)er Ellen uses with Dr. Bones, i2. Without the saying that ShipsRus needs to compute a predicate i1 : i2 mapping, Dr. Bones cannot really say whose p := (y > 60)? true : false. Thus, ShipsRus does not age he is vouching for. Ellen’s agent also provides a need to know y itself but the value p(y). How can signature for the i1 : i2 mapping, so that if a dispute ShipsRus obtain p(y) while Ellen retains control over arises in the future, Dr. Bones can prove that Ellen’s her age attribute y? agent claimed that i1 and i2 were the same person. In summary, the request for Ellen’s age proceeds as Simple Protocol We can proceed as follows. Ship- follows: sRus sends the predicate p to Ellen’s agent, e.g., as a SQL statement. (The query will run in a sandbox-ed 1 DealsRus asks Dr. Bones to evaluate p(y) for environment so it cannot have undesired side e(cid:11)ects.) the personDealsRuscallsi1 andwhousesEllen’s Ellen gives y to her agent, which then computes p(y) agent. andsendstheresulttoShipsRus. Inthisway,Ellenre- 2 Dr. BonesasksEllen’sagentforEllen’sidatDeal- tains control over her age information, and only gives ShipsRus the minimal legitimate information (p(y)) it sRus. If the agent approves, it sends the i1 : i2 mapping, appropriately signed. needs to have to provide service to Ellen. Challenges There are, of course, two important is- 3 Bonesthenlooksupi2’sage,yandcomputesp(y). The result is returned to DealsRus. sues we need to consider. First, the organization can \cheat" by using predicates that are easy to invert. For example, ShipsRus may give the trusted agent Challenges The weaker protocol we presented re- quires Ellen to reveal her DealsRus id to Dr. Bones. else. Yao [42] showed that any multi-party compu- The notarizing organization (Dr. Bones) could thus tation (and hence our multi-source value predicates) graduallygettoknowEllen’sidentityatvariousorga- can be solvedby building a combinatorialcircuit, and nizations. simulating that circuit. However, such schemes incur Of concern to DealsRus is the fact that it has to excessive computation and communication overhead. reveal its predicate p to Dr. Bones. Is it possible Can the recent work[18, 33] in this areamakes evalu- to devise a protocol that allows DealsRus to compute ating speci(cid:12)c predicate queries more practical? p(y) when DealsRus does not know y and Dr. Bones Trusted Third PartyAsimplersolutionistousean does not know p? agency that is trusted by all parties. The steps to do Trusted Third Party In the aboveprotocol, Ellen’s the computation are then as follows: EasyLoan asks agent could cheat and provide a false mapping since the agency to compute p(y;s) for the person it knows onlyitknowstherelationshipbetweenEllen’stwoper- as i1 and who uses a particular agent. By this point, sonas. Animprovementwouldbetorunagentsatsites Fredhasalready disclosedto EasyLoanwhomaypro- that could be trusted by both Ellen and the organi- videthe ageandsalary,sothe requestfromEasyLoan zations she deals with. In such a scenario, a trusted also includes the identities of Acme and Dr. Bones. organization,whichwecancalltheagencycanrunpri- TheagencythenasksFred’sagentforFred’sidentities vacy agents for a variety of individuals. The agency at Acme and Bones, and asks these organizations for somehowgathersevidencethataparticularindividual therequireddata. Finally,theagencycomputesp(y;s) iswhotheysaytheyare(perhapstheyhavetoshowup and returnsthe value to EasyLoan. The agencykeeps in personandidentify themselveswith aphoto identi- arecordofthe computationincaseoffuturedisputes. (cid:12)cation), and then runs an agentontheir behalf. The codeusedfortheagentcanbepublicsothatcustomers 4 P4P: Paranoid Platform for Privacy gaintrustinthe providedservices. Evenifthe agency Preferences is trusted, individuals can still cheat in various ways, but atleastorganizationsareabletogoto the agency We have illustrated through examples a set of infor- for help in resolving con(cid:13)icts that may arise. mation types where an individual can retain control As far as Ellen is concerned, her agent is a part over his information. We claim that for each such in- of the agency. Thus the mappings of its personas are formation type, one can devise a general-purpose set knownonlytotheagency,andneednotberevealedto ofmechanismstoretaincontrol. Weproposetogather Dr. Bones. DealsRusstillhasto revealitspredicate p thesesetofmechanismsintooneframework,whichwe to the agency. All parties now have to trust only one call P4P: Paranoid Platform for Privacy Preferences. organizationand need to rely on its P3P promises. We believe that private information can be classi- (cid:12)ed along three dimensions: (a) ownership, (b) func- 3.4 Multi-Source Value Predicates tion, and (c) desired level of control. In this section, weillustratethe abovepropertiesandgleanprinciples The need for parties trusted by individuals and orga- thatcanunderlytheP4Pframework. Wecautionthat nizations becomes more evident if we consider more ourframeworkisstillinitsformativestages,andmany complex scenarios where predicates need values from of our concepts are still not well de(cid:12)ned. di(cid:11)erent sources. To illustrate, consider a bank, Ea- For our illustration, we need to refer to a data syLoan, that needs Fred’s age and salary in order to model, and here we chose a simple entity-attributes determineifitcangivehimaloan. AllthatEasyLoan model, although of course other models are possible. needs is the output of a predicate p(y;s), where y is Fred’s age, and s is his salary. Fred does not want to disclose either attribute to EasyLoan, and Easy- (cid:15) Attribute: As usual, attributes represent the ba- Loan does not trust Fred to compute p(y;s). Fortu- sic building blocks of information, and let us nately, EasyLoan does trust Fred’s employer, Acme, say they are (label, value) pairs. For example, to provide the salary, and Fred’s doctor, Dr. Bones, (name:\Alice") and (address:\123 Main St.") are attributes. To simplify our notation, we will re- to provide the age needed by the computation. How can EasyLoan obtain p(y;s) from values provided by move the quotation marks from string values. Acme and Dr. Bones while Ellen retains control over (cid:15) Entity: An entity has a set of related attributes. her age and salary attributes? We are especially interested in entities that rep- Secure Multi-Party Computation Cryptogra- resent individuals or organizations. For ease of phers have studied ways to evaluate arbitrary func- notation, we will use the term \entity" to refer tionsinadistributedfashion. Thegoalofsecuremulti- to both (a) an individual/organization P in the party computation is to compute a function f(a;b;c) realworld,and (b) the representationof P in our with inputs a, b and c at three di(cid:11)erent parties, such framework as a set of related attributes. For in- that the threepartieslearnonlyf(a;b;c)andnothing stance,Aliceisanentitythatmayberepresented Address (Credit Card, Address purchased a book may be represented by a tu- (Prices) ple <invoiceNo:123, bookTitle: War and Peace>. Grocery List) This tuple is owned by AllMart, not Alice. Even Credit card Inventory Alice AllMart though it was a purchase by Alice, Alice cannot control the information. However, Alice should own the information that links this purchase to Grocery Prices List her,e.g.,the tuple: <invoiceNo: 123,name: Alice, address: 123 Main St.>. Figure 3: Rectangles represent entities, Ovals are at- tributes of entities and Triangles are interactions be- FunctionInordertocontrolinformation,oneneedsto tween entities. know what role it plays vis-a-vis interactions between by the following set of attributes: [Name:Alice, entities. This role can be of the following types, as Address: 123 Main St., Phone: 555-1234]. illustratedbyourexamplesinSection3. Notethatthe same information can be of multiple types, depending Notethatinourworld,attributesbythemselvesare on how it is used in an interaction. For instance, an usuallynotsensitive,e.g.,nobodywillcareifsomeone email address could be a service handle, and it could knows the attribute phone: 555-1234. It is only the also be an identi(cid:12)er. association of phone: 555-1234 and name: Alice with the entity Alice that is sensitive information. Thus, (cid:15) Identi(cid:12)er: Anidenti(cid:12)erisanattribute(orasetof typicallyassociationsof attributeswith anentitymay attributes) that is used to identify an entity in a be considered sensitive information. datastore. Forexample,if Carolgivesherphone numbertoDealsRus,thenDealsRusmayusethat Each entity has a datastore whose contents can be number to refer to Carol in its interactions with classi(cid:12)ed by the data-item’s ownership, function and Carol (or her agent). desired level of control. Each entity also associates a trust level for other entities it deals with, and uses (cid:15) ServiceHandle: Ahandleisanattributethatpro- those trust levels to determine how to interact with vides a path to a service that some other entity them. Each interaction involves exchange of data be- provides on behalf of Alice. Email addresses and tween the participant entities that reveals attributes credit card numbers are examples of service han- of one entity to others. dles. Example [Entity Interaction] Suppose Alice buys (cid:15) Input to Predicate: An attribute is of this type breadandbutteratAllMartusinghercreditcard. The if it can be used as an input to predicates other interaction between Alice and AllMart as seen in our entities wish to evaluate. In our examples, age frameworkisshowninFigure3. Aliceisanentitywith and salary were attributes of this type. attributesaddress,creditcardinformationandagrocery list. Similarly,AllMartisanentitywith attributesad- (cid:15) Copy: Attributes can be copied to another en- dress,inventoryandpricesofgoods. Alice’sinteraction tity’s datastore. In such cases, it is critical to with AllMart reveals information about one entity to track which of the copies is the primary copy (at theother. Thus,Alicemustsharehercreditcardinfor- thesitethatownstheinformation)andwhichare mation and grocery list with AllMart. AllMart must the secondary copies. reveal its prices of goods to Alice. Desired Level of Control This level speci(cid:12)es how OwnershipConsidertheinteractionbetweentwoen- the owner wants the information managed. The level tities,anindividualAliceandanorganizationAllMart. mayvarybyentity,thatis,onelevelmaybedesiredfor The participant entities share data with each other. one entity, and a di(cid:11)erent level for another, probably The data that is shared can be owned by Alice or by dependingonthetrustlevelplacedontheentities(see AllMart. below). Also, the desired level can refer to a set of attributes, since as we have discussed, a subset may (cid:15) By Individual: Thiscategoryincludesdatagener- be moresensitivethanothers. Basedonourexamples atedbyAlice,i.e.,herpersonaldata(e.g.,address) in Section 3, we can list the following useful points in and preferences (e.g., grocery list). The fact that the spectrum: Alice owns this data means that Alice should re- tainfullcontroloverit,decidingwhenandhowit (cid:15) CompletePrivacy: Theinformationshouldnotbe can be revealed to others. revealed at all. (cid:15) By Organization: This category covers data gen- (cid:15) Limited Time/Use: The information can be used erated by AllMart. For instance, say Alice buys for a limited time, or a limited number of times, a particular book there. The fact that someone or for a particular task, as in our email example. (cid:15) No Predicate Input: The information cannot be I. Attribute II. Function III. Level of Control used as input to predicates. We may disallow Image Copy Accountable either single-source or multi-source value predi- Email Service Handle Limited Use cates. Email Identi(cid:12)er No Integration Age Input to Predicate No Input (cid:15) No Integration: The information is given to an entity, but that entity should not be able to in- Table 1: P4P policies de(cid:12)ned by Alice for interactions tegratethatinformationtoothersubsetswehave with DatesRus. given other entities. To enforce this restriction, (cid:15) Isolation: Data provided in two interactions I we need to control the foreign keys we give out. j andI (j 6=k)cannotbeassociatedwiththesame k (cid:15) Accountable: The information is given to an en- entity Alice. tity,butthatentityshouldbeheldresponsiblefor (cid:15) Minimality: Alice ensures that the data that is any misuse of the information in the future. exchangedinaninteractionistheminimaltosuc- (cid:15) Sharable: As we have argued, there are cases cessfully achieve its goals. where we must give information to an entity and To illustrate our proposed taxonomy, let us return hope the entity will protect our data. For this to our sample entity for Alice [Name:Alice, Age: 23, type of sharabledata, we mayspecify what guar- Email: [email protected], Image: myPic.jpg]. Let us as- anteeswemaywantfromtheentity,asintheP3P sumethatAlicewantstosignupwithanonlinedating framework. Forinstance,wemayonlyshareinfor- service called DatesRus, but does not trust DatesRus mationwithanentityifitpromisesnottodivulge with her personal information. Alice may de(cid:12)ne P4P it to third parties, or if it promises to only use it policiesasshowninTable 1togovernherinteractions for computing statistics. withDatesRus. Eachrowinthetableillustratesapol- icy that enables Alice to retain control over her per- Trust As mentioned earlier,in ourframework, an en- sonal information vis-a-vis DatesRus. Column I lists tity also needs to specify the trust it has in other en- examples of attributes over which Alice desires con- tities. There are many ways to specify and manage trol, Column II speci(cid:12)es the attribute’s function, for trust that have been discussed in literature [1, 9, 16]. whichColumnIIIspeci(cid:12)esthelevelofcontroldesired. Given our focus on controlling access to information, We consider each row in more detail next. oneoptionistosimplyspecifypoliciesstatingthelevel of control desired on information released to a target Example [Image 7! Copy 7! Accountable] Alice entity. For example, if an entity is trusted to enforce wantstouploadherimageattheDatesRussite. How- no-integration, then we believe it will not attempt to ever, she is worried about abuses: e.g., DatesRus may integratetheinformationwegiveitwithwhatisavail- sell her image to advertisers without seeking her per- able at other entities. If we trust an entity in this mission. Since she needs to make a copy of the image fashion,thenwedonothavetoimplementprecautions which will be shared with DatesRus, she deems her with the identi(cid:12)ers we give it. attribute image: myPic.jpg to have function: copy and level of control: accountable. Therefore, Alice’s agent Properties of Interaction An unconstrained ex- mustensurethattheimageprovidedsatis(cid:12)esproperty: changeofinformationininteractionscanrevealanen- traceablesothatAlicewill(eventually)obtainproofof tity’s private attribute values to others. We propose DatesRus’ identity. Alice’s agent may watermark [24] that information that is exchanged during an inter- the image to ensure traceability. action be carefully \trimmed" to ensure information privacy. For example, let Alice participate in succes- Example [Email 7! Service Handle 7! Limited Use] sive interactions I1;I2;I3;::: with DealsRus. To en- Alice wants to provide an email address for DatesRus sure Alice’s privacy, we require the following, which toinformherofpossibleinterests. However,Alicedoes we call the TRIM properties, on each interaction: not foresees herself using DatesRus for more than an year. ShedoesnotwantDatesRustocontactheronce (cid:15) Traceability: The data that is exchanged during she ends her membership. So she deems her attribute an interaction I cannot be used by DealsRus for email: [email protected] to have function: service han- j an interaction with another entity, without Alice dle and level of control: limited use. Therefore, Alice’s having proof of DealsRus’ involvement. agentmust ensurethatthe releasedemailaddresssat- is(cid:12)es property: revocable. Alice’s agent may provide (cid:15) Revocability: Alicecan \severe"associationswith a temporary email address that can be invalidated by a particularinteraction in the future (e.g., on ex- Alice at will. piry of a subscription); the attribute values that wassharedinsuch aninteractioncannotbe asso- Example [Email 7! Identi(cid:12)er 7! No Integration] Al- ciated with Alice anymore. ice wants to interact with various organization (e.g., DatesRus, DealsRus, ShipsRus) each of which wants 5.1 Interfaces for Entities and Agents her email address. Alice realizes that her email ad- Adequate programmatic interfaces need to be de(cid:12)ned dressisuniquetoher, andcouldbeusedasheridenti- for entities, agents, agencies, predicate evaluatorsand (cid:12)erby the organizations. She doesnot want(a subset notaries. Agent interfaces for dealing with informa- of) these organizations to get together and integrate tiontypeswillhavegenericandapplicationdependent their datasets without her knowledge. So she deems parts. For example, an agent may be asked to create her attribute email: [email protected] to have function: a service handle that is limited for one day (a generic identi(cid:12)erandlevelofcontrol: nointegration. Therefore, restriction) or a handle that only allowscharges of up Alice’s agent must ensure that the released email ad- to 100 dollars (application speci(cid:12)c for money-related dress satis(cid:12)es property: isolation as well. Alice’s agent handles). Traceable copies of data may require em- may create distinct temporary email addresses, one bedding of application-dependent (cid:12)ngerprints [24]. It each for each organizationto ensure isolation. will be important to explore the types of application- speci(cid:12)c controls and services that would be useful. Example [Age 7! Input to Predicate 7! No Input] DatesRushaspromotionalo(cid:11)ersfromlocalclubs that provides free entry to DatesRus clients under the age 5.2 Human Interfaces of 25. Alice does not want to reveal her age and has Humaninterfacesmustbeinventedthatenablepeople decided to decline any o(cid:11)er that requires her to re- to describe their privacy goals and select appropriate veal her age. So she deems her attribute age: 23 to policies for their agents. The interface must also edu- have function: input to predicate and level of control: catepeopleaboutrisksoftheiroptions. Cantherecent no input. Therefore, Alice’s agent must ensure that workonprivacyinterfacesforubiquitouscomputingbe optional age-based predicates from DatesRus are not useful here? Researchthere has highlighted that indi- evaluated. viduals tend to release information subjectively while weighinginfactorslikeinformationfunction, informa- In summary, in our P4P framework, it is impor- tionsensitivityandtrustinrecipient[3,29]whichmir- tanttounderstandwhocontrols(owns)data,howthe ror our owner - function - level of control dimensions. data is being used (function), what control is desired, Perhaps user-interfaces de(cid:12)ned in the above context and what agents can be trusted. For each type of in- (e.g., SecureID [11]) can be adapted here. formation (a point in the function, ownership, control We havealready noted in Section 3.1 the trade-o(cid:11)s space), our goal is then to provide one or more mech- betweenconvenienceandprivacy. Toolsmust bebuilt anisms that enforce the desired property. that can integrate agents seamlessly with an individ- Inthe P4Pframework,trusted agenciesplayacen- ual’s day-to-day tasks. For example, a web-browser tral role. As illustrated in our examples, they provide toolbar could be built and helps the user obtain tem- agentandpredicateevaluatorservices,sothatentities porary email addresses from his/her agent. cane(cid:11)ectivelycontrolandatthesametimesharetheir Therehasrecentlybeenaninterestinexploringthe information. Eachindividual would contractwith one nature of privacy as a value determined by market or more agencies to provide services, and perhaps to forces [12, 26, 28, 40]. Instead of a declarative policy, store some of their data too. As the individual inter- individuals in this model maybe willing torelaxtheir actswithorganizations,insteadofgivingoutinforma- levelofcontrolinreturnforafaircompensation. How tion directly, it asks its agent to provide appropriate cansuchschemesbeincorporatedintheinterface,and attributes, whethertheybe privateemailaddressesor indeed, the framework? private identi(cid:12)ers. When an organization needs addi- tional information about an individual, it can contact 5.3 Reasoning about Information Privacy its agent or a trusted agency to obtain the data. While we have presented a few useful points in the 5 Challenges ownership - function - level of control spectrum, it is important to specify information work(cid:13)owsfora vari- We have sketched our vision for an information pro- ety of interactions and formally reason about privacy cessing world where individuals can retain, whenever guaranteesas an aggregateof an entity’s interactions. possible,controlovertheirinformation. Organizations Suppose that an entity could log all interactions it can also bene(cid:12)t by not getting control, and the liabil- participated in with other entities. How would such ity that goes with it, of information they do not own. logs augment agent services? The agent can now use Thisinformationprocessingmodelwillrequirethator- an entity’s log to pre-process (or even abort) current ganizations and individuals operate with information interactionstopreventviolationoftheentity’sprivacy in di(cid:11)erent ways (e.g., through agents, use TRIM in- policies. Forexample,Alice’sagentmayraiseanalarm teractions, etc.). Of course, the challenges to achieve ifasequenceof predicatesreceivedinsuccessiveinter- this vision are huge, and in closing we mention a few. actions with DealsRus are of the form y ==A? true :