CS Paper Radar

Pattern-level Differential Privacy for High-utility Complex Event Processing

He Gu, Thomas Plagemann, Vera Goebel, Maik Benndorf, Boris Koldehofe

cs.CR cs.DB ·submitted 2026-09-20 19:23 UTC · v1

Abstract

Current privacy-preserving mechanisms (PPMs) in Complex Event Processing (CEP) systems are unnecessarily restrictive, reducing the utility of data received by data consumers. This article presents a novel approach to preserve privacy in CEP systems, improving the utility of detected event patterns by dynamically adapting the noise added to an unprotected data stream. We introduce a new guarantee named pattern-level differential privacy (DP), which enables us to apply and compare the strength of PPMs at the pattern level. We propose new pattern-level PPMs yielding pattern-level DP and analyze different trust settings of these PPMs and their requirements for context knowledge in the CEP system, e.g., the deployed queries. Our evaluation is based on three datasets (two real-world, one synthetic) and shows that the proposed PPMs increase data utility while preserving the same privacy level as the state-of-the-art PPMs. We use simulations to study the performance of our proposed PPMs in various practical scenarios. Furthermore, we demonstrate that computational complexity is not an obstacle to deployment.

Closest papers

Nearest neighbours by meaning across the whole index.

Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private Filtering

cs.LG ·2026-10-29 ·Moshe Shenfeld, Eliad Tsfadia, Katrina Ligett
similarity 0.68
Abstract

Differential privacy requires that algorithms be stable to the change of any record in their input, even to an extreme outlier. Private algorithms thus commonly introduce noise scaled to the worst-case possible influence of any single record. This work studies how to build differentially private algorithms that can effectively tailor their noise to the typical case rather than the worst case. We introduce the general \emph{propose-filter-release} (PFR) framework, which, by privately filtering its input, turns a mechanism that protects the addition or removal of a \emph{typical} record into one that is differentially private in the standard sense, on \emph{every} input. We show how to instantiate PFR with a novel filtering step to obtain a general meta-algorithm. Given only a concave friendliness score (which measures how typical a record is with respect to a dataset) and a release mechanism that is friendly-DP (that is, private conditioned on the changed record being typical of the remaining data), it guarantees differential privacy on sufficiently large datasets. The FriendlyCore [TCK+22] and Propose-Test-Release [DL09] algorithms can be viewed as instantiations of our general approach. We illustrate the generality of PFR by instantiating it for scalar statistics, principal subspace estimation with a dimension-independent sample size, the KL divergence of user histograms, the effective resistances in a resistor network, and treatment-rule selection.

0.18

Identification of Compositional Risks in Data Protection Impact Assessments and Beyond

cs.CR ·2026-09-01 ·Henrik Graßhoff, Meiko Jensen, Malte Hansen, Nils Gruschka
top venue similarity 0.67
Abstract · This is the version as published by IEEE

When personal data is processed in a distributed manner by cooperating service providers, privacy risks may emerge solely from the choice of data processors included in the composition. For instance, different data processors may unknowingly rely on the same cloud provider, allowing for unintended linkability of personal data at that very provider. As such compositional risks to privacy are beyond the scope of each individual risk assessment, they are likely to be overseen when performing a data protection impact assessment. In this paper, we propose a novel protocol to detect and manage such compositional risks to privacy. Following an initial problem definition and requirements elicitation, we elaborate how our protocol identifies candidates for compositional risks and how this information may be used to improve the results of a data protection impact assessment over service compositions including multiple data processors.

0.35

Revisiting Continuous Noise Sampling for Multi-Party Differential Privacy

cs.CR ·2026-08-27 ·Yucheng Fu, Tianhao Wang
similarity 0.66
Abstract

