CS Paper Radar

Risk-aware Road-network Trajectory Synthesis under Local Differential Privacy

Hongzhen Xiang, Chenxu Wang, Yumeng Song, Tao Qin, Yushuai Li, Pinghui Wang, Wei Wang, Tianyi Li

cs.CR cs.DB ·submitted 2026-10-12 08:36 UTC · v2

Abstract

Road-network trajectory synthesis under local differential privacy (LDP) enables mobility data analysis without uploading raw trajectories to an untrusted server. Existing locally private trajectory synthesis methods mainly model whole trajectories, point sequences, or grid-level mobility patterns. However, they cannot handle non-uniform privacy risks caused by local road-network and trajectory contexts, such as endpoints, long-stay-associated regions, and low-out-degree branches. They also do not directly protect conditional next-hop choices on road networks, where a user's selected successor may reveal sensitive local movement intentions. To address these challenges, we propose TrajRACE, a locally private synthesis framework for road-network trajectories. TrajRACE uses start, segment-count, and transition reports to represent trajectories. For each transition, it keeps the current road segment as a public aggregation context and perturbs the true successor among legal successors on the client side. It then assigns risk-aware protection strengths to transitions according to local road-network and trajectory contexts. Finally, the server recovers population-level start, segment-count, and conditional transition statistics from heterogeneous privatized reports, and generates synthetic trajectories that follow the public road-network topology. Experiments on three road-network trajectory datasets demonstrate the effectiveness of TrajRACE in improving synthetic-data utility across distributional, query-based, and pattern-level metrics, while providing stronger protection for high-risk local transitions.

Closest papers

Nearest neighbours by meaning across the whole index.

GSynPEF: A Privacy Evaluation Framework for Synthetic Graphs

cs.CR cs.AIcs.SI ·2026-11-06 ·Yu Duan, Luca Baldesi, Carter T. Butts, Athina Markopoulou
similarity 0.64
Abstract

It is often desirable to generate and release synthetic graphs, which resemble real-world data, in a privacy-preserving way. While substantial progress has been made in designing private graph synthesizers (PGS), opportunities remain for more explicit connections between synthesizer models and privacy evaluation, and better accounting for output variation. This paper proposes GSynPEF, a practical framework for empirical evaluation of privacy and utility in settings for which a real-world graph is given as input and output synthetic graph(s) are observed. Our framework links a broad class of graph synthesizers (both statistical and deep-learning based) with privacy metrics, expanding evaluation dimensions to practical utility and risk, through empirical analysis of multiple actual outputs. The framework accommodates both an Exact Solution scenario, where synthesizer behavior is directly observable, and a Monte Carlo Approximation scenario where only synthetic outputs from a black box synthesizer are available. Extensive experiments on four real-world datasets and seven widely used graph synthesizers demonstrate framework's versatility, enabling privacy evaluation for different attack goals (e.g., to infer an edge or node) and capabilities (e.g., observing one or multiple synthetic graphs). We analyze evaluation results by examining the relationship between graph statistics and synthesizer design choices, providing insights for data curators in PGS selection and researchers for improved PGS design.

0.09

An Information Hierarchy of Privacy Filters and Odometers

cs.CR ·2026-11-02 ·Sophie Taylor, Praneeth Vippathalla, Justin P. Coon
similarity 0.61
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

CANTraj: Recovering Vehicle Trajectories from CAN Signals in Naturalistic Driving

cs.CR cs.DB ·2026-11-13 ·Yuhang Wang, Jingxin Yang, Chuheng Wei, Suyang Chen, Haozhuang Chi +1 more
benchmarkdatasetcode/data similarity 0.61
Abstract

Open driving releases and usage-based insurance programs often claim to prevent privacy breaches by omitting GPS records when sharing or collecting vehicle data. However, removing GPS coordinates from driving logs does not erase the location information carried by vehicle signals. While prior route-inference attacks have demonstrated that speed, steering, and driving events can be matched to road networks to reconstruct trajectories, existing studies rely on inconsistent prior assumptions and evaluation metrics and are tested only on small, restricted datasets, making their results difficult to compare and their real-world effectiveness uncertain. We release CANTraj, a naturalistic driving dataset pairing decoded CAN events with time-aligned GNSS trajectories (3,940 drives, 454 drivers), and CANTraj-Bench for evaluating trajectory recovery (3,675 drives, 431 drivers, 1,380 hours, 85,919 km). On 776 evaluation drives from 94 unseen drivers, we compare six re-implemented attacks and benchmark baselines under explicit information-access protocols, paired comparisons, and metrics incorporating failures. Experiments show that combining steering signals with road-network constraints yields the largest gain: With a known start and heading, adding steering to speed raises the online map filter's five-minute route recovery from 56% to 87%, with a median average displacement error of 43 m versus 921 m for map-free dead reckoning. Offline beam search recovers 88% of test routes with the heading and 81% without it. Because methods fail on different windows, we also evaluate an LLM harness that selects among candidate routes on 659 five-minute windows; its best configuration recovers 79% of routes on test and 83% on few-shot, outperforming the best baseline on test and matching it on few-shot. Data and code at huggingface.co/datasets/HenryYHW/CANTraj and github.com/WangYuHang-cmd/GPS--CAN.

0.45

