💻 computer science

REAEDP: Entropy-Calibrated Differentially Private Data Release with Formal Guarantees and Attack-Based Evaluation

This paper proposes REAEDP, a differential privacy framework that combines entropy-calibrated histogram release and a synthetic-data mechanism with formal guarantees and attack-based evaluation to effectively balance privacy protection and data utility against inference threats.

Original authors: Bo Ma, Jinsong Wu, Wei Qi Yan

Published 2026-03-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Bo Ma, Jinsong Wu, Wei Qi Yan

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 the librarian of a massive, secret library containing the personal stories of thousands of people. You want to share some interesting statistics about the library with the public—like "how many people read mystery novels" or "what the average age of our readers is."

However, you have a problem: The "Whispering Game" of Data.

If you just hand over a list of numbers, a clever detective (an attacker) might be able to figure out exactly who is in the library, what they read, or even if they are sick. They can do this by cross-referencing your list with other public data (like a phone book or social media). This is called a privacy leak.

To stop this, you decide to add a little bit of "static" or "noise" to your numbers before sharing them. This is the idea behind Differential Privacy. It's like wearing a foggy mask; the crowd can still see your general shape (the statistics), but they can't make out your specific face (your identity).

But here's the tricky part: How much fog do you add?

Too little fog? The detective can still see your face.
Too much fog? The crowd can't see your shape at all, and the statistics become useless.

This paper introduces a new system called REAEDP (pronounced "Read-P"). Think of it as a Smart Fog Machine that solves three big problems:

1. The "Surprise Meter" (Entropy Calibration)

Usually, librarians guess how much fog to add. This paper gives them a mathematical ruler called "Entropy Sensitivity."

