Information Technology Reference
In-Depth Information
5.5.2
Distributed Computation of Pareto-optimal SNE
The Pareto-optimal SNE computed by Algorithm 2 can be achieved in a distributed
manner. To this end, each user first obtains its potential anonymity set and its social
tie levels with others. Following Algorithm 2, each user checks if it should change
its strategy according to the condition in line 5 or 10 based on other users' strategies,
and if yes, announces the change to all users. With time divided into slots, a random
backoff mechanism can be used so that at most one user announces a change of
strategy in a time slot. If no user announces a change, it indicates the end of phase
I or phase II in Algorithm 2. Therefore, all users keep aware of the current state of
the algorithm as it proceeds, and thus can act correctly according to the algorithm.
The computational complexity of the distributed version of Algorithm 2 is almost
the same as the centralized version, and is upper bounded by
O
(
n
3
). Note that each
user only knows the strategies of other users during the execution the algorithm, and
thus users' privacy is preserved. After reaching the Pareto-optimal SNE, the users
who decide to change their pseudonyms coordinate their pseudonym changes.
5.5.3
Further Discussions
We assume that there is a third party platform where users interact with each other
to make pseudonym change decisions and coordinate their pseudonym changes.
The platform only serves to allow information exchanges among users (e.g., an
online chat service [
10
,
11
]). We assume that the platform is honest-but-curious such
that it honestly delivers messages among users, but is curious about users' private
information. To protect privacy, each user also uses a pseudonym as its identity on
the platform (which can be different from that used for the LBS). To make a socially-
aware pseudonym change decision, each users needs to know its potential anonymity
set and its social tie levels with others. This can be achieved in a privacy-preserving
manner using secure protocols as discussed below. Note that the platform is not
involved in the computing tasks of these protocols.
A user can learn whether another user is within its anonymity range using a
certain private proximity detection protocol [
12
,
13
]. For example, the protocol
proposed in [
12
] can be used if the anonymity range is a disk. Specifically, the
protocol involves several message exchanges between the two users, including one
message that contains encrypted values that are functions of a user' location or
the radius of the anonymity range. The protocol guarantees that both users can
only learn the binary result of whether or not one is in another's anonymity range,
and neither user can learn the other's location or anonymity range. In addition,
since location information is encrypted in the messages, the platform cannot learn
any user's location information. Similarly, the protocol in [
13
] can be used if the
anonymity range is a convex polygon. Therefore, each user can learn its potential
anonymity set without revealing its location information.
