Personalized information systems are information-filtering systems that endeavor to tailor information-exchange functionality to the specific interests of their users. The ability of these systems to profile users based on their search queries at Google, disclosed locations at Twitter or rated movies at Netflix, is on the one hand what enables such intelligent functionality, but on the other, the source of serious privacy concerns. Leveraging on the principle of data minimization, we propose a data-generalization mechanism that aims to protect users’ privacy against non-fully trusted personalized information systems. In our approach, a user may like to disclose personal data to such systems when they feel comfortable. But when they do not, they may wish to replace specific and sensitive data with more general and thus less sensitive data, before sharing this information with the personalized system in question. Generalization therefore may protect user privacy to a certain extent, but clearly at the cost of some information loss. In this work, we model mathematically an optimized version of this mechanism and investigate theoretically some key properties of the privacy-utility trade-off posed by this mechanism. Experimental results on two real-world datasets demonstrate how our approach may contribute to privacy protection and show it can outperform state-of-the-art perturbation techniques like data forgery and suppression by providing higher utility for a same privacy level. On a practical level, the implications of our work are diverse in the field of personalized online services. We emphasize that our mechanism allows each user individually to take charge of their own privacy, without the need to go to third parties or share resources with other users. And on the other hand, it provides privacy designers/engineers with a new data-perturbative mechanism with which to evaluate their systems in the presence of data that is likely to be generalizable according to a certain hierarchy, highlighting spatial generalization, with practical application in popular location based services. Overall, a data-perturbation mechanism for privacy protection against user profiling, which is optimal, deterministic, and local, based on a untrusted model towards third parties.

Privacy risks in differentially private (DP) systems increase significantly when data is correlated, as standard DP metrics often underestimate the resulting privacy leakage, leaving sensitive information vulnerable. Given the ubiquity of dependencies in real-world databases, this oversight poses a critical challenge for privacy protections. Bayesian differential privacy (BDP) extends DP to account for these correlations, yet current BDP mechanisms indicate a notable utility loss, limiting its adoption. In this work, we address whether BDP can be realistically implemented in common data structures without sacrificing utility—a key factor for its applicability. By analyzing arbitrary and structured correlation models, including Gaussian multivariate distributions and Markov chains, we derive practical utility guarantees for BDP. Our contributions include theoretical links between DP and BDP and a novel methodology to adapt DP mechanisms to meet the requirements of BDP. Through evaluations on real-world databases, we demonstrate that our novel theorems enable the design of BDP mechanisms that maintain competitive utility, paving the way for practical privacy-preserving data practices in correlated settings.

A privacy model is a privacy condition, dependent on a parameter, that guarantees an upper bound on the risk of reidentification disclosure and maybe also on the risk of attribute disclosure by an adversary. A privacy model is composable if the privacy guarantees of the model are preserved, possibly to a limited extent, after repeated independent application of the privacy model. From the opposite perspective, a privacy model is not composable if multiple independent data releases, each of them satisfying the requirements of the privacy model, may result in a privacy breach. Current privacy models are broadly classified into syntactic ones (such as k-anonymity and l-diversity) and semantic ones, which essentially refer to$\varepsilon $-differential privacy (e-DP) and variations thereof. While e-DP and its variants offer strong composability properties, syntactic notions are not composable unless data releases are conducted by a single, centralized data holder that uses specialized notions such as m-invariance and$\tau $-safety. In this work, we propose m-uncoordinated-syntactic-privacy (m-USP), the first syntactic notion with composability properties for the independent publication of nondisjoint data, in other words, without a centralized data holder. Theoretical results are formally proven, and experimental results demonstrate that the risk to individuals does not increase significantly, in contrast to non-composable methods, that are susceptible to attribute disclosure. In most cases, the utility degradation caused by the extra protection is less than 5% and decreases as the value of m increases.

Vertical Federated Graph Learning (VFGL) is a novel privacy-preserving technology that enables entities to collaborate on training Machine Learning (ML) models without exchanging their raw data. In VFGL, some of the entities hold a graph dataset capturing sensitive user relations, as in the case of social networks. This collaborative effort aims to leverage diverse features from each entity about shared users to enhance predictive models or recommendation systems, while safeguarding data privacy in the process. Despite these advantages, recent studies have revealed a critical vulnerability that appears in intermediate data representations, which may inadvertently expose link information in the graph. This work proposes a novel Link Inference Attack (LIA) that exploits gradients as a new source of link information leakage. Assuming a semi-honest adversary, we demonstrate through extensive experiments on seven real-world datasets that our LIA outperforms state-of-the-art attacks, achieving over 10% higher Area Under the Curve (AUC) in some instances, thereby highlighting a significant risk of link information leakage through gradients. Our attack’s effectiveness primarily stems from label information embedded in gradients, as evidenced by comparison with a label-only LIA. We analytically derive our Label-based LIA’s accuracy using graph characteristics, assessing target graph vulnerability. To address these vulnerabilities, we evaluate two types of defenses: edge perturbation based on differential privacy and a novel label perturbation approach, demonstrating that our proposed label perturbation defense is more effective against all attack types across all datasets examined, offering a more favorable privacy-utility trade-off. Our comprehensive analysis shows why LIAs are effective and identifies potential defenses, highlighting the need for further research to improve the security of VFGL systems against link information leakage.