The Analogy: Imagine you are measuring the "surprise" of a deck of cards. If the deck is all Aces, there is zero surprise. If it's a perfect mix of all cards, there is maximum surprise.
The Problem: When you change just one card in the deck (one person's data), how much does the "surprise level" change?
The Solution: The authors calculated a strict upper limit (a "speed limit") for how much that surprise can change. This allows them to add just enough fog to hide the individual card without blurring the whole deck. They call this Entropy-Calibrated Release.

2. The "Ghost Writer" (Synthetic Data)

Sometimes, instead of just sharing numbers, you want to share fake stories that look real but aren't real. This is called Synthetic Data.

The Analogy: Imagine a "Ghost Writer" who reads your secret library and writes a new book of stories. These stories have the same feel and patterns as the real ones, but the characters are made up.
The Problem: How do you know the Ghost Writer didn't accidentally copy a real person's story?
The Solution: The paper introduces a Privacy Test (a security checkpoint). Before the Ghost Writer publishes a story, it runs a test. It asks: "If I remove one real person from the library, would this story still look the same?" If the answer is "Yes," the story is safe to publish. If the answer is "No," the story is rejected. This ensures the "Ghost Writer" is truly creating new, safe data.

3. The "Detective Drill" (Attack-Based Evaluation)

Many papers just say, "Trust us, our math says it's safe." This paper says, "Let's hire a team of detectives to try and break it."

The Analogy: Instead of just locking the door and hoping no one picks the lock, you hire a professional burglar to try and break in.
The Result: They tested their system against two common types of attacks:
1. Membership Inference: "Is this specific person in the library?"
2. Record Linkage: "Can I match this person's data to their real identity?"
The Outcome: As they turned up the "fog" (privacy protection), the detectives got worse and worse at guessing. Eventually, their success rate dropped to the level of random guessing (like flipping a coin). This proves the system actually works in the real world, not just on paper.

The Big Picture: Why This Matters

Think of REAEDP as a Gold Standard Toolkit for data sharing.

Before: Data custodians were flying blind, guessing how much noise to add, often making data either too risky or too useless.
Now: They have a calibrated ruler (The Entropy Bound) to measure risk, a security checkpoint (The Privacy Test) for fake data, and a proven track record (The Detective Drills) showing that the system actually protects people.

In short: This paper gives us a way to share the "flavor" of our data without revealing the "ingredients" of any single person. It turns the scary world of data privacy into a manageable, measurable, and safe process.

1. Problem Statement

The release of sensitive data (e.g., health records, trajectories, recommendation logs) faces significant privacy threats, including membership inference, attribute inference, and record linkage. While Differential Privacy (DP) offers a formal framework to limit information leakage, existing approaches often suffer from three limitations:

Lack of Entropy Calibration: For histogram-based releases, standard DP mechanisms (like Laplace or Gaussian) require known sensitivity. However, the sensitivity of Shannon entropy (a natural utility measure for histograms) was not previously bounded in a form suitable for calibration.
Fragmented Frameworks: Entropy-based calibration, synthetic data generation, and formal DP analysis are often studied in isolation rather than within a unified pipeline.
Insufficient Evaluation: Many studies rely solely on utility metrics or theoretical bounds, lacking direct empirical evaluation against standard privacy attacks (e.g., membership inference) to verify if the protection holds in practice.

2. Methodology: The REAEDP Framework

The authors propose REAEDP, a unified framework combining entropy-calibrated histogram release, a synthetic-data mechanism, and rigorous attack-based evaluation.

A. Theoretical Foundations

Entropy Sensitivity Bounds (Theorem 3): The paper derives an explicit upper bound for the sensitivity of Shannon entropy ( $\Delta H$ ) under a replacement adjacency model (where two datasets of size $n$ differ by exactly one record).
- The bound is given by: $\Delta H \leq \frac{1}{n} \left( 2 + \frac{1}{\ln 2} + 2 \log_2 n \right)$ .
- This bound is extended to Rényi entropy ( $H_\alpha$ ), showing that sensitivity scales as $O(1/n)$ for any order $\alpha$ .
- Significance: This allows practitioners to calibrate the noise level for histogram releases based on the dataset size $n$ , ensuring the released entropy remains within a predictable error margin.
Synthetic Data Mechanism $F$ (Theorem 4): The authors introduce a synthetic-data generation mechanism $F$ operating in a Wiener-kernel (RKHS) setting.
- Mechanism: It uses a seed-dependent proposal distribution to generate candidate synthetic records.
- Privacy Test: A candidate is accepted only if it passes a probabilistic "privacy test" based on a partition of the dataset and a random variable $L$ .
- Guarantee: Under specific parameter conditions ( $k, t, \gamma, \epsilon_0$ ), the mechanism satisfies $(\epsilon, \delta)$ -Differential Privacy. The privacy parameters are defined as $\epsilon = \epsilon_0 + \ln(1 + \gamma/t)$ and $\delta = e^{-\epsilon_0(k-t)}$ .

B. Algorithmic Implementation

The framework operates in two modes:

Histogram Release: Computes empirical counts, adds calibrated Laplace noise based on the derived $\Delta H$ bound, and releases the noisy histogram.
Synthetic Release: Iteratively samples seeds and candidates, applying the privacy test until a valid synthetic record is generated.

3. Key Contributions

Explicit Sensitivity Bounds: The derivation of the first explicit sensitivity bound for Shannon and Rényi entropy under replacement adjacency, enabling calibrated noise addition for entropy-preserving releases.
Unified Framework: The integration of entropy calibration, a formally proven synthetic-data mechanism ( $F$ ), and empirical validation into a single pipeline.
Formal Guarantees for Synthetic Data: Establishing an $(\epsilon, \delta)$ -DP guarantee for the synthetic mechanism $F$ under the Wiener-kernel setting, addressing a gap in non-interactive synthetic data release.
Comprehensive Evaluation: A multi-faceted evaluation strategy combining:
- Theoretical bound validation.
- Baseline comparisons (Laplace vs. Gaussian).
- Attack-based evaluation: Explicit testing against Membership Inference Attacks (MIA) and linkage-style attacks.

4. Experimental Results

The framework was evaluated on multiple public tabular datasets (e.g., Amazon/Google Reviews, House Prices, Home Credit) and synthetic data.

Entropy Calibration:
- Empirical entropy changes ( $\hat{\Delta H}$ ) across various dataset sizes ( $n=50$ to $5000$) consistently remained below the theoretical bound derived in Theorem 3.
- The bound decreases as $O(1/n)$ , confirming its utility for calibration in large datasets.
Utility vs. Privacy Tradeoff:
- Synthetic Data: In the Wiener-kernel setting, increasing the penalty parameter $\rho$ reduced the noise, bringing the private mean closer to the original mean, demonstrating a controllable tradeoff.
- Baselines: Standard Laplace and Gaussian mechanisms showed comparable utility trends to the proposed entropy-calibrated approach.
Attack Resistance:
- Membership Inference (MIA): As the privacy parameter $\epsilon$ decreased, MIA accuracy and AUC scores dropped toward random-guess levels (0.5), indicating strong protection against membership inference.
- Linkage Attacks: Similarly, linkage-style attack performance degraded as privacy increased, confirming the mechanism's robustness against record linkage.
Pass Rates: The privacy test for mechanism $F$ maintained non-negligible pass rates even under strict privacy settings (large $k$ ), proving the mechanism is practically usable for generating synthetic data.

5. Significance and Conclusion

The REAEDP framework addresses a critical gap in privacy-preserving data release by bridging the divide between theoretical guarantees and practical utility.

Practical Utility: By providing an explicit sensitivity bound for entropy, it allows data custodians to release statistics with quantifiable error margins, moving beyond "black box" noise addition.
Robustness: The inclusion of attack-based evaluation demonstrates that the theoretical guarantees translate into real-world resistance against inference attacks.
Scalability: The framework is validated on diverse real-world tabular datasets, showing applicability beyond synthetic benchmarks.

Limitations & Future Work:
The authors note that the histogram approach depends on discretization (binning), which may be sensitive in high-dimensional spaces. Additionally, while the Wiener-kernel component offers a functional-space perspective, it relies on finite-dimensional approximations. Future work aims to extend the framework to attribute inference benchmarks, stronger adversarial models, and multimodal/federated data settings.

In summary, REAEDP provides a practically usable, theoretically grounded pipeline for releasing sensitive data that balances formal privacy guarantees with measurable utility preservation.