💻 computer science

Dependency-Aware Privacy for Multi-turn Agents

RootGuard is a novel privacy framework for multi-turn LLM agents that sanitizes private root values once and deterministically derives subsequent outputs, thereby preventing privacy degradation across turns and achieving significantly better privacy-utility tradeoffs compared to existing independent noising methods.

Original authors: Divyam Anshumaan, Sarthak Choudhary, Nils Palumbo, Somesh Jha

Published 2026-05-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Divyam Anshumaan, Sarthak Choudhary, Nils Palumbo, Somesh Jha

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a patient visiting a digital health assistant (an "LLM agent"). You need to share sensitive private data, like your blood pressure, weight, or lab results, so the assistant can calculate a diagnosis or risk score. However, the services the assistant talks to (the "adversarial services") might be untrustworthy. They could be hackers, they could be coerced by legal orders, or they might simply be curious and try to piece together your real identity from the numbers you share.

The Problem: The "Leaky Bucket" of Independent Noise

Currently, most privacy tools work like a leaky bucket. Every time the assistant sends a number to a service, it adds a little bit of "static" (noise) to hide the real value. This is called independent noising.

Here is the flaw:

Turn 1: You share your height. The assistant adds static.
Turn 2: You share your weight. The assistant adds new, different static.
Turn 3: The service asks for your BMI. The assistant calculates it from your noisy height and weight, then adds even more static to the result before sending it.

To the attacker, this looks like a treasure hunt. They get multiple independent glimpses of the same underlying truth. If they ask for the same thing twice, or ask for a derived value (like BMI) after asking for the parts (height/weight), they can average out the static. It's like trying to guess a secret number by listening to it whispered through a wall; if you hear it whispered three different times with different background noises, you can eventually figure out the real number. The more turns the attacker forces, the more "leaks" they get, and the less private you become.

The Solution: RootGuard (The "Master Blueprint")

The paper proposes a new system called RootGuard. Instead of adding noise every time a number is sent, RootGuard changes the strategy entirely.

The Analogy: The Master Blueprint
Imagine you have a secret recipe (your private data).

Old Way (Independent Noising): Every time you send a copy of the recipe to a chef, you scribble random notes on the paper, tear off a corner, and smudge the ink. If you send it to 10 chefs, you have 10 different smudged versions. A clever observer can compare all 10 to guess the original recipe.
RootGuard Way: You take your secret recipe and scribble the notes only once on the original master copy. You then lock this "noisy master copy" in a safe.
- When Chef A asks for the ingredients, you give them a photocopy of the noisy master.
- When Chef B asks for the final dish, you calculate it using the noisy master and give them the result.
- If Chef A asks again, you give them the exact same photocopy.

Because every single piece of information the attacker sees comes from that one noisy master copy, they cannot learn anything new by asking more questions. Whether they ask 1 time or 1,000 times, they are just looking at the same static-filled image. The privacy guarantee is locked in at the very beginning.

The "Double Asymmetry" Advantage

The paper highlights a fascinating twist called the Double Asymmetry:

For the Attacker (Independent Noising): Every extra question they ask makes their job easier. They get more data points to average out the noise. Their ability to guess your real data gets stronger with every turn.
For You (RootGuard): Every extra question the attacker asks actually makes the system better for you (in terms of utility). Since the attacker forces the system to use a larger total "privacy budget" (more noise allowed), RootGuard can spread that larger budget across your data roots. This means the noise per root can be lower, making the medical calculations more accurate, while your privacy stays exactly the same.

In short: The more the attacker tries to pry, the more accurate your medical results become under RootGuard, while their ability to guess your secrets stays flat. Under the old method, the more they pry, the more they learn.

Using "Domain Knowledge" to Get Smarter

RootGuard isn't just a static lock; it's a smart lock that understands the relationships between your data.

Level 1 (Dependencies): If you know that BMI is just a math formula based on Height and Weight, RootGuard realizes it doesn't need to add noise to BMI separately. It just calculates BMI from the noisy Height and Weight. This saves "privacy budget" (the allowance for how much noise you can add) so it can be used where it matters most.
Level 2 (Sensitivity): Some numbers matter more for a specific diagnosis than others. RootGuard looks at the medical formula (e.g., "Liver Fibrosis Score") and asks: "Which input causes the biggest change in the result?" It then gives more privacy budget (more noise) to the sensitive inputs and less to the ones that don't matter as much. This keeps the final diagnosis accurate while protecting the most critical secrets.