Combining secure multi-party computation (MPC) with differential privacy (DP) enables multiple parties to release aggregate statistics without a trusted curator, and the core primitive is the protocol to sample noise from a continuous distribution under finite-precision arithmetic. In this paper, we revisit the continuous noise sampling protocols and present several improvements in both security and efficiency. We start by identifying a vulnerability in widely used sample-and-scale constructions. We demonstrate that the scaling operation in arithmetic circuits confines the noise to a sparse, publicly known set of values, so that an adversary can observe the released noisy queries and decide which dataset produced them. As concrete demonstrations, we instantiate attacks on two systems employing such ``flawed'' sampling protocols: Orchard (OSDI'20) for DP secure aggregation and DP-BREM$^+$ (USENIX Sec'25) for DP federated learning. We report a near-$100\%$ attack success rate on both systems, under any noise scaler $s\geq 2$ used in practice. The leakage we reveal is intrinsic to the scaling operation, and direct repairs either substantially sacrifice utility or add significant precision bits to make the sampling more expensive. To address the security and efficiency issues together, we turn to discrete sampling at the granularity of individual biased bits. We make several optimizations to the sampler and prove its security. Our implementation achieves $4\times \sim 612\times$ speedup over existing secure discrete samplers and orders-of-magnitude speedup over the insecure sample-and-scale paradigm, with negligible utility loss compared to the ideal continuous mechanism.

0.37

Tight End-to-End Accounting for Differentially Private Synthetic Data

cs.CR cs.LGstat.ML ·2026-10-12 ·Georgi Ganev, Vadym Doroshenko, Arun Ganesh, Juan Felipe Gomez, Ryan McKenna +1 more
similarity 0.65
Abstract

Differentially private (DP) pipelines often combine heterogeneous mechanisms, yet their guarantees are best analyzed using different notions of privacy (e.g., bounded range, zCDP, ADP). When composing them, we have to analyze the guarantees through a reduced common representation that loses accounting precision. This issue is particularly relevant in DP synthetic data generation, where data preprocessing, generation algorithms, and DP-SGD could appear within the same pipeline. We develop novel tools for tight end-to-end accounting of such compositions using privacy loss distributions (PLD), $f$-DP, and Gaussian DP (GDP). In particular, we derive PLD and GDP analyses of bounded-range mechanisms such as the Exponential mechanism. Building on these theoretical results, we introduce AIM-GDP, a GDP-native variant of AIM (a state-of-the-art DP synthetic data mechanism) that enables easy composability with complex pipelines via PLD, attack-aware risk calibration, and tight end-to-end auditing while consistently achieving better utility; and MixCal, an algorithm for calibrating adaptive mixed compositions using PLD accounting. Overall, our tools enable tighter end-to-end accounting and thus less noise at the same privacy level in DP synthetic data pipelines.

0.24

Ask in the Crowd: Differentially Private LLM Inference via Dummy-Augmented Shuffling

cs.AI cs.CR ·2026-11-19 ·Zhihao Liu, Zixiong Guo, Shuo Shao, Yu He, Wenli Wang +3 more
similarity 0.65
Abstract

Large language models are increasingly deployed as LLM-as-a-Service (LLMaaS), where user queries are sent to remote LLMs for inference, raising severe privacy concerns about the exposure of sensitive user inputs. Differentially private inference mitigates these risks by injecting noise into input embeddings. However, existing methods struggle to balance privacy and utility, as stronger privacy protection often leads to substantial accuracy degradation in LLM inference. In this work, we propose DP-SPD, a differentially private LLM inference framework that protects user queries by hiding the real query among client-generated dummy queries. All queries are randomly shuffled before being sent to the server, preventing direct identification of the user's true intent. To improve inference efficiency, we exploit the shared-prefix structure among queries and reuse transformer key--value (KV) caches during decoding. We analyze the privacy guarantee of DP-SPD and evaluate its utility on classification and generation tasks, as well as its privacy protection under QIA, EIA, and GPT-based attacks. Experimental results show that our method achieves strong inference-time privacy protection and near-plaintext utility while improving inference efficiency through shared-prefix KV-cache reuse.

0.07

Big data, differential privacy, and national statistical organisations

