Is Privacy possible without Anonymity?
The case for microblogging services
Panagiotis Papadopoulos∗

Antonis Papadogiannakis∗

Brave Software
panpap@brave.com

ProtectWise, USA
apapadog@gmail.com

Michalis Polychronakis

Evangelos P. Markatos

Stony Brook University, USA
mikepo@cs.stonybrook.edu

FORTH-ICS, Greece
markatos@ics.forth.gr

ABSTRACT
Traditional approaches to privacy are usually based on top ofanonymizing or pseudonymizing systems. For example, users who
would like to protect their identity and/or hide their activities whilebrowsing the web frequently use anonymizing systems (e.g., Tor) or
services (e.g., VPNs and proxies). Although anonymizing systems
are usually effective, recent revelations suggest that anonymization
can be compromised and can be used to provide a false sense of
security. In this paper we assume a world where anonymizationis (practically) not possible. Imagine, for example, a community
where the use of anonymizing systems is frowned upon or evenforbidden. Is it possible for users to protect their privacy when they
can not hide their identity?
In this paper, we focus our question on users interested in following information channels in microblogging services and we showthat it is possible for users to protect their privacy even if they can
not hide their identity. To do so, we propose two obfuscation-basedalgorithms and quantify their effectiveness. We show that obfuscation can be used in such a way so that attackers can not use thisservice to increase their a priori knowledge on whether a user isinterested in a channel or not.

KEYWORDS
Obfuscation, Anonymous Subscription, User Interests
ACM Reference Format:
Panagiotis Papadopoulos, Antonis Papadogiannakis[1], Michalis Polychronakis, and Evangelos P. Markatos. 2019. Is Privacy possible without Anonymity?
The case for microblogging services. In 12th European Workshop on Systems
Security (EuroSec ’19), March 25–28, 2019, Dresden, Germany. ACM, New
York, NY, USA, 6 pages. https://doi.org/10.1145/3301417.3312498

1

INTRODUCTION

Over the past few years we have seen an increase in the deployment
and use of microblogging services and news aggregators. Indeed,∗ Work was conducted when authors were in FORTH-ICS

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
EuroSec ’19, March 25–28, 2019, Dresden, Germany© 2019 Association for Computing Machinery.
ACM ISBN 978-1-4503-6274-0/19/03. . . $15.00
https://doi.org/10.1145/3301417.3312498