The composition theorems of differential privacy (DP) allow data curators to combine different algorithms to obtain a new algorithm that continues to satisfy DP. However, new granularity notions (i.e., neigh-borhood definitions), data domains, and composition settings have appeared in the literature that the classical composition theorems do not cover. For instance, the original parallel composition theorem does not translate well to general granularity notions. This complicates the opportunity of composing DP mechanisms in new settings and obtaining accurate estimates of the incurred privacy loss after composition. To overcome these limitations, we study the composability of DP in a general framework and for any kind of data domain or neighborhood definition. We give a general composition theorem in both independent and adaptive versions and we provide analogous composition results for approximate, zero-concentrated, and Gaussian DP. Besides, we study the hypothesis needed to obtain the best composition bounds. Our theorems cover both parallel and sequential composition settings. Importantly, they also cover every setting in between, allowing us to compute the final privacy loss of a composition with greatly improved accuracy.

Continuous data publishing consists in the republication of updating microdata. The most relevant syntactic notions in continuous data publishing are based on m-invariance. This notion enforces that no user can be distinguished among, at least,m- 1 other users, each with distinct secret data. To achieve m-invariance, the existing methods must first alter the dataset to satisfy a property called m-eligibility. Essentially, a dataset can be made m-invariant if and only if it satisfies the m-eligibility constraint. Although guaranteeing the m-eligibility property is a crucial step, no theoretical study of the best strategies to achieve it has been carried out. This paper performs such a study by giving strategies and demonstrating their optimality under two approaches: insertion of counterfeit tuples and partial publication. The empirical evaluation of our proposal shows a significant reduction on the number of modifications needed to enforce m-eligbility of up to 41% with respect to the literature.

The usage of authentication schemes is increasing in our daily life with the ubiquitous spreading Internet services. The verification of user's identity is still predominantly password-based, despite being susceptible to various attacks and openly disliked by users. Bonneau et al. presented a framework, based on Usability, Deployability, and Security criteria (UDS), to evaluate authentication schemes and find a replacement for passwords. Although the UDS framework is a mature and comprehensive evaluation framework and has been extended by other authors, it does not analyse privacy aspects in the usage of authentication schemes. In the present work, we extend the UDS framework with a privacy category to allow a more comprehensive evaluation, becoming the UDSP framework. We provide a thorough, rigorous assessment of sample authentication schemes, including the analysis of novel behavioural biometrics. Our work also discusses implementation aspects regarding the new privacy dimension and current gaps to be addressed in the future research.

Trajectory analysis holds many promises, from improvements in traffic management to routing advice or infrastructure development. However, learning users' paths is extremely privacy-invasive. Therefore, there is a necessity to protect trajectories such that we preserve the global properties, useful for analysis, while specific and private information of individuals remains inaccessible. Trajectories, however, are difficult to protect, since they are sequential, highly dimensional, correlated, bound to geophysical restrictions, and easily mapped to semantic points of interest. This paper aims to establish a systematic framework on protective masking and synthetic-generation measures for trajectory databases with syntactic and differentially private (DP) guarantees, including also utility properties, derived from ideas and limitations of existing proposals. To reach this goal, we systematize the utility metrics used throughout the literature, deeply analyze the DP granularity notions, explore and elaborate on the state of the art on privacy-enhancing mechanisms and their problems, and expose the main limitations of DP notions in the context of trajectories.

While most anonymization technology available today is designed for static and small data, the current picture is of massive volumes of dynamic data arriving at unprecedented velocities. From the standpoint of anonymization, the most challenging type of dynamic data is data streams. However, while the majority of proposals deal with publishing either count-based or aggregated statistics about the underlying stream, little attention has been paid to the problem of continuously publishing the stream itself with differential privacy guarantees. In this work, we propose an anonymization method that can publish multiple numerical-attribute, finite microdata streams with high protection as well as high utility, the latter aspect measured as data distortion, delay and record reordering. Our method, which relies on the well-known differential pulse-code modulation scheme, adapts techniques originally intended for hybrid video encoding, to favor and leverage dependencies among the blocks of the original stream and thereby reduce data distortion. The proposed solution is assessed experimentally on two of the largest data sets in the scientific community working in data anonymization. Our extensive empirical evaluation shows the trade-off among privacy protection, data distortion, delay and record reordering, and demonstrates the suitability of adapting video-compression techniques to anonymize database streams.

