CS Paper Radar

Privacy-Constrained Function Computation in Distributed Databases

Vamoua Yachongka, Rémi A. Chou

cs.IT ·submitted 2026-10-29 22:26 UTC · v1
published

Abstract

Consider distributed databases that contain both sensitive (private) and non-sensitive (public) attributes. A user seeks to compute a function of public attributes and side information by interacting with the databases and downloading their responses. In this paper, we study the trade-offs among download cost, information leakage about the private attributes, and distortion between the computed function and its reconstruction, referred to as the capacity region. Our main contributions are as follows. For a single database, we provide a complete characterization of the capacity region for general discrete sources and characterize the capacity region of two different setups for Gaussian sources when the computed function is defined as the sum of the public attribute and side information. For distributed databases, we establish inner and outer bounds on the capacity region of discrete sources and we characterize the capacity region when the databases and the side information are mutually independent. As a special instance, we study lossless function computation, and results analogous to the lossy case are obtained.

Comment
A preliminary version of this paper was presented at IEEE ISIT 2025

Closest papers

Nearest neighbours by meaning across the whole index.

Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results

cs.IT cs.CRcs.NIeess.SP ·2026-09-14 ·Mohamed Nomeir, Shreya Meel, Sennur Ulukus
similarity 0.66
Abstract · Abstract is trimmed for space limitations

In this paper, we introduce the problem of private information retrieval (PIR) under arbitrary privacy requirements, in a graph-based storage system. This formulation is motivated by the server storage limitations, abundance of data (messages) and heterogeneous data privacy requirements. Under the arbitrary privacy requirement, each message has to be retrieved privately from a pre-specified subset of servers, where the subset always includes the servers storing it. Thus, each server is associated with a privacy set, which pre-specifies the message indices that should be privately retrieved from it. This setting is a generalization of the classical PIR setting, where the required message index needs to be kept private from all servers, i.e., there, the privacy set of each server comprises all message indices. Our setting is also a bridge between the newly formulated local PIR (LPIR) setting and the classical PIR setting, where in the former, the privacy set is exactly the set of stored message indices. In this paper, we derive general lower and upper bounds on the PIR capacity for general graphs, under certain privacy requirements, that capture the essence of both LPIR and classical PIR. Then, we focus on path and cyclic storage graphs under these and more fine-grained settings, for which we derive capacity results for certain cases, and establish lower and upper bounds for others. Their low degree allows for a more in-depth understanding of the new privacy formulation and admits more privacy requirement settings compared to other simple graphs. Finally, we introduce a new graph structure, the pyramid storage graph, to model server storage. Although this graph has never been investigated in the literature in any PIR context, it enjoys a nice symmetric structure for message storage and replication patterns.

0.24

Private Vulnerability Testing for User Oversharing

cs.CR ·2026-11-04 ·Alexander Boyd, Daniel Gardham, Nishanth Sastry, Suparna De
similarity 0.65
Abstract · 19 pages, 4 figures, submitted to WWW 2027

Users can inadvertently increase their vulnerability to privacy attacks by oversharing personal information. In particular, the combination of individually innocuous attributes can place a user in a sufficiently small population to enable linkage or re-identification attacks. We present a privacy-preserving mechanism that allows users to determine whether the information they disclose places them below a predefined population threshold, without revealing their query or the data of other users. Our setting presents several practical challenges: users contributing data may be offline when queries are made, queries may select arbitrary subsets of attributes, and neither server should learn the queried population or its size. We address these challenges using secret-shared data and queries, private equality testing, and secure threshold computation. Our protocol provides computational privacy against a malicious client and semi-honest, non-colluding servers, while supporting arbitrary queries and dynamic database updates. We define reactive $f$-privacy for a dynamically evolving database and prove that our construction satisfies it, with the sequence of permitted threshold outputs defining the information available to the adversary across an execution. We optimise the protocol using oblivious-transfer extensions and pre-computation, achieving sub-second online query times for 96-bit queries on datasets of up to one million records.

0.35

Differentially Private Continual Release with Relative Error

cs.DS ·2026-08-20 ·Bo Li, Wei Wang, Peng Ye
theory similarity 0.65
Abstract

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.

0.16

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.64
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

Unifying Privacy Accounting: Information Equivalence and Information Loss

cs.CR cs.ITmath.ST ·2026-10-01 ·Buxin Su, Qiaoshi Yang, Yiding Su, Chendi Wang
similarity 0.64
Abstract