The Results: What the Paper Found

The authors tested this on 8 different medical scenarios (like calculating liver risk, heart disease risk, or anemia) using real health data from the CDC.

Accuracy: RootGuard was 2.6 to 3.8 times more accurate at producing the correct medical diagnosis compared to the old "independent noise" method.
Privacy: When attackers tried to reconstruct your real data by asking many questions, the old method failed miserably (their guesses got much better with every question). RootGuard remained completely invariant; the attacker learned no more after 16 questions than they did after the first one.
Real-World Test: They even ran this through a real AI agent (GPT-5.4 nano) making tool calls. The results held up perfectly, proving this isn't just theory—it works in a live, multi-turn conversation.

The Bottom Line

RootGuard treats your private data like a single source of truth that is protected once at the root. Everything else is just a calculation derived from that protected source. This prevents attackers from "cracking the code" by asking the same question in different ways, ensuring that your privacy doesn't degrade just because you need to have a long conversation with a digital assistant.

Technical Summary: Dependency-Aware Privacy for Multi-Turn LLM Agents

Problem Statement

The integration of Large Language Model (LLM) agents into sensitive domains (healthcare, finance, legal) creates a new privacy attack surface. Users delegate tasks to agents that interact with multiple external services via protocols like the Model Context Protocol (MCP). In multi-turn workflows, an adversary can combine independent data releases to reconstruct private user attributes.

Existing sanitization methods, such as Prϵmpt and CAPE, rely on metric differential privacy (mDP) but treat each data release independently. This independence assumption fails in multi-turn scenarios:

Benign Leakage: Cross-platform redundancy (sending the same root value to two services) or structural redundancy (sending a root and a derived value separately) causes the privacy budget to scale linearly with the number of services or derived functions.
Adversarial Leakage: An adversary can force repeated queries to average out noise ( $1/\sqrt{q}$ ) or request arbitrary derived functions. For nonlinear functions common in medical and financial workflows (e.g., BMI, FIB-4), independent noising of a derived value amplifies the distinguishability of the underlying root by the function's Lipschitz constant ( $L$ ), potentially exceeding the nominal privacy parameter by orders of magnitude.

The core problem is that without tracking dependencies between releases, every additional interaction degrades the user's privacy beyond the nominal budget, regardless of whether the leakage is benign or malicious.

Methodology: RootGuard

The authors propose RootGuard, a dependency-aware privacy mechanism designed for multi-turn agentic interactions. The core principle is to sanitize private "root" values exactly once and compute all subsequent releases deterministically from these noised roots.

System Architecture

Initialization: The user agent identifies sensitive root values ( $X$ ) and sanitizes them once using a differentially private mechanism ( $M_\epsilon$ ). These noised values ( $\hat{X}$ ) are stored in a sanitized cache.
Per-Turn Operation: When an adversary requests a value:
- If the request is for a root, the cached noised value is returned.
- If the request is for a derived value, it is computed deterministically from the cached noised roots.
- No fresh noise is drawn after initialization.
Trust Boundary: The adversary interacts only with the sanitized cache. By the Post-Processing Theorem of differential privacy, the adversary's view is no more informative than the initial root sanitization, regardless of the number of turns ( $t$ ) or the functions ( $f$ ) requested.

Exploiting Structural Knowledge

RootGuard utilizes public domain knowledge to optimize the privacy-utility tradeoff without weakening guarantees:

Level 1 (Inter-root Dependencies): If a declared root is a deterministic function of others (e.g., BMI from height and weight), the agent identifies true independent roots. Dependent roots are recomputed from noised parents, inheriting privacy at zero marginal cost (Theorem 3).
Level 2 (Target Sensitivity): If the intermediate target function $g$ (e.g., a clinical formula like FIB-4) is known, the agent allocates the privacy budget $\epsilon_i$ to roots based on their sensitivity to the target. The allocation follows a sensitivity-weighted rule: $\epsilon_i \propto (|h_i| \cdot D_i)^{1/2}$ , where $h_i$ is the partial derivative of the target function with respect to root $i$ , and $D_i$ is the domain width. This minimizes the expected error in the final clinical decision.