The intrusiveness of Web tracking and the increasing invasiveness of digital advertising have raised serious concerns regarding user privacy and Web usability, leading a substantial chunk of the populace to adopt ad-blocking technologies in recent years. The problem with these technologies, however, is that they are extremely limited and radical in their approach, and they completely disregard the underlying economic model of the Web, in which users get content free in return for allowing advertisers to show them ads. Nowadays, with around 200 million people regularly using such tools, said economic model is in danger. In this article, we investigate an Internet technology that targets users who are not, in general, against advertising, accept the trade-off that comes with the “free” content, but—for privacy concerns—they wish to exert fine-grained control over tracking. Our working assumption is that some categories of web pages (e.g., related to health or religion) are more privacy-sensitive to users than others (e.g., about education or science). Capitalizing on this, we propose a technology that allows users to specify the categories of web pages that are privacy-sensitive to them and block the trackers present on such web pages only. As tracking is prevented by blocking network connections of third-party domains, we avoid not only tracking but also third-party ads. Since users continue receiving ads on those web pages that belong to non-sensitive categories, our approach may provide a better point of operation within the trade-off between user privacy and the Web economy. To test the appropriateness and feasibility of our solution, we implemented it as a Web-browser plug-in, which is currently available for Google Chrome and Mozilla Firefox. Experimental results from the collected data of 746 users during one year show that only 16.25% of ads are blocked by our tool, which seems to indicate that the economic impact of the ad-blocking exerted by privacy-sensitive users could be significantly reduced.

The intrusiveness and the increasing invasiveness of online advertising have, in the last few years, raised serious concerns regarding user privacy and Web usability. As a reaction to these concerns, we have witnessed the emergence of a myriad of ad-blocking and antitracking tools, whose aim is to return control to users over advertising. The problem with these technologies, however, is that they are extremely limited and radical in their approach: users can only choose either to block or allow all ads. With around 200 million people regularly using these tools, the economic model of the Web—in which users get content free in return for allowing advertisers to show them ads—is at serious peril. In this article, we propose a smart Web technology that aims at bringing transparency to online advertising, so that users can make an informed and equitable decision regarding ad blocking. The proposed technology is implemented as a Web-browser extension and enables users to exert fine-grained control over advertising, thus providing them with certain guarantees in terms of privacy and browsing experience, while preserving the Internet economic model. Experimental results in a real environment demonstrate the suitability and feasibility of our approach, and provide preliminary findings on behavioral targeting from real user browsing profiles.

ABSTRACT Message encryption does not prevent eavesdroppers from unveiling who is communicating with whom, when, or how frequently, a privacy risk wireless networks are particularly vulnerable to. The Crowds protocol, a well‐established anonymous communication system, capitalizes on user collaboration to enforce sender anonymity. This work formulates a mathematical model of a Crowd‐like protocol for anonymous communication in a lossy network, establishes quantifiable metrics of anonymity and quality of service (QoS), and theoretically characterizes the trade‐off between them. The anonymity metric chosen follows the principle of measuring privacy as an attacker's estimation error. By introducing losses, we extend the applicability of the protocol beyond its original proposal. We quantify the intuition that anonymity comes at the expense of both delay and end‐to‐end losses. Aside from introducing losses in our model, another main difference with respect to the traditional Crowds is the focus on networks with stringent QoS requirements, for best effort anonymity, and the consequent elimination of the initial forwarding step. Beyond the mathematical solution, we illustrate a systematic methodology in our analysis of the protocol. This methodology includes a series of formal steps, from the establishment of quantifiable metrics all the way to the theoretical study of the privacy QoS trade‐off. Copyright © 2013 John Wiley & Sons, Ltd.

Collaborative tagging is one of the most popular services available online, and it allows end user to loosely classify either online or offline resources based on their feedback, expressed in the form of free-text labels (i.e., tags). Although tags may not be per se sensitive information, the wide use of collaborative tagging services increases the risk of cross referencing, thereby seriously compromising user privacy. In this paper, we make a first contribution toward the development of a privacy-preserving collaborative tagging service, by showing how a specific privacy-enhancing technology, namely tag suppression, can be used to protect end-user privacy. Moreover, we analyze how our approach can affect the effectiveness of a policy-based collaborative tagging system that supports enhanced web access functionalities, like content filtering and discovery, based on preferences specified by end users.