these aggregators have become very popular, because they provide
timely information in short (280-characters-long) nuggets that canbe quickly scanned, tailored, absorbed, and shared. As a result of
this popularity, an increasing number of users choose to receive
their news through such microblogging services such as Twitter,
Tumblr, Weibo, Tout, and many more.
Although useful, this timely and personalized information delivery by microblogging services may raise significant privacy concerns. For example, if a user follows a channel of a political party,
these microblogging services may be able to infer the user’s politicalbeliefs. If the user follows a channel dealing with a particular healthproblem, the microblogging services may be able to infer that theuser is interested in this health problem, or, to make matters worse,that the user is suffering from it. As a result, an adversary who hasaccess to the information provided to microblogging services may
easily be able to figure out what the users are interested in, basedon the types of channels they follow.
To protect their privacy, users may choose to hide their real
identity by creating and using a fake account. Although such a fakeaccount may give a sense of privacy through pseudonynity, previous
research suggests that fake accounts may be traced back to the real
identities of their users [9, 24]. To make matters worse, third-party
ad networks and tracking services [14, 18, 19] can also be used toreveal the real identity of the user. To protect their privacy evenfurther, in addition to using a fake account, sophisticated users may
choose to connect to the Internet through an anonymizing proxyor an anonymizing network such as Tor [4]. Indeed, anonymizing
networks have been shown to be very effective at hiding the IP
address of their users. Unfortunately, recent attacks have shownthat despite the user of an anonymizing networks, users may stillbe identified through their browser “fingerprint” [6] or throughother characteristics of their device, such as their clock drift rate
[13] or their battery drain rate [15]. Even if one manages to hide
all identifying characteristics of a device, microblogging services
may simply reveal the identity of their users by simply requiringthem to log in, much like Facebook does today.
In this paper, instead of joining the arms race between anonymizing networks and their adversaries, we take a slightly different pointof view by addressing the following question: “Let us assume a world
where anonymity is (practically) not possible. Can we still protect
the privacy of users of a microblogging service?” We believe that theanswer to the above question is yes: we believe that even if theuser is not able to hide her real identity, she is able to hide her realinterests. One way to do this is by using obfuscation: that is, sheEuroSec ’19, March 25–28, 2019, Dresden, Germany
will subscribe to more channels than those she is really interestedin, making it difficult for an adversary to find out what her realinterests are. By subscribing to more channels that she is reallyinterested in, the user adds noise, protecting, essentially, her realinterests. At this point we must admit that adding noise, or obfuscating, is not a new idea: it has already been used in loyalty cards, inhiding web searches [2], and even in microblogging services [21].
Despite having been studied and deployed in the past, adding
noise is easier said than done. Indeed, recent work has shown that
previous obfuscation approaches have been very ineffective [8]. We
believe that two are the main issues behind for this ineffectiveness:(i) I1: selecting noise: It is not clear how to select noise. Naive
approaches to noise selection (such as adding random channels
or issuing random queries) eventually lead to countermeasures
which are able to remove such added random noise, and (ii) I2:
correlation attacks: The longer a user interacts with a system,
the more information she reveals. As a result, the system might beable to launch what in web searches is called a linkage attack [8],or what we describe later as a correlation attack.
To deal with the first of the issues above (i.e. selecting noise) wedeveloped an analytic model which enables us to explore how muchnoise is needed to hide the fact that the user (say U ) is interested
in following a given channel (say S). Our analytic model uses aninformation-theoretic approach: we assume that the adversary hassome a priori knowledge about how possible it is for user U tofollow channel S (say PU (S)). In order to hide that U is interested in
S, our model argues that we should add ⌈1/PU (S)⌉ noise channels.
In addition to describing how much noise we need to add, section
3.1 describes an algorithm that computes what kind of noise needs
to be added. Indeed, adding randomly chosen channels may seemreasonable, but it is not enough. Random noise can be easily filteredout.
Dealing with the second of the issues identified above (i.e. I2:
correlation attacks) is much tricker. In a correlation attack, theadversary observes what channels the user is following over time(even if the real channels are obfuscated in a bundle of noise), andtries to find which of them are correlated. The intuition of theattacker is that the channels user U is really interested in willprobably be correlated, while the channels that were added asnoise were probably not correlated. Thus, if the adversary finds
correlated channels, then the user is probably interested in theircommon theme. For example, if the user follows a channel on
alcoholics anonymous (along with a bundle of noise channels) andthen a channel on rehab clinics (along with another bunch of noisechannels), and then a channel on substance abuse (along again
with other noise channels), the adversary may safely conclude
that U is interested in alcoholism-related issues. This is because
these alcoholism-related channels seem highly correlated among
themselves, while the noise channels, would probably not be sostrongly correlated (if at all). To deal with such correlation attacks
we develop an analytic approach based on conditional probabilities.
The approach models the information available for a correlation
attack and later leads to an algorithm that chooses appropriate noise
so as to make the correlation attack very difficult, it not completely
impossible.
To summarize, our work makes the following main contributions:

Panagiotis Papadopoulos et al.
(1) We explore the following question: In a world where anonymity
is practically not possible, can we protect the privacy of usersof microblogging services? i.e. can we efficiently hide theirinterests?
(2) We propose SMOKE: an obfuscation-based approach to preserve the privacy of the users’ interests in microblogging
services. Our approach aims to hide a sensitive channel theuser is interested in inside other channels that act as noise.
(3) We propose an analytic approach and a subsequent algorithm
that computes the optimal amount and the type of noise thatshould be added: too little noise leaves the user exposed, while
too much noise is deemed unnecessary.
(4) We show that users who follow a sequence of channels may
be subject to correlation attacks. We describe the attack andpropose an analytical model that evaluates these correlations
based on conditional probabilities. Based on the model, we
propose an algorithm which adds appropriate noise that is
not subject to these correlation attacks.

2

THREAT MODEL

