Access Granted, Privacy Lost: Formalizing & Quantifying the Hidden Anonymity Risks of Exclusive-Use Systems
Authors: Christopher Ellis (The Ohio State University), Zhiqiang Lin (The Ohio State University)
Volume: 2026
Issue: 3
Pages: 32–47
DOI: https://doi.org/10.56553/popets-2026-0069
Abstract: Exclusive-use systems emit binary interaction signals through core functions such as authentication, presence updates, and message submissions. Although sparse and encrypted, these signals reflect user-specific behavior and, when linked over time, can erode anonymity. Because each credential or device is uniquely tied to an individual, even minimal activity patterns can enable re-identification and behavioral inference, posing a hidden but persistent privacy risk. We present a formal framework that models this leakage by digitizing interaction outcomes into multidimensional binary signals and quantifying anonymity degradation using entropy-based Quantitative Information Flow (QIF), Bayes vulnerability, and indistinguishability games. To generalize the threat, we introduce a taxonomy spanning attacker capabilities, observation methods, and types of information leaked. After discovering these signals from network analysis of Microsoft Teams, we produce a simulation case study with varying user activity profiles, demonstrating that content-agnostic signals alone enable a passive adversary to achieve 54.7% Top-1 and 89.1% Top-3 re-identification accuracy in a 16-user pool, with mean entropy losses of approximately 1.2 bits (about 30% of the 4-bit anonymity space), and worst-case reductions exceeding 2.4 bits. Additional analyses of WhatsApp traffic and the IDBleed BLE relay attack highlight broader applicability. Our results show that binary observables long treated as benign can systematically compromise anonymity, establishing a cross-domain framework for formalizing, quantifying, and classifying privacy loss in exclusive-use systems. This framework further enables defenders to formally model exclusive-use systems and quantitatively evaluate the privacy impact of proposed mitigations using entropy and vulnerability-based metrics.
Keywords: user privacy, exclusive-use, network protocols, deanonymization, user profiling, tracking, formalization, privacy risks
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
