CS Paper Radar

No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches

Edith Cohen, Uri Stemmer

cs.DS cs.LG ·submitted 2026-10-18 04:24 UTC · v2

Abstract

Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection. At constant accuracy, randomized Euclidean-norm sketches, notably the Johnson-Lindenstrauss transform, support exponentially many nonadaptive queries in sketch dimension $k$. For adaptive black-box queries, known privacy-based defenses guarantee $\widetildeΩ(k^2)$ and it remained open whether stronger guarantees were possible. Prior attacks used more queries, restricted the responder, or provided weaker failure guarantees. We show that the quadratic guarantee is optimal up to logarithmic factors, even with a computationally unbounded responder that knows the matrix, attack algorithm, history, and query distributions and may change its randomized rule after every query. For every fixed hidden $A\in\mathbb{R}^{k\times n}$ with $n>40k$ and target accuracy $α\in (0,1]$, our black-box attack uses $O(k+α^2k^2\log(2+α^2k))$ queries in $\widetilde{O}(1+α^2k)$ adaptive rounds to force, with constant probability, a round in which a constant fraction of answers have $Ω(α)$ relative error. This fraction can be taken arbitrarily close to one half. Our results clarify the limits of defending a fixed compressive linear representation by adapting the prediction rule.

Closest papers

Nearest neighbours by meaning across the whole index.

Private Online Release of Adaptive Linear Queries

cs.DS ·2026-11-03 ·Aleksandar Nikolov, Haohua Tang
theory similarity 0.67
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

A Sharp Transition in Data Reconstruction under Differential Privacy

cs.LG cs.AIstat.ML ·2026-09-29 ·Max Cairney-Leeming, Simone Bombari, Marco Mondelli
similarity 0.67
Abstract

Data reconstruction attacks have empirically been successful in recovering training samples from learned models, raising privacy concerns and motivating defenses with guarantees that remain valid against future threats. While differential privacy (DP) provides formal protection, choosing the privacy budget remains a challenge: small budgets severely reduce utility, but it is hard to quantify how large the budget can be without allowing accurate reconstruction. In this work, we study informed attackers who aim to reconstruct a single $d$-dimensional training sample from a $ρ$-zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at $ρ\asymp d$ for data reconstruction: on the one hand, we derive entropy-based lower bounds for any private mechanism and any attack, characterizing a set of target priors for which reconstruction is information-theoretically impossible for $ρ\ll d$; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for $ρ\gg d$. Remarkably, the transition moves to $ρ\asymp s$ for data lying in an $s$-dimensional subspace, demonstrating that the privacy budget guaranteeing adequate protection must be assessed in terms of the effective dimension of the data. We validate our findings via experiments on synthetic data and natural images (CIFAR-10, ImageNet).

0.05

Preventing Model Extraction in Contextual Linear Optimization

cs.LG math.OC ·2026-10-21 ·Adam N. Elmachtoub, Tianyi Lin, Wenxuan Liu
theory similarity 0.65
Abstract · 25 pages, 11 figures

Consider a contextual linear optimization problem, where a predict-then-optimize (PTO) system returns optimal decisions without revealing the cost vectors used in its downstream linear program. Our focus is on how to prevent attackers, who can submit context queries, from extracting the underlying prediction model. Although the cost-to-decision map is many-to-one, observations across contexts can reveal the underlying prediction model. For linear models, we provide sufficient conditions where the attacker can learn the model up to positive scaling by only observing the decision. These conditions motivate an adaptive attack that alternates inverse optimization with boundary sampling, i.e., using context queries leading to decision boundaries of the current attacker model. To prevent extraction, we propose a mechanism that perturbs decisions only when the predicted cost vector is near a decision boundary. We establish a regret bound in terms of the perturbation radius. For the attackers that fit the defended responses as optimal decisions under the evaluation distribution, we also prove a lower bound on expected extraction error. Experiments on synthetic instances and real data quantify the security-performance trade-off of the defense mechanism and illustrate that our defense can increase the extraction error.

0.18

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

cs.LG cs.AIcs.CR ·2026-10-12 ·Ali Javeri, Javad Hezareh, Radin Shahdaei, AmirMahdi Sadeghzadeh
similarity 0.65
Abstract