We assume the existence of a service that enables users to receive
personalized news about their topics of interest. Such services
include news aggregators and RSS readers like Digg, Apple News,
Google News or microblogging services like Twitter, Tout, Tumblr,
Weibo. In these services the users are able to subscribe themselves
to individual channels or domains that distribute content about
various topics. In microblogging services these channels can be
accounts of physical persons, of entities such as corporations, ofnews sites, of public figures like actors, of activists, of politicians’
offices, and so on.
By subscribing to these channels the users are able to get in theirtimeline timely information directly delivered from the information sources meeting their interests. On the other hand, the service
operator is capable of recording the users’ interests by observing
which channels each user follows. All information about the users’interests, along with any data aggregated after them is property ofthe service operator and can be later sold to advertisers [3, 22] fortargeted advertising in ad auctions [20] or considered as company’s
assets in case of a service’s future purchase [12]. As a consequence
all this information can be used for a variety of purposes, all ofwhich are beyond the control of individual users. To remedy thispotential infringement of the users’ privacy, we would like to develop mechanisms to enable the users to hide their actual interests
while they consume personalized information.
In this work we assume an “honest but curious” microblogging
service able to find the user’s interests by monitoring the channels
she follows and by mining data produced by the user in order toaggregate and/or correlate any information she provides with heractions inside the web service. On the other hand, we assume that
it will not try to actively interfere with the process users are employing to protect their privacy or try to gain more information
than what a user is willing, or required, to give. We think sucha microblogging service is reasonable in practice, since popular
services have a reputation they do not want to jeopardize by becoming hostile against their own clients. As a result we assume thatthe service will not create any fake channels or fake accounts in

Is Privacy possible without Anonymity?
The case for microblogging services
order to gain any more information than its real users are willingto disclose.
Finally, it is important to note at this point, that in this work
we assume that users act as consumers of information and refrainfrom actively exposing their real interests by posting information,
replying, retweeting, or sharing their interests in any other way.
Recall, that we assume a world where anonymity is (practically)
impossible. Actively sharing one’s interests in such a world leaves
very limited, if any at all, options to protect privacy. 1

3 OUR APPROACH: OBFUSCATION
3.1 Noise selection
When a user wants to follow a channel S, SMOKE instructs theuser’s profile in the microblogging service to follow N other “noise”
channels (say S 1 , S 2 , ..., S N ) as well.
To make sure that we select the right amount and right type ofnoise we introduce two points of view:
A priori knowledge: the adversary has some confidence that
U is interested in S, even before U follows S. This confidence
may be the result of general background information available (e.g. what percentage of people are alcoholics), or evenbackground information available specifically tailored to U
(e.g. what percentage of white males between 40 and 50 are
alcoholics). Let us denote this confidence (that user U ispinterested in following channel S) with PU (S).
A posteriori knowledge: after U follows channel S (along
possibly with some noise channels S 1 to S N ), this new information may produce a new confidence level that U isinterested in S: let us denote this new confidence level withPUa (S). For example, if U follows only S and no noise channels, then this confidence will obviously become 1. Indeed,
if U follows S and only S and does not add any noise, theadversary will be 100% sure that user U is interested in channel S. As another example, if U follows S along with only
one noise channel (say S 1 ), the adversary will know that U
is interested either in S or in S 1 , and thus the a posterioriconfidence will be 0.5: PUa (S) = 0.5. That is, the adversaryis 50% confident that user U is interested in channel S, and
50% confident that user U is interested in channel S 1 .
Framed in this context of a priori and a posteriori knowledge
our approach is at odds with the approach of the adversary: theadversary would like to increase as much as possible the a posterioriconfidence that U is interested in S (i.e. the adversary would likep
to achieve PUa (S) ≫ PU (S)) while we would like to reduce this aposteriori confidence, if possible, to the level where the a posterioriconfidence is no higher than the a priori one: (i.e. we would like topachieve PUa (S) = PU (S)).
3.1.1 How much noise should be added? To make sure that the aposteriori confidence is no higher than the a priori one, we advocatepthat we should add ⌈1/PU (S)⌉ − 1 noise channels. In this way,
the adversary will see that the user U is interested in followingp⌈1/PU (S)⌉ channels (S included in them), and his confidence that
1 One might argue that we can use an obfuscation-based approach to protect users
who post information. Indeed, in such an approach a user would both to channels shefollows and to channels she is not interested in. We are afraid that such an aggressive
approach would lead to information pollution and should probably not be encouraged.

