  Anonymous data sharing has been becoming more challenging in today's
interconnected digital world, especially for individuals that have both
anonymous and identified online activities. The most prominent example of such
data sharing platforms today are online social networks (OSNs). Many
individuals have multiple profiles in different OSNs, including anonymous and
identified ones (depending on the nature of the OSN). Here, the privacy threat
is profile matching: if an attacker links anonymous profiles of individuals to
their real identities, it can obtain privacy-sensitive information which may
have serious consequences, such as discrimination or blackmailing. Therefore,
it is very important to quantify and show to the OSN users the extent of this
privacy risk. Existing attempts to model profile matching in OSNs are
inadequate and computationally inefficient for real-time risk quantification.
Thus, in this work, we develop algorithms to efficiently model and quantify
profile matching attacks in OSNs as a step towards real-time privacy risk
quantification. For this, we model the profile matching problem using a graph
and develop a belief propagation (BP)-based algorithm to solve this problem in
a significantly more efficient and accurate way compared to the
state-of-the-art. We evaluate the proposed framework on three real-life
datasets (including data from four different social networks) and show how
users' profiles in different OSNs can be matched efficiently and with high
probability. We show that the proposed model generation has linear complexity
in terms of number of user pairs, which is significantly more efficient than
the state-of-the-art (which has cubic complexity). Furthermore, it provides
comparable accuracy, precision, and recall compared to state-of-the-art.

Cryptography and Security;Social and Information Networks