Score-based black-box adversarial attacks pose a serious threat to deployed machine learning systems by exploiting repeated model queries to craft adversarial examples, requiring neither access to model parameters nor architecture. Existing defenses predominantly rely on stochastic output perturbations, which fail to prevent determined attackers from recovering stable gradient estimates by increasing query budgets or averaging over randomness. In this work, we propose the Gradient Confusion Defense (GCD), a retraining-free, deterministic test-time wrapper that actively shapes the probability vector returned to querying adversaries. By solving a constrained optimization problem grounded in the model's Jacobian, GCD aligns the exposed logit-gradient with a target confusion direction that is maximally misaligned with the true adversarial loss gradient---increasing the query complexity of attacks without sacrificing predictive utility or top-1 accuracy. We provide rigorous theoretical analysis demonstrating that GCD provably slows gradient-estimation-based attacks and induces systematic accept/reject errors in random search-based attacks, with the confusion effect amplifying as the fraction of defended queries increases. Extensive experiments on CIFAR-10 and ImageNet across multiple architectures (ResNet-18, ResNet-50, ViT-B/16) and four state-of-the-art attacks confirm these predictions: GCD achieves state-of-the-art robustness, while incurring zero clean accuracy degradation. %Crucially, unlike randomization-based defenses, GCD's deterministic structure provides resilience against adaptive attacks that exploit stochasticity, making it well-suited for security-critical deployment settings.

0.12

Private Evaluation of High-Dimensional Functions

cs.CR stat.MLcs.DScs.IT+1 ·2026-10-17 ·Mohammad Afzali, Hassan Ashtiani, Adam Smith
similarity 0.63
Abstract

We study differentially private black-box evaluation of arbitrary high-dimensional functions. Given a dataset $S$ and query access to a function $f$---whose sensitivity may be unknown or unbounded---the goal is to privately output an approximation to $f(S)$. The black-box evaluator can only query the value of $f$ over a down neighborhood of $S$ (i.e., those subsets of $S$ that are obtained by removing a bounded number of elements from $S$). We design generic black-box evaluators for both pure and approximate differential privacy through a reduction to high-dimensional private quasi-concave optimization (QCO). Our black-box evaluator enjoys a geometric notion of utility. Consider the vectors obtained by applying $f$ on sets in a down neighborhood of $S$. With high probability, the evaluator's output is guaranteed to be in the convex hull of these vectors. Our work generalizes the result of Linder et al. [LRSS25] for real-valued function evaluation to high dimensions. It also recovers the private center-point guarantees of Beimel et al. [BMNS19], with an explicit additive approximation to maximum Tukey depth. We also apply our evaluators to user-level quasi-concave and convex optimization, showing how they can improve upon the sample-and-aggregate baseline of Nissim et al. [NRS07] by replacing the multiplicative data overhead with an additive overhead. Finally, we show that our formulation of high dimensional black-box evaluation and high dimensional private QCO are equivalent up to a factor of the dimension: the hardest private evaluation instances already arise from the cases that $f$ is a (non-private) quasi-concave optimizer.

0.20

Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

cs.CR cs.CC ·2026-09-02 ·Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
similarity 0.63
Abstract

We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\| \cdot \|_K$-norm mechanism of Hardt and Talwar [HT10]. For the $\ell_\infty$-error, our algorithm can answer $d$ linear queries with $O(d / \varepsilon)$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\varepsilon \le 1/d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.

0.20

Private Online Prediction from Experts with Small Losses

cs.LG stat.ML ·2026-10-21 ·Bo Li, Peng Ye
theory similarity 0.63
Abstract

We consider online prediction from experts, a fundamental problem in machine learning, under differential privacy constraints. Existing private algorithms achieve near-optimal regret $\tilde{O}(\sqrt{T})$, where $T$ is the time horizon. However, this bound becomes suboptimal when $L^\star$, the cumulative loss of the best expert, is significantly less than $T$. In this work, we present the first differentially private algorithm with regret $\tilde{O}(\sqrt{L^\star})$, offering a substantial improvement in the low-loss regime. Our regret bound matches the non-private lower bound up to poly-logarithmic factors for constant privacy parameters, demonstrating that privacy incurs only a small cost in this setting. Our result assumes that the input sequence is oblivious, i.e., it is fixed in advance and independent of the algorithm's outputs. We also prove that an $\tildeΩ(\sqrt{T})$ regret is inevitable for adaptively generated inputs, even when $L^\star = 0$.

0.17

Spectrum-Aware Bounds on Invertibility for Privacy-Enhancing Instance Encoding

cs.LG cs.CR ·2026-08-24 ·Seokjin Hwang, Yuting Li, Kiwan Maeng
similarity 0.62
Abstract

Instance encoding is a popular empirical technique for privacy enhancement when sharing data to an untrusted server. It transforms sensitive data through an encoding process before sharing, with the hope that the encoding process retains utility but makes it hard to reconstruct the original data. However, most work offers no theoretical guarantee that the encoding process is actually irreversible. A recent work derived a mean-squared error (MSE) bound limiting any adversary's reconstruction accuracy, offering one of the first theoretical results in this domain. This bound, however, has three critical limitations: it is often too loose, only works with randomized encoders (excluding many deterministic encoders practitioners use), and only bounds MSE. We introduce a family of new bounds that (1) are tighter, (2) applicable even to fully deterministic encoders, and (3) can extend beyond MSE to other norm-based similarity metrics, by properly accounting for the encoder's spectral structure. We evaluate our bounds across a range of encoders, datasets, and attacks, showing they hold consistently and improve upon the existing bound.

0.29