cs.CY stat.AP ·2026-09-02 ·James Bailie
published similarity 0.65
Abstract · 15 pages plus references, 2 tables, 2 figures

Differential privacy (DP) has emerged in the computer science literature as a measure of the impact on an individual's privacy resulting from the publication of a statistical output such as a frequency table. This paper provides an introduction to DP for official statisticians and discuss its relevance, benefits, and challenges from a National Statistical Organisation (NSO) perspective. We motivate our study by examining how privacy is evolving in the era of big data and how this might prompt a shift from traditional statistical disclosure techniques used in official statistics--which are generally applied on a cell-by-cell or table-by-table basis--to formal privacy methods, like DP, which are applied from a perspective encompassing the totality of the outputs generated from a given dataset. We identify an important interplay between DP's holistic privacy risk measure and the difficulty for NSOs in implementing DP, showing that DP's major advantage is also DP's major challenge. This paper provides new work addressing two key DP research areas for NSOs: DP's application to survey data and its incorporation within the Five Safes framework.

0.55

Revisiting the Provable-Auditable Privacy Gap of DP-SGD

cs.LG ·2026-08-28 ·Saloni Modi, Srivi Balaji, Yusong Zhu, Gautam Kamath, Kevin Tian
theorycode/data similarity 0.64
Abstract · The code for this paper can be found here: https://github.com/pineappleEnthusiast/empirical-privacy-defense

Differential privacy (DP) has traditionally been used to provide theoretical upper bounds on an algorithm's stability to changing its training data. In modern private machine learning applications, achieving strong tradeoffs between utility and theoretical privacy is challenging, and thus one may optimistically hope that existing theoretical privacy analyses are loose. Recent work on privacy auditing has adopted a dual viewpoint, instead lower bounding the true privacy of an algorithm by constructing empirical distinguishing events. The auditing literature has thus far yielded a pessimistic outlook on the looseness of theoretical privacy bounds for DP-SGD, the de facto private training method in modern ML, as nearly-matching empirical lower bounds have been achieved under various threat models [NHSBTJCT23, AC24, CBP25]. In this work, we propose the empirical privacy lower bound of an algorithm as a concrete metric to optimize for, complementary to the theoretical upper bound. We give a lightweight defense framework that generically augments optimization methods in the ML pipeline to have significantly-improved empirical privacy on standard benchmarks. Moreover, we show that our framework comes at no theoretical privacy cost when augmenting DP-SGD, unlike previously-proposed defenses against membership inference attacks. We evaluate our defense against a broad range of audit constructions, models, and datasets to demonstrate its flexibility.

0.25

An Information Hierarchy of Privacy Filters and Odometers

cs.CR ·2026-11-02 ·Sophie Taylor, Praneeth Vippathalla, Justin P. Coon
similarity 0.64
Abstract

In sequential data analysis, privacy loss accumulates over time, and privacy filters and odometers are used to control and track this cumulative cost. We study how the information used by differential privacy filters and odometers fundamentally limits what they can achieve. We formalise three levels of information: spec-level information, fixed prior to the interaction; mechanism-level information, which includes the mechanisms instantiated during the interaction; and realisation-level information, which further includes the realised interaction. We classify privacy filters and odometers by the least informative level sufficient to determine their behaviour. Our main results establish strict and arbitrarily large separations in achievable performance across this information hierarchy. For privacy filters, moving up the hierarchy can yield an unbounded utility advantage, quantified by a clipped measure of the number of allowed releases. For privacy odometers, it can yield an arbitrarily large improvement in precision, quantified by the expected peak excess of the reported bound over the realised privacy loss. Further, although the information classes are distinct, we show that moving to a richer class need incur essentially no loss in performance. Finally, we show that randomisation provides a resource orthogonal to information: at every information level, it can yield an arbitrarily large utility improvement over deterministic filters. Thus, information access and randomisation can be viewed as fundamental resources governing privacy procedures in adaptive interactions.

0.23