Theoretical Guarantees

Theorem 1 (DAG Privacy Guarantee): The privacy guarantee depends solely on the root sanitization parameters and is independent of the adversary's choice of functions or the number of interaction turns.
Theorem 2 (Distinguishability Amplification): Proves that independently noising a derived value amplifies the parent root's distinguishability by the function's Lipschitz constant $L$ .
Theorem 3 (Implied Privacy): Proves that adding noise to roots and post-processing them to derive values provides at least as strong privacy as noising the derived values directly.

Key Contributions

Formalization of Multi-Turn Agentic Privacy: The paper formalizes the privacy game for multi-turn interactions and proves that RootGuard's guarantee is invariant to the adversary's query count and function choices.
Proof of Amplification and Inheritance: It demonstrates that independent noising of derived values amplifies privacy loss (Theorem 2) while coordinated root noising allows derived values to inherit privacy for free (Theorem 3).
Sensitivity-Weighted Allocation: A method for allocating privacy budgets based on the sensitivity of the target function, minimizing target error while maintaining formal guarantees.
Empirical Validation: Extensive experiments on 8 medical diagnostic templates (derived from NHANES data) and a full end-to-end LLM deployment (GPT-5.4 nano) validating the mechanism.

Experimental Results

The evaluation compares RootGuard configurations (M-Roots, M-Opt) against independent noising (M-All) across three research questions:

RQ1: Target Utility

Metric: Weighted Mean Absolute Percentage Error (wMAPE) and Risk Class Error (RCE).
Findings: RootGuard significantly outperforms independent noising. At $\epsilon = 0.1$ and a budget of $B = (2k+1)\epsilon$ , M-Opt achieves 2.6 $\times$ lower wMAPE (7.8% vs. 20.3%) and 2.2 $\times$ lower Risk Class Error (7.0% vs. 15.7%) compared to M-All.
Double Asymmetry: As the adversary forces more turns ( $t$ ), RootGuard's utility improves (more budget available per root), while M-All's privacy degrades (accumulation of independent observations).

RQ2: Reconstruction Attacks

Metric: Reconstruction wMAPE under a Maximum A Posteriori (MAP) adversary.
Findings: Under M-All, reconstruction error decreases as the number of queries ( $q$ ) increases (e.g., dropping from 10.2% to 3.2% as $q$ goes from 1 to 16 at $\epsilon_r=0.1$ ). Under RootGuard, reconstruction error remains invariant to $q$ because repeated queries return the same cached value.

RQ3: Structural Analysis

Findings: The advantage of RootGuard is most pronounced for "compressing" formulas (e.g., FIB-4, HOMA) where the target function attenuates root noise. The budget allocation follows the predicted power law $\epsilon_i \propto (|h_i| \cdot D_i)^{0.5}$ , confirming the sensitivity-weighted strategy.

RQ4: End-to-End Deployment

Setup: A real-world simulation using a GPT-5.4 nano agent across 21,600 sessions.
Findings: The mechanism-level findings transfer to the LLM deployment. The ordering of performance (M-Opt > M-Roots > M-All) holds, and there were zero session-level compliance failures (no parse errors or malformed responses).

Significance and Claims

The paper claims that RootGuard fundamentally changes the privacy-utility tradeoff in multi-turn agent interactions. By shifting from stateless, independent sanitization to a stateful, dependency-aware approach, RootGuard ensures that:

Privacy is Constant: The adversary gains no additional information regardless of how many turns they force or what functions they compute.
Utility Improves with Turns: Additional interaction turns allow for a larger total privacy budget to be distributed across roots, improving accuracy without increasing privacy risk.
Robustness: The approach holds even under adversarial prompt injection or malicious service design, as all releases are post-processings of the initial noised roots.

The authors conclude that independent noising is fundamentally insufficient for multi-turn workflows involving correlated private values, and that dependency-aware sanitization is a necessary defense for deploying LLM agents in high-stakes domains. The work assumes perfect Named Entity Recognition (NER) for root identification and focuses on structured numeric data, leaving free-form text and noisy NER integration as future work.