EuroSec ’19, March 25–28, 2019, Dresden, Germany
among all those channels U is interested in S will be PUa (s) =pp1/⌈1/PU (S)⌉ ≈ PU (S). Thus the a posteriori confidence (PUa (s)) willp
be almost equal to the a priori one (PU (S)) and the adversary will
have gained little, if any at all, information. For example, if theadversary is about 10% confident that U is interested in channel S,
possibly based on a priori knowledge that he has (i.e. PUa (S) = 0.1),
our approach will add 9 noise channels and user U will follow a
total of 10 channels (= 9 noise channels plus channel S). Seeing that
U is following 10 channels, the adversary will still be about 10%
confident that user S is a “real” channel (and not a noise channel).
Thus, the a posteriori confidence of the adversary will still be 10%
and will not have increased compared to his a priori confidence.
3.1.2 What kind of noise should be added? As explained above, inorder for the adversary to gain little, if any at all, information, wemust make sure that the confidence that he has that U is interested
in S should be the same as the confidence that he has that U isinterested in S 1 , in S 2 , in S 3 , etc. Obviously, if the adversary knowsthat U is not interested at all in, say S 1 , adding S 1 as noise will not beeffective: the adversary will immediately realize that S 1 is just noise
and U is not interested in S 1 . Therefore, the adversary will be able
to remove at least one noise channel and increase his confidence
level about whether user U is interested in channel S. Therefore,
user U should be interested in following all noise channels withthe same level of interest she is interested in following channel S.
That is, the a priori probability that U is interested in S should be
the same as the a priori probability that U is interested in S 1 , whichshould be the same as the a priori probability that U is interested
in S 2 , etc. Or equivalently:
p

p

p

p