Differential privacy (DP) admits several notions, but the choice among them may affect both privacy analysis and utility. In this paper, we consider four mainstream curve-based privacy notions within a unified information-theoretic framework. For a fixed ordered pair of output distributions, we establish information equivalence among the two directional privacy profiles of $(\varepsilon,δ)$-DP, the pair of hypothesis-testing trade-off functions, and the extended privacy-loss distribution. The exact Rényi differential privacy (RDP) curve joins this equivalence class whenever it is finite at some order greater than one. Under this mild condition, choosing among these notions changes only their semantic interpretation and computational requirements. In contrast, taking the maximum of the directional privacy profiles or compressing the RDP curve into a single zero-concentrated differential privacy (zCDP) parameter can lose information. We quantify the information loss between the exact RDP curve and its zCDP bound for standard noise mechanisms. This gap is zero for Gaussian noise but generally positive for Gaussian-mixture, Laplace, discrete Gaussian, and Poisson-subsampled Gaussian mechanisms. Moreover, this gap grows linearly with the number of independently composed mechanisms. Our information-theoretic perspective has practical consequences. At the same certified privacy level, retaining the full RDP curve rather than using zCDP reduces the required noise variance by up to $45\%$ for Gaussian-mixture noise in workloads comparable in size to the American Community Survey. For DP-SGD on Fashion-MNIST under Poisson subsampling, an RDP-based privacy accountant improves test accuracy by up to $8.73$ percentage points compared to a zCDP-based accountant when both are calibrated to the same $(\varepsilon,δ)$ guarantee.

0.13

Residual Privacy Budgeting with Weighted Scarcity Allocation for Online Query Answering

cs.DB cs.DS ·2026-08-23 ·Mina Khoshmehr, Fernando Beltran
theory similarity 0.63
Abstract · 13 pages. Presented as a poster at the Learning Theory Workshop, University of Copenhagen, June 2026

In many practical deployments of differential privacy, queries do not arrive all at once. We study online differentially private query answering under a finite zero-concentrated differential privacy (zCDP) contract. In this setting, queries arrive sequentially, carry different accuracy thresholds, and may overlap with information already released. We formulate this setting as residual privacy budgeting: for each arriving query, the mechanism first credits reusable support from previous DP outputs and then spends new budget only on the remaining support required to satisfy the current threshold. The controller separates feasible cases, where the minimal residual support is allocated exactly, from scarcity cases, where a weighted shortfall-conservation optimiser assigns limited support according to query difficulty. We define the weight using the Query Influence Factor (QIF), a diagnostic signal for query difficulty and instability rather than query importance. For scalar Gaussian exact reuse, inverse-variance fusion justifies additive support. We prove zCDP composition, residual minimality, 1-competitiveness against the offline optimum in the feasible regime, and avoidable expenditure for allocators that ignore released history. A scarcity impossibility result shows that no online allocator can guarantee a competitive ratio better than 1/n in threshold satisfaction, contextualising the QIF scarcity layer as a design choice for an inherently hard online problem.

0.44

Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast

cs.IT ·2026-10-06 ·Derya Malak, Vijith Kumar K. P., M. Reza Deylam Salehi
publishedtheory similarity 0.62
Abstract · This work extends the conference version presented at IEEE ISIT 2025, available at https://arxiv.org/abs/2502.13688. Example 2, concerning t…

This work studies non-linear function computation broadcast (NFCB), in which a sender with access to $N$ datasets $(X_1,\dots,X_N)$ broadcasts a common message to $K$ users, each possessing side information and requesting a function of the datasets. The goal is to minimize the rate required for asymptotically lossless recovery of all demands. We introduce a broadcast graph that jointly captures the source distribution, side information, and demanded functions. Using Körner's characteristic-graph framework, we develop an achievable scheme for arbitrary $K$, general source distributions, and general finite-field demands, including linear, non-separable, and non-linear functions, without restricting the encoding or decoding operations to be linear. We also present a side-information-assisted independent-set scheme and characterize the optimal graph-based achievable rate for compatible functions. For the converse, we derive a multi-letter response-profile bound that strengthens a basic side-information converse, zero-error and asymptotically lossless clique-entropy bounds based on the operational block broadcast graph, and a genie-aided lower bound. For binary NFCB with $N=K$ and side information $X_i$ at user $i$, we characterize the optimal rate in several special cases and bound the worst-case and average additive gaps between the proposed achievable rate and the genie-aided converse for $K=3$ and $K=4$. Finally, three-user examples with Boolean and linear demands illustrate the proposed bounds and show that non-linear encoding can strictly outperform the best scalar and vector linear schemes.

0.48

Private Online Release of Adaptive Linear Queries

cs.DS ·2026-11-03 ·Aleksandar Nikolov, Haohua Tang
theory similarity 0.62
Abstract

In this paper we study answering counting and other linear queries online under differential privacy constraints. Recent work by Nikolov, Tang, and Ullman [STOC 2026] gave the first online algorithm that answers \emph{obliviously chosen} online linear queries privately, and achieves poly-logarithmic competitiveness against an optimal offline factorization mechanism. This also implied poly-logarithmic competitiveness against arbitrary private offline mechanisms when the private dataset is large enough. The error guarantees of their algorithm, however, can fail when the queries are adaptive. We give a new algorithm that also achieves poly-logarithmic competitiveness, while being able to handle \emph{adaptively chosen} queries. This implies that there is no large separation between the optimal error bounds for privately answering, respectively, offline linear queries, obliviously chosen online linear queries, and adaptively chosen online linear queries. Our algorithm combines the online factorization approach from prior work with a novel layered Euclidean iterative database construction, presenting a new way to use factorization in private algorithms. We also give a lower bound that shows that some poly-logarithmic factor in the competitive ratio is unavoidable. Our lower bound first shows that any interactive private mechanism implies a deterministic online factorization algorithm, and then gives a new lower bound for the competitive ratio of any deterministic online factorization algorithm.

0.06