LDPGraph: Locally Differentially Private Graph Synthesis by Exploiting Neighborhood Structure

cs.DB ·2026-10-07 ·Jiawei Dong, Zhikun Zhang, Quan Yuan, Zhe Liu, Yunjun Gao
top venuecode/data similarity 0.60
Abstract · Accepted at IEEE ICDE 2027. Extended version with appendices

The widespread application of graph data inevitably brings significant privacy risks, as its unprotected use can lead to the leakage of sensitive information. These risks are particularly acute in the setting with an untrusted curator, where the data remains decentralized and each user only holds the connections to their neighbors. To mitigate such privacy risks, we adopt local differential privacy (LDP) to collect users' private information and generate a synthetic graph. However, existing methods suffer from either excessive noise injection by perturbing the local adjacency lists or significant structural information loss due to the simplistic graph encoding process. To address these issues, we propose LDPGraph, an effective graph synthesis algorithm that takes one step further by exploiting neighborhood structures under LDP. To obtain neighborhood statistics beyond degrees, LDPGraph aggregates a noisy global view from perturbed adjacency lists and combines it with projected local connections to estimate node-level triangle counts. To correct the structural inconsistency caused by separately perturbing degree and triangle count, LDPGraph jointly refines them into feasible degree-triangle targets. To reconstruct a global graph from these estimated targets, LDPGraph adopts a triangle-first strategy that first preserves local clustering structures and then fulfills remaining degree requirements. Extensive experiments on four real-world datasets and multiple commonly used graph metrics validate the superiority of LDPGraph. Source code is available at https://github.com/ZJU-TrustAID/LDPGraph.

0.44

Data Poisoning Attacks to Locally Differentially Private Triangle Counting Protocols

cs.CR ·2026-11-18 ·Tingxuan Han, Wei Tong, Zijian Wang, Sheng Zhong
top venue similarity 0.60
Abstract · Accepted by ICDE 2027

Local differential privacy (LDP) has become a crucial paradigm for privacy-preserving graph analytics, enabling graph analytics tasks such as subgraph counting without requiring a trusted curator. However, while LDP provides strong privacy guarantees, the integrity and robustness of LDP subgraph counting protocols in the presence of malicious participants remain poorly understood. In particular, since data are randomized locally before collection, it is inherently difficult to distinguish malicious users from honest ones based solely on their submitted reports, and small, protocol-compliant local manipulations can be systematically amplified through reconstruction and calibration into large global estimation bias. In this paper, we use LDP triangle counting as a representative task to characterize the vulnerability of LDP subgraph counting to data poisoning attacks. For both non-interactive and interactive LDP triangle counting protocols, we analyze their attack surfaces and develop a unified gain-driven framework that captures how adversarial users can manipulate calibrated subgraph count estimates, which we instantiate on representative protocols of both types. Extensive experiments on four real-world graph datasets demonstrate that these attacks can significantly distort triangle count estimates across different protocols and adversarial settings. Moreover, we show that existing and straightforward defenses are insufficient to mitigate these attacks, underscoring the need for robustness mechanisms tailored to LDP subgraph counting.

0.51

AgentPrivArena: Evaluating and Auditing Real-world AI Agent Privacy

cs.AI ·2026-10-05 ·Shouju Wang, Haopeng Zhang
similarity 0.60
Abstract

The rapid advancement of LLM agents has enabled systems to autonomously perform complex tasks through external tools, but their growing access to personal data introduces significant privacy risks. Existing benchmarks primarily evaluate LLM agent privacy through simulated trajectories and outcome-based metrics, limiting their ability to capture privacy risks arising during multi-step agent execution. In this work, we introduce AgentPrivArena, a framework for evaluating privacy risks in realistic LLM agent workflows. AgentPrivArena integrates authentic MCP tools and self-hosted services within a reproducible execution environment. We further propose trajectory-level privacy metrics that quantify unnecessary information access beyond final response leakage. Building on this framework, we introduce AgentPrivAudit, a runtime auditing approach for monitoring privacy violations during agent execution. Extensive experiments on state-of-the-art LLM agents reveal substantial privacy risks overlooked by existing evaluation paradigms, highlighting the importance of trajectory-level auditing for trustworthy agent deployment.

0.10

Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy

cs.CR stat.OT ·2026-10-14 ·Devansh Gupta, Cristóbal Guzman, Enayat Ullah
similarity 0.59
Abstract

Sequential data such as documents, conversations, and trajectories are naturally partitioned across users, motivating privacy guarantees that protect each user's entire trajectory. We initiate the study of privately estimating the transition matrix of a discrete ergodic Markov chain from N independent trajectories of length T, with arbitrary initial distributions, under maximum row-wise ell 1 error. Besides N, T, and the number of states, our bounds depend on the minimum stationary probability and the pseudo-spectral gap, which govern state coverage and mixing. Under item-level privacy, we give upper and lower bounds that separate the costs of sampling, state occupancy and mixing, and privacy. Under user-level privacy, we reduce the problem for sufficiently long trajectories to private product distribution estimation. Along the way, we establish optimal user-level private bounds for estimating products of discrete distributions, which may be of independent interest. In the user level setting, our bounds are nearly tight in the large T regime, whereas in the item-level setting, our bounds as tight up-to a non-private term.

0.25

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