PU (S ) = PU (S 1 ) = PU (S 2 ) = ... = PU (S N )(1)Finding noise channels that satisfy the equation above we force
the adversary to a position where he is unable to determine withaccuracy whether the user is actually interested in channel S or
one of the channels S 1 , S 2 , ..., S N .
As equation (1) above shows, in order to effectively hide thefact that user U is interested in channel S, we need to find N otherchannels (S 1 , S 2 , . . . , S N ) in which the user is equally interested.
Unfortunately, it is not very likely to find exactly N other channelsppppwith all probabilities PU (S), PU (S 1 ), PU (S 2 ), . . . , PU (S N ) exactly
equal to each other. It is more probable to find N noise channels
with probabilities close to each other, but not equal to each other.
In this case, one might be tempted to select the channels with thepprobabilities as close as possible to PU (S) and use them as noise.
To address this issue, one might be tempted to borrow ideas fromk-anonymity [23] and k-subscription [21] and always add a constant number of noise channels. Although possible, such a solution
would not be efficient. Indeed, in some cases k would be too small
increasing the adversary’s confidence that the user is interested inchannel S, and in other cases k might be too large which will add
too much unnecessary noise. Therefore a one-size-fits-all solution(i.e. a constant k) is not appropriate.
Therefore, we introduce a new approach to noise called bucketing. This approach places all channels in buckets. When user U
is interested in following one channel from the bucket, she is requested to follow all channels of this bucket. In this aspect, from theEuroSec ’19, March 25–28, 2019, Dresden, Germany
adversary’s point of view, all channels of the same bucket are indistinguishable: if the user is interested in following any one of them,she is requested to follow all of them. Therefore, the adversary
can not distinguish any of the channels in the bucket: since users
always follow all of them, no matter which individual channel they
are interested in, the adversary can point pinpoint which individual
channel a user is actually interested in.
Placing the channels in buckets is not easy, however. One reason
for this is that the size of each bucket should not be constant; itshould depend on the probability of the channels it contains andmore specifically, on the lowest channel probability contained in
the bucket. For example, if user U interested in channel S with probp
ability PU (S) = 10%, the bucket should contain around 10 channels.
If it contains much less than 10 channels, then the adversary will
be able to increase its a posteriori confidence (that U is interestedin S) well above 10%. On the other hand, if it contains many morethan 10 channels, user U will be forced to follow many more noisechannels than necessary.
To define the buckets our algorithm proceeds as follows:• It orders all channels C according to their a priori probabilityp
PU (C) in decreasing order.
• It constructs the set of channels that have probabilities in
the range [1/2, 1). If there are more than two such channels
it creates buckets of size two. Each bucket contains at least
two channels each of them with probability at least 1/2.
• It then constructs the set of channels that have probabilities
in the range [1/3, 1/2). If there are more than three suchchannels in this range, it creates buckets of size three. If,
however, no three such channels are found, the algorithm
will try to find four channels in the range [1/4, 1/2). 2 If
unsuccessful, it will try to find five channels in the range[1/5, 1/2), and, if unsuccessful, it will try to find six channels
in the range [1/6, 1/2), etc. until it succeeds.
In Algorithm 1 we present the bucket algorithm in pseudocode.
At first we define a range of values: [ k1 , 1i ) and we set as cursor
the left edge (i.e. 1/k). Then, in each step we check if there arek channels that their probabilities are in this range (i.e. [ k1 , 1i ) if not, we increase k and check if there are k channels that theirprobabilities are in this range (i.e. [ k1 , 1i ) - if not, we increase k again
and so on, until we find k channels that their probabilities are in therange [ k1 , 1i . In this way, the bucket algorithm will create a bucketin the field of values [1/k, 1/i) that contain at least k channels.
Let us give another example as well: let’s assume that we havechannels with probabilities P(A) = 0.6, P(B) = 0.55, P(C) = 0.44,
P(D) = 0.37, P(E) = 0.30, and P(F ) = 0.29. Our bucket creation
algorithm will create one bucket in the range [1/2, 1) which will

Panagiotis Papadopoulos et al.
ALGORITHM 1: Bucket creation algorithm#de f ine M 1000 {maximum obfuscation factor}
B=∅
for (i = 1 to M ) dofor (k = i + 1 to M ) do
B = {set of channels with a priori probability in [ k1 , 1i )} ∪B
if (|B | >= k) thenwhile (|B | >= k) do
L = {set of first k channels from B}
newbucket = L
B =B\Lend while
i =k
break
{break the inner k loop and continue with the i loop}
end ifend forend forcontain 2 channels (i.e. A and B). It will then try to find 3 channels
in the range [1/3, 1/2) but it will not succeed (because only twochannels are in this range: channel C and channel D); then, it will
try to find four channels in the range [1/4, 1/2), it will succeed andit will create a bucket with them (i.e. C, D, E, and F ).
After creating the buckets, SMOKE proceeds as follows:
If user U is interested in following channel S which
belongs in bucket B, then U is requested to follow allchannels of bucket B.
Theorem 3.1. When user U is interested in following channel
S, Algorithm 1 places S in such a bucket so that the a posteriori
probability of U being interested in S is not higher than the a priori
probability of U being interested in S.
Proof. Let us assume that user U is interested in following
channel S. Let us also assume that the adversary knows the a prioripprobability PU (S). Let us also assume that there exists an integer lpso that 1/(l + 1) < PU (S) ≤ 1/l. Then Algorithm 1 places channel
S in a bucket with k − 1 channels whose a priori probabilities are
all between 1/k and 1/l. That is,p

1/k < PU (Si ) ≤ 1/lp

P (S )PUa (S) = Ík U p. We need to show that this is less or equal toi =1 PU (S i )p

P (S )

the a priori probability or equivalently Ík U p

i =1 PU (S i )2 The reason for this choice is the following. Let us assume that there are no threechannels in the range [1/3, 1/2]. Let us further assume that there is only one channel
in the range [1/3, 1/2]. Let us assume that we create a bucket that contains only thischannel. If, at some point in the future, the user would be interested to follow thischannel, our system would ask the user to follow all channels of the bucket. Since,
however the bucket contains only one channel, the adversary will be 100% sure thatthe user is interested in this channel . Similarly, if there are only two channels in therange [1/3, 1/2], if we create a bucket out of these two channels, and ask the user
to follow the bucket when the user is interested in either of the channels, then theattacker will know with probability 50% that the user is interested in the channel. Since
the a priori probability was less than 1/2 and the a posteriori probability is 50%, thenthe attacker increased his knowledge with regards to whether the user is interested inthis channel.

(2)

As we said, the a priori probability that U is interested in S
p
is PU (S). The a posteriori probability that U is interested in S iskÕp
PU (Si ) ≥ 1

p≤ PU (S) or
(3)

i=1
p

But from equation 2 we know that ∀ i, PU (Si ) > 1/k. Plugging
ÍÍpthis into inequality 3 we get ki=1 PU (Si ) ≥ ki=1 1/k = 1 and thusp

P (S )PUa (S) = Ík U p

i =1 PU (S i )p≤ PU (S)□Is Privacy possible without Anonymity?
The case for microblogging services

EuroSec ’19, March 25–28, 2019, Dresden, Germany

3.1.3 Bounds in the error estimation. The described approach (i.e.
Algorithm 1) is based on the fact that for each user U and eachchannel S we know the a priori probability that U is interestedpin S: PU (S). One might reasonably argue that this probability is
not known, or is not accurately estimated. In this section we acknowledge this fact and we take it one step further to focus on thepfollowing question: if we have only an estimate of PU (S), how is it
expected to influence our results?
Let us illustrate this with an example. Suppose that we have auser U who would like to follow the channel S of a political party.
Suppose that the general feeling out there is that this party haspabout 10% of the voters, and so a general approximation of PU (S)would be about 0.10. Our approach, which does not have insidep
information would reasonably assume that PU (S) = 0.10. Assume,
however, that the microblogging service has more information andknows that people who fit the profile of U are two times less likelypto vote for this party and thus the correct estimate of PU (S) would
be 0.05, and not 0.10.
Since our approach assumes that the probability is 0.1, it would
probably choose 9 more channels as noise and thus it would present
the microblogging service with a request to follow 10 channels (oneof the being S). Since the microblogging service was presented witha request for 10 channels, it would assume that the a posteriori
probability would be PUa (S) = 0.1, or twice as much as the a priori
probability.
On general it can be shown that the following theorem is true:p

Theorem 3.2. If our estimate for the a priori probability PU (S) is
off by a factor of f (> 1) compared to the adversary’s estimate, thenthe adversary’s estimate for the a posteriori probability PUa (S) will
increase at most by a factor of f .
Proof. We will assume two cases: Case 1: we underestimate
the a priori probability, and Case 2: we overestimate the a priori
probability.
In Case 1 where we underestimate the a priori probability, letp
us say that our estimate is PU (S) and that the adversary’s estimatepp
is f × PU (S). Based on our approach we will select 3 ⌈1/(PU (S))⌉
channels to follow and thus based on the number of channels topfollow the adversary’s a posteriori probability would be PU (S) whichp
is much lower than the adversary’s a priori probability f × PU (S).
In this case, the adversary will just ignore the fact that user U isfollowing S among other noise channels and stick to his a priori
probability.
In Case 2 where we overestimate the a priori probability, let usp
say that our estimate is PU (S) and that the adversary’s estimate ispp
PU (S)/f . Based on our approach we will select ⌈1/(PU (S))⌉ channels to follow and thus based on the number of channels to followpthe adversary’s a posteriori probability would be PU (S) which isphigher than the adversary’s a priori probability PU (S)/f by a factorof f . Thus, the adversary has increased his confidence by a factorof f .
3 Without loss of generality we assume that there exist ⌈1/(P p (S ))⌉ channels with aUppriori probability (PU (S )) each. If no such channels can be found, the proof is similar

in concept.

To summarize, in Case 1 the adversary’s estimate for the a posteriori probability PUa (S) has not increased and in Case 2 it has
increased by a factor of f .
□The above theorem gives us a very elegant results that bounds
the error in the estimation of of the a priori probability:
If the a priori is overestimated by a factor of f thiswill increase the adversary’s belief by no more than afactor of f . If the a priori is underestimated by a factorof f , this will not increase the adversary’s belief.
In addition, theorem provides a nice way for us to make conservative choices. That is, if we are concerned that we have overestimateda probability by a factor of f , we may just decrease it by the same
factor and the adversary will have gained no knowledge at all.

3.2

Correlation Attacks

As explained in section 1 the longer a user interacts with a system,
the more information she reveals. This information can be potentially used by an adversary to filter out some noise channels andfind the real interests of the users. This is what we call a correlation
attack. Let us use an example to illustrate the attack. Let us assume
that user U is following channel S (along with a bunch of noisechannels). Let us also assume that U is interested in following T as
well. Let us also assume that T publishes content semantically correlated with the content of S. 4 Such cases, constitute a privacy risk
since the microblogging service is able to identify this correlation
and as a consequence the fact that U interested in sensitive channel
S and not in any of the noise channels. To summarize, when a user
follows a channel new channel T , there are two cases:• T is semantically unrelated to the previously followed channel S, or• T is semantically related to S,
In the former case the fact that user follows T reveals no more
information about whether the user is interested in S. In the latter case, however, the fact that the user is following T (which issemantically related to S) gives some more confidence that the user
is really interested in S and not in the rest of the noise channels
followed.
Let’s try, at this point, to mathematically define the notion ofwhat is called semantically related channels. Assuming P(S) is theprobability that the user is interested in channel S, then P(S |T ) is
the probability that she is actually interested in a already followed
sensitive channel S given that she now follows channel T . Thus,
channels S and T are semantically related if P(S |T ) , P(S). So,
similar to the single channel noise selection, in this case we selectnoise following the equation:
P (S |T ) = P (S 1 |T1 ) = P (S 2 |T2 ) = ... = P (S N − 1 |T N − 1)(4)

where, S 1 , S 2 ,... S N − 1 are the already followed noise channels
for sensitive channel S. From the formula above, we can see thateach couple of channels: S 1 and T1 , S 2 and T2 ,..., S N − 1 and TN −1 are also correlated channels. Hence, we select the appropriate
noise channels for T based on the already followed noise channels
4 For example, S can be an information channel on cancer and T can be a supportchannel for cancer survivors.

EuroSec ’19, March 25–28, 2019, Dresden, Germanyof S creating this way noise correlations. As a result, we hide thecorrelated couple of channels that the user is interested in, inside
other correlated channel pairs. In the same manner, in case of
more than two correlated channels we use the same algorithm tointroduce noise channels formed as couples.

4

RELATED WORK

Papadopoulos et al. in [21] propose to hide a user’s subscription
from the microblogging service by selecting k − 1 other noisechannels in which the channel that the user is actual interested
in will be hidden, and afterwards by encouraging the user to subscribe to all these k channels. They also propose two algorithms,
the uniform and the proportional algorithm, for random selectionof the noise channels from a set with sensitive channels that iscommons among the users of the microblogging service. Although
our approach is similar to k-subscription, k-subscription deals onlywith unrelated channels and can not take into account correlations
between different channels.
There are similar approaches in different context, aiming to hideuser queries in search engines. Howe and Nissenbaum in [11] proposed TrackMeNot, a system designed to hide a user’s real interest
from a search engine. More specifically, for each real query submitted to the search engine, by a user, the TrackMeNot browser
plugin [10] also submits several other queries to confuse the searchengine and introduce doubt for the user’s real queries. TrackMeNot
has been proven to be seminal work in the field and has led to thedevelopment of several other methods. For example, GooPIR [5],as an extend of TrackMeNot, proposes an approach that is robust
against timing attacks. For each real query, the user wants to submit,
GooPIR constructs k − 1 other queries and submits all k of them atthe same time to the search engine. As a consequence, the searchengine cannot construct a timing model on the user’s real queries.
Murugesan and Clifton in [16] propose Plausibly Deniable Search(PDS) aiming to provide plausible deniability to users, with respect
to their search queries. Similar to GooPIR mentioned above, eachreal query is accompanied by k − 1 other noise queries. In addition,
each real query is also brought into a canonical from preventing
this way identifiability based on typos and/or grammar/syntax ofthe queries [1, 17]. In the same spirit, Ye et al. [25] propose noise
injection for search privacy protection. They give a lower boundfor the amount of noise queries required for perfect privacy protection and provide the optimal protection given the number of noise
queries. Although the above systems are very effective at hiding one
real query in a crowd of k queries, a determined adversary may beable to find a user’s interests by studying successive sequences ofqueries. Indeed, if a user consistently generates authentic queries ona particular topic, but the k − 1 “noise” queries added are on several
different topics, then the adversary may easily find the user’s realinterests using clustering approaches. To protect against clustering
attacks, PRAW [7] generates dummy queries on topics related tothe topics the user is interested in.

5

CONCLUSION

In this paper we explored whether it is possible for users to hide
their interests in microblogging services in a setting where anonymity
is not possible. We showed that it is possible for users to protect
their privacy even if they can not hide their identity. To do so, wePanagiotis Papadopoulos et al.
proposed two obfuscation-based algorithms and quantified their effectiveness. We believe that this result is very encouraging and that
it will probably encourage more privacy research in this setting.
Acknowledgements: The research leading to these results hasreceived funding from European Union’s Marie Sklodowska-Curie
grant agreement 690972 (PROTASIS). The paper reflects only the authors’ view and the Agency and the Commission are not responsible
for any use that may be made of the information it contains.

REFERENCES[1] S. Afroz, M. Brennan, and R. Greenstadt. Detecting Hoaxes, Frauds, and Deception in Writing Style Online. In , pages 461–475, Washington, DC, USA,2012. IEEE Computer Society.
[2] E. Balsa, C. Troncoso, and C. Diaz. Ob-pws: Obfuscation-based private web
search. In SP ’12, 2012.
[3] F. T. Commission.
F.t.c. sues failed website, toysmart.com, fordeceptively offering for sale personal information of website visitors.
http://www.ftc.gov/news-events/press-releases/2000/07/
ftc-sues-failed-website-toysmartcom-deceptively-offering-sale, 2000.
[4] R. Dingledine, N. Mathewson, and P. Syverson. Tor: The second-generation
onion router. In SSYM’04.
[5] Domingo-Ferrer, Josep and Solanas, Agusti and Castellà-Roca, Jordi.
h(k)-private information retrieval from privacy-uncooperative queryable
databases. Online Information Review, 33(4):720–744, 2009.
[6] P. Eckersley. How unique is your web browser? In , 2010.
[7] Y. Elovici, C. Glezer, and B. Shapira. Enhancing Customer Privacy While
Searching for Products and Services on the World Wide Web. Internet Research, 2005.
[8] A. Gervais, R. Shokri, A. Singla, S. Capkun, and V. Lenders. Quantifying websearch privacy. In CCS ’14, pages 966–977, New York, NY, USA, 2014. ACM.
[9] O. Goga, D. Perito, H. Lei, R. Teixeira, and R. Sommer. Large-scale correlationof accounts across social networks. Technical report, International Computer
Science Institute (ICSI), 2013.
[10] P. Gralla. Trackmenot firefox add-on keeps search engine data profilers confused. http://www.pcworld.com/article/235741/TrackMeNot.html, July 2011.
[11] D. C. Howe and H. Nissenbaum. TrackMeNot: Resisting surveillance in web
search. In I. Kerr, V. Steeves, and C. Lucock, editors, Lessons from the Identity Trail: Anonymity, Privacy, and Identity in a Networked Society, chapter 23,
pages 417–436. Oxford University Press, Oxford, UK, 2009.
[12] L. King.
Facebook, whatsapp, and the insatiable appetite
for
data.
http://www.forbes.com/sites/leoking/2014/03/06/
facebook-whatsapp-and-the-insatiable-appetite-for-data/, March 2014.
[13] T. Kohno, A. Broido, and K. Claffy. Remote physical device fingerprinting.
Dependable and Secure Computing, IEEE Transactions on, 2005.
[14] G. Kontaxis, M. Polychronakis, A. D. Keromytis, and E. P. Markatos. Privacypreserving social plugins. In Security’12, 2012.
[15] N. Lomas. Battery attributes can be used to track web users. http://techcrunch.
com/2015/08/04/battery-attributes-can-be-used-to-track-web-users/, 2015.
[16] M. Murugesan and C. Clifton. Providing privacy through plausibly deniablesearch. In SDM’09, pages 768–779, 2009.
[17] A. Narayanan, H. Paskov, N. Z. Gong, J. Bethencourt, E. Stefanov, E. C. R. Shin,and D. Song. On the feasibility of internet-scale author identification. In SP’12, pages 300–314, Washington, DC, USA, 2012. IEEE Computer Society.
[18] P. Papadopoulos, N. Kourtellis, and E. P. Markatos. Exclusive: How the(synced) cookie monster breached my encrypted vpn session. In EuroSec’18.
[19] P. Papadopoulos, N. Kourtellis, and E. P. Markatos. Cookie synchronization: Everything you always wanted to know but were afraid to ask. CoRR,
abs/1805.10505, 2018.
[20] P. Papadopoulos, N. Kourtellis, P. R. Rodriguez, and N. Laoutaris. If you are
not paying for it, you are the product: How much do advertisers pay to reachyou? In IMC’17.
[21] P. Papadopoulos, A. Papadogiannakis, M. Polychronakis, A. Zarras, T. Holz,and E. P. Markatos. K-subscription: Privacy-preserving microblogging browsing through obfuscation. In ACSAC ’13.
[22] RT. Privacy betrayed: Twitter sells multi-billion tweet archive. http://www.rt.
com/news/twitter-sells-tweet-archive-529/, February 2012.
[23] L. Sweeney. K-anonymity: A model for protecting privacy. Int. J. Uncertain.
Fuzziness Knowl.-Based Syst., 10(5):557–570, Oct. 2002.
[24] M. N. Szomszor, I. Cantador, and H. Alani. Correlating user profiles frommultiple folksonomies. In HT ’08.
[25] S. Ye, F. Wu, R. Pandey, and H. Chen. Noise injection for search privacy protection. In CSE ’09, 2009.