Coprivacy: an introduction to the theory and applications of co-operative privacy

Statistics & Operations Research Transactions SORT Special issue: Privacy in statistical databases, 2011, 25-40 Statistics & Operations Research Transactions c Institut d’Estad´ ıstica de Catalunya [email protected] ISSN: 1696-2281 eISSN: 2013-8830 www.idescat.cat/sort/ Coprivacy: an introduction to the theory and applications of co-operative privacy Josep Domingo-Ferrer∗ Universitat Rovira i Virgili Abstract We introduce the novel concept of coprivacy or co-operative privacy to make privacy preservation attractive. A protocol is coprivate if the best option for a player to preserve her privacy is to help another player in preserving his privacy. Coprivacy makes an individual’s privacy preservation a goal that rationally interests other individuals: it is a matter of helping oneself by helping someone else. We formally define coprivacy in terms of Nash equilibria. We then extend the concept to: i) general coprivacy, where a helping player’s utility (i.e. interest) may include earning functionality and security in addition to privacy; ii) mixed coprivacy, where mixed strategies and mixed Nash equilibria are allowed with some restrictions; iii) correlated coprivacy, in which Nash equilibria are replaced by correlated equilibria. Coprivacy can be applied to any peer-to-peer (P2P) protocol. We illustrate coprivacy in P2P anonymous keyword search, in content privacy in social networks, in vehicular network communications and in controlled content distribution and digital oblivion enforcement. MSC: 91A26, 91A40, 68P20, 94A60 Keywords: Data privacy, game theory, anonymous keyword search, content privacy in social networks, vehicular networks, content distribution, digital oblivion. 1. Introduction The motivation of the coprivacy concept and its incipient theory presented in this paper is one of double sustainability in the information society: 1. Privacy preservation is essential to make the information society sustainable just as environment preservation is essential to make the physical world sustainable. *Universitat Rovira i Virgili, UNESCO Chair in Data Privacy, Department of Computer Engineering and Mathematics, Av. Pa¨ ısos Catalans 26, E-43007 Tarragona, Catalonia. [email protected] Received: November 2010 Accepted: March 2011 26 Coprivacy: an introduction to the theory and applications of co-operative privacy This idea, which we already introduced in Domingo-Ferrer (2009) and in the conference paper Domingo-Ferrer (2010) which this article extends, should lead to clean information and communications technologies (ICT) offering functionality with minimum invasion of the privacy of individuals. Such an invasion can be regarded as a virtual pollution as harmful in the long run to the moral welfare of individuals as physical pollution is to their physical welfare. A parallel of climate change is an information society with dwindling privacy, where everyone is scared of using any service at all. Just as people’s views on environment preservation have changed (they now care about environment, they require and pay for green products, etc.) and this has forced companies to change to green, the same change is happening now regarding privacy. 2. Privacy preservation itself should be sustainable, and be achieved as effortlessly as possible as the result of rational co-operation rather than as an expensive legal requirement. Indeed, even if privacy was acclaimed as a fundamental right by the United Nations in article 12 of the Universal Declaration of Human Rights (1948), relying on worldwide legal enforcement of privacy is nowadays quite unrealistic and is likely to stay so in the next decades. However, unlike law, technology is global and can enforce privacy worldwide, provided that privacy is achieved as the result of rational cooperation. This is the objective of the coprivacy concept and theory presented in this paper. Two major pollutants of privacy are privacy-unfriendly security and privacy-unaware functionality. Privacy-unfriendly security refers to the tendency of sacrificing privacy with the excuse of security. This is partly justified by the global threat of international terrorism. With that argument, Western states have adopted shock measures on information security. Beyond the sheer technological challenge of mass-scale communications security and analysis, a new, subtler and unaddressed challenge arises: security must be increased with minimum privacy loss for the citizens. The current trend is to sacrifice privacy for alleged security: disputably, governments track phone calls, emails and, as seen in the Wikileaks case, social media interactions. In the private sector, privacy-unfriendly security is also present: more and more often, biometrics is enforced on customers with the argument of fighting identity theft. Privacy-unaware (let alone privacy-unfriendly) functionality is illustrated by search engines (Google, Yahoo, etc.), social networks, Web 2.0 services (e.g. Google Calendar, Streetview, Latitude) and so on, which concentrate on offering enticing functionality for users while completely disregarding their privacy. At most, privacy vs third parties is mentioned, but not privacy of the user vs the service provider itself, who becomes a big brother in the purest Orwellian sense. Josep Domingo-Ferrer 27 1.1. Contribution and plan of this paper The environmental analogy above can be pushed further by drawing inspiration on the three “R” of environment: reducing, reusing and recycling. Reducing Re-identifiable information must be reduced. This is the idea behind database anonymization: e.g. k-anonymization (Samarati 2001) by means of microdata masking methods (e.g., Domingo-Ferrer, Seb´ e and Solanas (2008)) reduces the informational content of quasi-identifiers. Reduction is also the idea behind ring and group signatures (Chaum and Van Heyst 2006, Groth 2007), which attempt to conciliate message authentication with signer privacy by reducing signer identifiability: the larger the group, the more private is the signer. Just as in the environment there are physical limits to the amount of waste reduction, in the privacy scenario there are functionality and security limits to reduction: completely eliminating quasi-identifiers dramatically reduces the utility of a data set (functionality problem); deleting the signature in a message suppresses authentication (security problem). A useful lesson that can be extracted from reduction is privacy graduality: privacy preservation is not all-or-nothing, it is a continuous magnitude from no privacy to full privacy preservation. Reusing The idea of reusing is certainly in the mind of impersonators mounting replay attacks, but it can also be used by data protectors to gain privacy. Such is the case of re-sampling techniques for database privacy: an original data set with Nrecords is re-sampled Mtimes with replacement (where Mcan be even greater than N) and the resulting data set with Mrecords is released instead of the original one. This is the idea behind synthetic data generation via multiple imputation (Rubin 1993). Re-sampling is also the idea of the tabular protection method in (Domingo- Ferrer and Mateo-Sanz (1999). However, as it happened for reduction there are functionality limitations to data reuse: the more reuse, the less data utility. Recycling The idea of recycling is probably more intriguing and far less explored than reducing and reusing. Adapted to the privacy context, recycling can be regarded as leveraging other people’s efforts to preserve their privacy to preserve one’s own privacy. The environmental analog would be to share a car with other people: we leverage the other people’s wish to save fuel to save fuel ourselves. Of course, whether in the privacy or the environment scenario, there is a functionality toll to this kind of recycling: one must adjust to the needs of other people. Nonetheless, we believe that recycling has an enormous potential in privacy preservation, as it renders privacy an attractive and shared goal, thereby making it easier to achieve and thus more sustainable. In this spirit, we next introduce a new recycling concept, called coprivacy, around which this proposal is centered. 28 Coprivacy: an introduction to the theory and applications of co-operative privacy Section 2 gives some background on game theory. Section 3 gives a game-theoretic definition of coprivacy and some of its generalizations. Section 4 illustrates coprivacy in the context of peer-to-peer (P2P) anonymous keyword search. Section 5 illustrates correlated coprivacy applied to content disclosure in social networks. Section 6 shows how general coprivacy applies to vehicular networks. Section 7 sketches how coprivacy can help enforcing controlled content distribution and digital oblivion. Section 8 summarizes conclusions and open research issues. A preliminary conference version of this paper appeared in Domingo-Ferrer (2010). 2. Basics of game theory A game is a protocol between a set of N players,{1,...,N}. Each player ihas her own set of possible strategies, say Si. To play the game, each player iselects a strategy si∈Si. We will use s= (s1,...,sN)to denote the vector of strategies selected by the players and S=ΠiSito denote the set of all possible ways in which players can pick strategies. The vector of strategies s∈Sselected by the players determines the outcome for each player, which can be a payoff or a cost. In general, the outcome will be different for different players. To specify the game, we need to give, for each player, a preference ordering on these outcomes by giving a complete, transitive, reflexive binary relation on the set of all strategy vectors S. The simplest way to assign preferences is by assigning, for each player, a value for each outcome representing the payoff of the outcome (a negative payoff can be used to represent a cost). A function whereby player iassigns a payoff to each outcome is called a utility function and is denoted by ui:S−→ R. For a strategy vector s∈S, we use sito denote the strategy played by player iand s−ito denote the (n−1)-dimensional vector of the strategies played by all other players. With this notation, the utility ui(s)can also be expressed as ui(si,s−i). A strategy vector s∈Sis a dominant strategy solution if, for each player iand each alternate strategy vector s′∈S, it holds that ui(si,s′ −i)≥ui(s′ i,s′ −i)(1) In plain words, a dominant strategy sis the best strategy for each player i, independently of the strategies played by all other players. A strategy vector s∈Sis said to be a Nash equilibrium (Nash 1951) if, for all players iand each alternate strategy s′ i∈Si, it holds that ui(si,s−i)≥ui(s′ i,s−i) In plain words, no player ican change her chosen strategy from sito s′ iand thereby improve her payoff, assuming that all other players stick to the strategies they have chosen in s. A Nash equilibrium is self-enforcing in the sense that once the players Josep Domingo-Ferrer 29 are playing such a solution, it is in every player’s best interest to stick to her strategy. Clearly, a dominant strategy solution is a Nash equilibrium. Moreover, if the solution is strictly dominant (i.e. when the inequality in Expression (1) is strict), it is also the unique Nash equilibrium. See Nisan, Roughgarden, Tardos and Vazirani (2007) for further background on game theory. 3. Coprivacy and its generalizations We introduce in this section the novel concept of coprivacy in a community of peers, whereby one peer recycles to her privacy’s benefit the efforts of other peers to maintain their own privacy. Informally, there is coprivacy when the best option for a peer to preserve her privacy is to help another peer in preserving his privacy. The great advantage isthatcoprivacymakes privacy preservationofeach specific individual a goal that interests other individuals: therefore, privacy preservation becomes more attractive and hence easier to achieve and more sustainable. A game-theoretic formalization of coprivacy follows. Definition 1 (Coprivacy) Let Πbe a game with self-interested, rational peer players P1,...,PN, and an optional system player P0. Each player may have leaked a different amount of private information to the rest of players before the game starts. The game is as follows: i) P1selects one player Pkwith k ∈ {0}∪{2,···,N}and submits a request to Pk; ii) If k =0, P0always processes P1’s request; if k >1, Pkdecides whether to process P1’s request (which may involve accessing the system player on P1’s behalf) or reject it. The players’ strategies are S0={s0 1}(process P1’s request); S1={s1 0,s1 2,···,s1 N}, where s1 jmeans that P1selects Pj; for i >1, Si={si 1,si 2}, where si 1means processing P1’s request and si 2rejecting it. Game Πis said to be coprivate with respect to the set U= (u1,···,uN)of privacy utility functions if, for some k >1, a peer Pkexists such that (s1 k,sk 1)is a pure strategy Nash equilibrium between P1and Pk, that is, if the best strategy for P1is to request help to Pkand the best strategy for Pkis to provide the requested help. Note that the notions of privacy utility function and therefore of coprivacy are based on the aforementioned privacy graduality: one can have a varying degree of privacy preservation, hence it makes sense to trade it off. In the environmental analogy, coprivacy is a recycling concept which involves trading off waste reduction among players. A quantification of coprivacy follows: Definition 2 (δ δ δ-Coprivacy) Given δ∈[0,1], the game of Definition 1 is said to be δ-coprivate with respect to the set U = (u1,···,uN)of privacy utility functions if the probability of it being coprivate for U is at least δ. 30 Coprivacy: an introduction to the theory and applications of co-operative privacy The following extensions of coprivacy are conceivable: •General coprivacy can be defined by replacing the set Uof privacy utility functions in Definition 1 with a set Uof general utility functions for peer players Pkcombining privacy preservation with security and/or functionality. In general coprivacy, the interests of peers include, in addition to privacy, functionality and/or security. •General δ δ δ-coprivacy can be defined by replacing Uwith Uin Definition 2. •Mixedcoprivacyresults ifoneallowsmixed strategiesforplayersandreplacesthe requirement of pure strategy Nash equilibrium in Definition 1 by a mixed strategy Nash equilibrium. The good point of mixed coprivacy is that a theorem by Nash (Nash 1951) guarantees that any game with a finite set of players and a finite set of strategies has a mixed strategy Nash equilibrium, and is therefore mixedly coprivate. •Correlated coprivacy results if one replaces the requirement of pure Nash equilibrium in Definition 1 by a correlated equilibrium. Indeed, the outcome of independent rational behavior by users, provided by Nash equilibria, can be inferior to a centrally designed outcome. Correlated equilibria resulting from coordination of strategies may give a higher outcome. We will illustrate this in Section 5 below. In correlated equilibria, players do not have any incentive to deviate from their corresponding equilibrium strategies. An approximation to correlated equilibria are ǫ-correlated equilibria, in which players have at most an incentive ǫ>0 to deviate from their corresponding equilibrium strategies. The advantage of ǫ-correlated equilibria is that they can always be reached by distributed heuristics run by a set of autonomous players without centrally designed strategies. •The above extensions can be combined to yield mixed general coprivacy and correlated general coprivacy. Since mixed coprivacy is always achievable if any mixed strategy is valid for any player, mixed δ δ δ-coprivacy and mixed general δ δ δ-coprivacy only make sense when players have boundary conditions that define a subset of feasible mixed strategies. Acoprivate protocol is a protocol based on a coprivate game. If a privacy preservation problem can be solved by a coprivate protocol, the advantage is that it is in a player’s rational privacy interest to help other players to preserve their privacy. We next give an example to show that the coprivacy concept is latent in existing protocols. More examples of the potential of coprivacy follow in the next sections. Example 1 (Coprivacy in anonymous communication) The success of the well-known system Tor (http://www.torproject.org) for anonymous communication, made even more famous by Wikileaks, can be explained by coprivacy. As hinted in the Tor website, “each new user and relay provides additional diversity, enhancing Tor’s ability to put control over your security and privacy back into your hands”. Therefore, using Tor is not only good for one’s own privacy, but for other people’s privacy as well. Josep Domingo-Ferrer 31 4. Coprivacy in P2P anonymous keyword search Private information retrieval (PIR) is normally modeled as a game between two players: a user and a database. The user retrieves some item from the database without the latter learning which item was retrieved. Most PIR protocols are ill-suited to provide PIR from a search engine or large database, not only because their computational complexity is linear in the size of the database, but also because they (unrealistically) assume active cooperation by the database in the PIR protocol. Pragmatic approaches to guarantee some query privacy have therefore been based so far on two relaxations of PIR: standalone and peer-to-peer (P2P). In the standalone approach, a program running locally in the user’s computer either keeps submitting fake queries to cover the user’s real queries (TrackMeNot, Howe and Nissenbaum 2009)) or masks the real query keywords with additional fake keywords (GooPIR, Domingo- Ferrer, Solanas and Castell` a-Roca 2009)). In the P2P approach, a user gets her queries submitted by other users in the P2P community; in this way, the database still learns which item is being retrieved, but it cannot obtain the real query histories of users, which become diffused among the peer users, thereby achieving anonymous keyword search. We first proposed a P2P anonymous keyword search system in Domingo-Ferrer, Bras-Amor´ os, Wu and Manj´ on (2009). Consider a system with Npeers P1to PN, who are interested in querying a database DB playing the role of system player P0. If any Pioriginates a query for submission to DB, she can send the query directly to DB or ask some other peer to submit the query on Pi’s behalf and return the query results. More formally, the strategies available for a requesting Piare: Sii:Pisubmits her query directly to DB; Sij:Piforwards her query to Pj, for some j6=i, and requests Pjto submit the query on Pi’s behalf. When receiving Pi’s query, Pjhas two possible strategies: T ji:Pjsubmits Pi’s query to DB and returns the answer to Pi; T jj:Pjignores Pi’s query and does nothing. Let Xi(t)be the set of queries originated by Piup to time t. Let Yi(t)be the set of queries submitted to DB by Piup to time t. For each query xi rin Xi(t), define Fi(xi r,t)as the set of players to whom Pihas forwarded xi rfor submission up to time t. The players in Fi(xi r,t)can be associated relative frequencies as follows: for j=1 to Nwith j6=i, let fij(xi r,t)be the relative frequency with which Pihas forwarded xi rto player Pj, up to time t. The privacy utility function for Pishould reflect the following intuitions: (i) the more homogeneous the relative frequencies of queries in Yi(t), the more private stay 32 Coprivacy: an introduction to the theory and applications of co-operative privacy the interests of Pivs DB; (ii) the more homogeneous the relative frequencies of peers in Fi(xi r,t)for every xi r∈Xi(t), the more private stay the interests of Pivs the other peers. Givenarandomvariable Ztaking values z1,z2,...,znwithprobabilities p1,p2,...,pn, respectively, Shannon’s entropy (Shannon 1948) is a measure of uncertainty defined as H(Z) = − n ∑ i=1 pilog2pi The more homogeneous the pi, the higher is H(Z): the rationale is that the outcome of Zbecomes more uncertain as the pibecome more homogeneous. The maximum H(Z) is reached when p1=···=pn=1/n. By assimilating Yi(t)and Fi(xi r,t)to random variables and relative frequencies to probabilities, intuition (i) above can be expressed as maximizing H(Yi(t)) and intuition (ii) as maximizing H(Fi(xi r,t)) for all xi r∈Xi(t). Hence, those Shannon entropies are reasonable privacy utility functions for Pi. When Pigenerates a query xi rat time t+1: •Pichooses Sii (direct submission) if H(Yi(t+1)) ≥H(Yi(t)), where Yi(t+1) = Yi(t)∪{xi r}; •Otherwise Pichooses Sik (forwarding the query to Pk), where k=arg max j∈{1,·,N}\{i}H(Fi(xi r,t+1)).(2) In plain words, if direct submission decreases privacy vs DB, the query is forwarded to the player Pkvs whom the privacy loss is minimum. Note that if Piforwards her query to a player Pj,Pialways incurs some privacy loss vs Pj, because Pjknows the query has been generated by Pi. Therefore, the best policy is to distribute the successive submissions of a certain query xi ras evenly as possible among the various peers. This is what the choice of kin Expression (2) attempts. When Pkreceives xi r, it proceeds as follows: •Pkchooses Tki (submitting xi r) if H(Yk(t+1)) >H(Yk(t)), where Yk(t+1) = Yk(t)∪{xi r}; •Otherwise Pkchooses Tkk (ignoring xi r). In plain words, Pksubmits xi ronly if doing so increases her privacy vs the DB. If Pk ignores xi r, then Piwill have to look for a second best player to submit xi r(and a third best if the second best ignores xi r, and so on). If, after a number of attempts to be decided by Pi, no peer is found who is willing to help, then Pimust submit xi rherself. If Pi’s best strategy is Sik and Pkbest strategy is Tki, then (Sik,Tki)is a pure-strategy Nash equilibrium between Piand Pkand there is coprivacy between Piand Pk. We giveadetailedformalizationandempiricalresultsforthe N-player P2P anonymous keywordsearchgameinthemanuscript Domingo-Ferrer and Gonz´ alez-Nicol´ as (2011). Josep Domingo-Ferrer 33 5. Correlated coprivacy in social networks Social networks (SNs) have become an important web service with a broad range of applications: collaborative work, collaborative service rating, resource sharing, friend search, etc. Facebook, MySpace, Xing, etc., are well-known examples. In an SN, a user publishes and shares information and services. There are two types of privacy in SNs: •Content privacy. The information a user publishes clearly affects her privacy. Recently, a privacy risk score (Liu and Terzi 2009) has been proposed for the user to evaluate the privacy risk caused by the publication of a certain information. Let the information attributes published by the users in an SN be labeled from 1 to n. Then the privacy score risk of user jis PR(j) = n ∑ i=1 ℓ ∑ k=1 βik ×V(i,j,k) where V(i,j,k)is the visibility of user j’s value for attribute ito users which are at most klinks away from jand βik is the sensitivity of attribute ivs those users. •Relationship privacy. In some SNs, the user can specify how much it trusts other users, by assigning them a trust level. It is also possible to establish several types of relationships among users (like “colleague of”, “friend of”, etc.). The trust level and the relationship type are used to decide whether access is granted to resources and services being offered (access rule). The availability of information on relationships (trust level, relationship type) has increased with the advent of the Semantic Web and raises privacy concerns: knowing who is trusted by whom and to what extent discloses a lot about the user’s thoughts and feelings. For a list of related abuses see Barnes (2006). In Domingo-Ferrer, Viejo, Seb´ e and Gonz´ alez- Nicol´ as (2008), we described a new protocol offering private relationships in an SN while allowing resource access throughindirect relationships without requiring a mediating trusted third party. We focus here on content privacy in SNs. A possible privacy-functionality score for user jreflecting the utility the user derives from participating in an SN is PRF(j) = ∑N j′=1,j′6=j∑n i=1∑ℓ k=1βikV(i,j′,k)I(j,j′,k) 1+PR(j) =∑N j′=1,j′6=j∑n i=1∑ℓ k=1βikV(i,j′,k)I(j,j′,k) 1+∑n i=1∑ℓ k=1βikV(i,j,k) where I(j,j′,k)is 1 if jand j′are klinks away from each other, and it is 0 otherwise. 40 Coprivacy: an introduction to the theory and applications of co-operative privacy Liu, K. and Terzi, E. (2009). A framework for computing the privacy scores of users in online social networks, in Proc. of ICDM 2009-The 9th IEEE International Conference on Data Mining, 288– 297. Mayer-Sch¨ onberger, V. (2009). The Virtue of Forgetting in the Digital Age, Princeton University Press. Nash, J. (1951). Non-cooperative games, Annals of Mathematics, 54, 289–295. Nisan, N., Roughgarden, T., Tardos, ´ E. and Vazirani, V. V. eds. (2007). Algorithmic Game Theory, Cambridge University Press. Pfitzmann, B. and Waidner, M. (1997). Anonymousfingerprinting,in Advances in Cryptology-EUROCRYPT 1997, Springer, LNCS 1233, 88–102. Raya, M., Aziz, A. and Hubaux, J.-P. (2006). Efficient secure aggregation in VANETs, in Proc. of 3rd Intl. Workshop on Vehicular Ad Hoc Networks-VANET, 67–75. Rubin, D. B. (1993). Discussion on statistical disclosure limitation, Journal of Official Statistics, 9, 461– 468. Samarati, P. (2001). Protecting respondents’ identities in microdata release, IEEE Transactions on Knowledge and Data Engineering, 13, 1010–1027. Shannon, C. (1948). A mathematical theory of communication, Bell Systems Technical Journal, 27, 379– 423 and 623–656. Tardos, ´ E. and Vazirani, V. V. (2007). Basic solution concepts and computational issues, in N. Nisan, T. Roughgarden, ´ E. Tardos and V. V. Vazirani (eds.), Algorithmic Game Theory, Cambridge University Press, 3–28. Wu, Q., Mu, Y., Susilo, W., Qin, B. and Domingo-Ferrer, J. (2009). Asymmetric group key agreement, in Advances in Cryptology-EUROCRYPT 2009, Springer, LNCS 5479, 153–170.