Frequency Estimation of Correlated Multi-attribute Data under Local Differential Privacy

Shafizur Rahman Seeam (Paper author · Rochester Institute of Technology), Ye Zheng (Paper author · Rochester Institute of Technology), Yidan Hu (Paper author · Rochester Institute of Technology)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Moose

Overview

In an era where modern devices constantly collect vast amounts of multi-attribute data – from heartbeats and location on smartphones to various user preferences – the challenge of protecting user privacy while still enabling valuable data analysis is paramount. This talk, presented by Shafizur Rahman Seeam from Rochester Institute of Technology, addresses a critical limitation in existing privacy-preserving data collection mechanisms: their failure to account for inherent correlations between different attributes. Traditional approaches often treat each attribute independently, leading to significant privacy-utility trade-offs, especially when dealing with high-dimensional data.

Watch on YouTube · Slides

Visual summary for Frequency Estimation of Correlated Multi-attribute Data under Local Differential Privacy by Shafizur Rahman Seeam, Ye Zheng, Yidan Hu
Visual summary for Frequency Estimation of Correlated Multi-attribute Data under Local Differential Privacy by Shafizur Rahman Seeam, Ye Zheng, Yidan Hu

Key moments

  1. 0:00 Introduction: Multi-attribute data privacy problem
  2. 2:00 LDP challenges for multi-attribute frequency estimation
  3. 3:30 Key idea: Leveraging attribute correlation for privacy
  4. 4:30 Proposed two-phase framework for correlated data
  5. 5:50 Deriving and calculating the reuse probability (PY)
  6. 7:00 Experimental results: Improved scaling with more attributes
  7. 8:00 Impact of correlation and real-world dataset analysis
  8. 8:40 Conclusion: Leveraging correlation for better performance

Frequency Estimation of Correlated Multi-attribute Data under Local Differential Privacy

Speakers: Shafizur Rahman Seeam (Paper author, PhD student, Rochester Institute of Technology); Ye Zheng (Paper author, Rochester Institute of Technology); Yidan Hu (Paper author, Rochester Institute of Technology)

Conference: PETS

YouTube: https://www.youtube.com/watch?v=LUCFdzyXtfA

Overview

In an era where modern devices constantly collect vast amounts of multi-attribute data – from heartbeats and location on smartphones to various user preferences – the challenge of protecting user privacy while still enabling valuable data analysis is paramount. This talk, presented by Shafizur Rahman Seeam from Rochester Institute of Technology, addresses a critical limitation in existing privacy-preserving data collection mechanisms: their failure to account for inherent correlations between different attributes. Traditional approaches often treat each attribute independently, leading to significant privacy-utility trade-offs, especially when dealing with high-dimensional data.

The paper introduces a novel two-phase framework designed to enhance the accuracy of frequency estimation for correlated multi-attribute data under Local Differential Privacy (LDP). LDP is a robust privacy model that guarantees formal privacy by ensuring data distortion occurs directly on the user's device, preventing any single data point from being uniquely identifiable by an adversary. By strategically leveraging the dependencies between attributes, the proposed mechanism aims to significantly improve data utility (accuracy of estimates) without compromising the strong privacy guarantees of LDP, thereby offering a more practical solution for privacy-preserving data collection in real-world scenarios.

This research is particularly relevant for service providers, data scientists, and privacy engineers who seek to derive valuable insights from sensitive user data while adhering to stringent privacy regulations and ethical considerations. It presents a sophisticated yet practical method to overcome the inherent noise amplification associated with LDP when applied to complex, multi-attribute datasets, paving the way for more effective and privacy-conscious data analytics.

Background

▶ Watch: Introduction: Multi-attribute data privacy problem (0:00)

The pervasive collection of user data by modern devices, while enabling personalized services and improved recommendations, poses significant privacy risks. Individual attributes like age might not be uniquely identifying on their own, but when combined with others, such as zip code, they can easily pinpoint an individual. This aggregation of attributes necessitates robust privacy protection that originates directly from the user's device, rather than relying solely on server-side anonymization.

Local Differential Privacy (LDP) has emerged as a widely adopted framework to address this challenge, offering a formal privacy guarantee. In an LDP model, each user applies a private mechanism locally to their data before sending it to a central server. This local perturbation ensures that an adversary observing the transmitted data cannot ascertain with certainty whether a specific user contributed a particular data point, with this uncertainty bounded by a privacy parameter, epsilon (ε). A smaller epsilon implies stronger privacy but typically comes at the cost of lower data utility (i.e., less accurate aggregate statistics).

While frequency estimation under LDP is a well-studied area for single attributes, extending it to multi-attribute data introduces considerable complexity and challenges. Existing baseline solutions often fall short:

  1. Split Budget (SPL): This naive approach uniformly divides the total privacy budget (epsilon) among all attributes. Consequently, each attribute receives a smaller budget, leading to increased noise and significantly reduced utility. This method "does not scale well" with an increasing number of attributes, as the noise quickly overwhelms the signal.
  2. Random Sampling + Fake Data: This family of solutions typically involves randomly sampling one attribute from a user's data and perturbing it with the full privacy budget. For the remaining attributes, "fake data" is generated, either synthetically or by drawing from prior distributions. The major drawback here is that these methods, including SPL, fundamentally do not consider attribute dependencies. Attributes like age and salary are often inherently correlated, and ignoring these relationships leads to suboptimal privacy-utility trade-offs, as valuable information that could be leveraged for better estimates is discarded.

The core problem, therefore, is to design an LDP mechanism for multi-attribute frequency estimation that can effectively leverage the inherent correlations between attributes to improve the accuracy of aggregate statistics without compromising the strong privacy guarantees of LDP. The existing solutions fail to exploit these dependencies, leading to inefficient use of the privacy budget and ultimately less accurate data.

Key Findings

▶ Watch: Key idea: Leveraging attribute correlation for privacy (3:30)

The central discovery and contribution of this research lie in demonstrating that leveraging attribute correlation can significantly enhance the accuracy of frequency estimation for multi-attribute data under Local Differential Privacy (LDP). The authors successfully developed and validated a novel two-phase framework that explicitly accounts for these dependencies, outperforming existing baseline LDP mechanisms, particularly as the number of attributes increases and attribute correlation strengthens.

Key findings include:

  • Improved Privacy-Utility Trade-off: The proposed mechanism achieves a superior balance between privacy (guaranteed by epsilon LDP) and utility (accuracy of frequency estimates) compared to traditional methods like Split Budget or Random Sampling + Fake Data, which disregard attribute correlations. By exploiting correlations, the mechanism can achieve higher accuracy for a given privacy budget, or equivalent accuracy with a tighter privacy budget.
  • Scalability with Attributes: The framework demonstrates significantly better scalability. As the number of attributes in the dataset increases, the performance gap between the proposed solution and baseline methods widens, indicating its particular effectiveness for high-dimensional data.
  • Direct Impact of Correlation: Empirical results confirm that the mean square error (MSE) of the estimates decreases proportionally with an increase in attribute correlation. This validates the core hypothesis that attribute dependencies are a valuable resource for privacy-preserving data aggregation.
  • Practical Feasibility with Limited Samples: The first phase of the protocol, which estimates marginals and correlation-related probabilities, requires only a small fraction of the total user base (typically 5-10%). This makes the two-phase approach practical and efficient, minimizing the initial overhead while still deriving crucial correlation information without accessing sensitive raw data.
  • Formal Privacy Guarantee: The entire two-phase framework is rigorously shown to satisfy epsilon Local Differential Privacy, ensuring that the enhanced utility does not come at the expense of weakened privacy protections.

In essence, the research provides a concrete and validated method for moving beyond attribute independence assumptions in LDP, unlocking new potential for accurate and private data analytics on complex, real-world datasets.

Technical Deep Dive

▶ Watch: Deriving and calculating the reuse probability (PY) (5:50)

The core technical innovation of this work lies in its two-phase framework for frequency estimation of correlated multi-attribute data under Local Differential Privacy (LDP). The fundamental idea is to leverage attribute correlations to minimize the noise introduced by LDP mechanisms, thereby improving the privacy-utility trade-off.

To illustrate the underlying principle, consider an idealized scenario with two perfectly correlated attributes, X1 and X2. If a user perturbs X1 to obtain Y1 using the full privacy budget, they can then deterministically derive Y2 from Y1 (since X1 and X2 are perfectly correlated, Y1 carries enough information to infer Y2). According to the post-processing property of differential privacy, any computation performed on privatized data (Y1) does not incur additional privacy cost. Thus, by perturbing only one attribute and deriving the other, the mechanism effectively privatizes both attributes with the budget of one, leading to significantly higher utility.

However, in the real world, attributes are rarely perfectly correlated, and the correlation itself is sensitive information that cannot be directly accessed. This is where the two-phase framework comes into play:

Phase One: Estimating Correlation Information

The objective of Phase One is to estimate the necessary correlation information without directly observing sensitive raw data. This is achieved by engaging a small sample of users, typically between 5% and 10% of the total user population.

  1. Local Perturbation (SPL): Each user in this sample employs the Split Budget (SPL) mechanism. This means they divide the total privacy budget (epsilon) uniformly among all their attributes and perturb each attribute independently. For instance, if there are d attributes, each attribute is privatized with an epsilon budget of ε/d.
  2. Server-Side Estimation: The server collects these perturbed data points from the sample users. It then debiases the results to obtain approximate marginal estimates for each attribute. These marginal estimates are essentially noisy approximations of the true frequency distributions of individual attributes.
  3. Calculating Reuse Probability (PY): Using these estimated marginals, the server then calculates a crucial parameter referred to as the reuse probability (PY). PY represents the probability that a non-pivot attribute's privatized output will "reuse" or be derived from the privatized output of a pivot attribute. This calculation involves an optimization problem: minimizing the mean square error (MSE) of the Phase Two estimator. The authors derive a closed-form solution for PY, which is a biased estimator, chosen specifically to prioritize error reduction over unbiasedness. Importantly, throughout this phase, the server does not access any sensitive raw data; all calculations are performed on locally perturbed data.

Phase Two: Leveraging Correlation for Improved Estimation

Once PY values are estimated in Phase One, the system transitions to Phase Two, involving the remaining (larger) portion of the user base. This phase is designed to exploit the learned correlation information for more accurate frequency estimation.

  1. Random Attribute Sampling (Pivot): Each user randomly selects one of their attributes to be the pivot attribute. This pivot attribute is then perturbed using the full privacy budget (epsilon).
  2. Non-Pivot Attribute Generation (Reuse): For all other attributes (the non-pivot attributes), instead of perturbing them independently, the user generates their privatized output based on the privatized output of the pivot attribute and the pre-calculated PY. Specifically, the non-pivot attribute's privatized value is generated by "reusing" the pivot's privatized output with a probability determined by PY. If reuse doesn't occur, a different perturbation strategy (not detailed in the talk but implied to be standard LDP) might be used. Since this generation of non-pivot attributes is a function applied to an already privatized value (the pivot attribute), it qualifies as post-processing. According to the post-processing property of differential privacy, this step incurs no additional privacy cost.
  3. Server-Side Aggregation: The server collects these privatized multi-attribute data points from all users in Phase Two and debiases them to compute the final frequency estimates.

Formal Privacy Guarantee

The entire two-phase protocol rigorously satisfies epsilon Local Differential Privacy (LDP). The authors demonstrate this through a combination of established LDP composition theorems:

  • Phase One: The SPL mechanism used in Phase One, when applied sequentially to multiple attributes, maintains epsilon LDP through sequential composition.
  • Phase Two: The core of Phase Two relies on privatizing the pivot attribute with the full budget and then deriving non-pivot attributes via post-processing, which inherently preserves LDP.
  • Overall Protocol: Since Phase One and Phase Two operate on disjoint sets of users, their combined privacy guarantee can be established using parallel composition. This ensures that the overall mechanism, from initial data collection to final estimation, provides a strong, quantifiable privacy guarantee.

The design of PY, the two-phase interaction, and the reliance on LDP composition theorems are crucial to the technical elegance and effectiveness of this approach, allowing for superior utility by leveraging correlations without sacrificing privacy.

Demo / Proof of Concept

▶ Watch: Experimental results: Improved scaling with more attributes (7:00)

While the talk did not feature a live software demonstration, the authors provided compelling empirical evidence from experiments on both synthetic and real-world datasets to serve as a proof of concept for their proposed two-phase framework. The results consistently highlighted the superior performance of their mechanism compared to existing baselines.

The key experimental findings were presented through graphical representations, primarily focusing on the mean square error (MSE) as a measure of estimation accuracy.

  1. Overall Performance Against Baselines: The proposed solution (consistently depicted as a red line in the graphs) demonstrated significantly lower MSE across various privacy regimes (different epsilon values) and dataset characteristics. This indicated that for a given level of privacy, their mechanism yielded more accurate frequency estimates than baseline methods like Split Budget or Random Sampling + Fake Data.
  2. Scalability with Number of Attributes: A critical aspect of the evaluation was how the performance scaled with an increasing number of attributes. The results showed that as the number of attributes grew, the performance difference between the proposed mechanism and the baselines widened considerably. This suggests that the correlation-leveraging approach becomes even more advantageous in high-dimensional data settings, where traditional methods struggle due to noise amplification.
  3. Effect of Attribute Correlation: The experiments explicitly validated the core hypothesis regarding correlation. As the correlation (represented by 'rho' in the graphs) between attributes increased, the MSE of the proposed mechanism decreased significantly. In contrast, the baselines, which do not leverage correlation, showed no such improvement, reinforcing the effectiveness of the two-phase framework's design.
  4. Phase One Sample Size: The authors also investigated the optimal number of users required for Phase One to accurately estimate the marginals and reuse probabilities. Their findings indicated that a relatively small sample, typically between 5% and 10% of the total user population, was sufficient to achieve robust estimates, making the initial overhead of Phase One practical and efficient.
  5. Real-World Data Validation: Beyond synthetic data, the mechanism was tested on real-world datasets. The general trend of superior performance held true, mirroring the results from synthetic experiments. However, an interesting anomaly was observed with the Mushroom dataset. In this specific case, one of the baseline solutions performed better than the proposed mechanism. The speaker attributed this to two factors: the Mushroom dataset exhibits low attribute correlation and has extremely skewed marginal distributions. This particular finding acknowledges a limitation of the correlation-based approach – its benefits are most pronounced when attributes indeed have meaningful correlations, and its performance might be challenged by highly unusual marginal distributions.

In summary, the empirical results robustly demonstrate that by explicitly leveraging attribute correlation through its two-phase design, the proposed mechanism achieves a superior privacy-utility trade-off for multi-attribute frequency estimation under LDP, especially for datasets with higher dimensionality and stronger attribute dependencies.

Defensive Implications

▶ Watch: Conclusion: Leveraging correlation for better performance (8:40)

The research presented by Shafizur Rahman Seeam offers significant defensive implications, not in the traditional sense of patching vulnerabilities or detecting attacks, but by providing a more robust and effective tool for privacy-preserving data collection and analysis. For organizations and service providers that collect sensitive multi-attribute user data, the findings suggest a path to:

  1. Enhance User Privacy Guarantees: By adopting this two-phase LDP framework, organizations can offer stronger, formally guaranteed privacy to their users. The epsilon LDP guarantee means that even if an adversary gains access to the collected, privatized data, they cannot uniquely identify individuals with any high degree of certainty. This builds trust and aligns with growing privacy regulations like GDPR and CCPA.
  2. Improve Data Utility Under Privacy Constraints: A common challenge with LDP is the trade-off between privacy and the utility of the aggregated data. Previous methods often resulted in very noisy estimates, making the collected data less useful for analysis and service improvement. This new mechanism allows organizations to obtain more accurate frequency estimates for multi-attribute data at a given privacy budget, or achieve the same accuracy with a tighter privacy budget (smaller epsilon), thereby making privacy-preserving analytics more practical and insightful.
  3. Enable Richer Data Collection: With the improved utility, organizations can be more confident in collecting and analyzing multi-attribute data, which often contains richer insights than single-attribute data. This allows for better personalized recommendations, more effective policy decisions, and a deeper understanding of user behavior, all while maintaining strong privacy protections.
  4. Strategic Resource Allocation for Privacy: The finding that only a small sample of users (5-10%) is needed for Phase One to estimate correlation information is a crucial practical implication. This means that the more resource-intensive initial phase can be limited to a small subset of the user base, optimizing computational and communication overhead while still benefiting the entire population in Phase Two.
  5. Guidance for Mechanism Selection: The analysis, particularly the observation with the Mushroom dataset, provides valuable guidance for defenders. It highlights that the benefits of this correlation-aware mechanism are most pronounced when attributes indeed exhibit significant correlations. For datasets with low correlation or highly skewed marginals, other LDP mechanisms might still be competitive or even preferable. This encourages a data-driven approach to selecting the most appropriate privacy-preserving technique.

In essence, this work empowers data custodians to "defend" user privacy more effectively while simultaneously "defending" the utility of their data. It's a proactive defense strategy that strengthens the foundation of privacy-preserving data analytics, making it a more viable and attractive option for modern data-driven services.

Key Takeaways

  • Correlation Matters for LDP: Existing Local Differential Privacy (LDP) mechanisms for multi-attribute data often ignore inherent correlations between attributes, leading to suboptimal privacy-utility trade-offs.
  • Two-Phase Framework for Enhanced Utility: The proposed two-phase framework effectively leverages attribute correlations to significantly improve the accuracy of frequency estimates under LDP.
  • Formal Epsilon LDP Guarantee: The entire protocol is rigorously shown to satisfy epsilon LDP, ensuring strong, formal privacy protection for user data.
  • Scalability for High-Dimensional Data: The mechanism's performance advantages become more pronounced as the number of attributes increases, making it particularly suitable for complex, high-dimensional datasets.
  • Efficient Correlation Estimation: Only a small percentage of users (typically 5-10%) are required in the first phase to estimate the necessary correlation parameters (reuse probabilities), making the approach practical and resource-efficient.
  • Improved Balance for Data Custodians: This research provides a powerful tool for organizations to collect richer, more accurate multi-attribute data while maintaining robust user privacy, fostering trust and enabling better services.

About the Speaker(s)

The research was presented by Shafizur Rahman Seeam, a PhD student at Rochester Institute of Technology. He is one of the paper's authors, along with Ye Zheng and Yidan Hu, also affiliated with Rochester Institute of Technology. Their work focuses on advancing privacy-preserving data analysis, specifically addressing the challenges of frequency estimation in multi-attribute datasets under the framework of Local Differential Privacy. Their collective expertise contributes to developing practical and theoretically sound solutions for balancing data utility with stringent privacy requirements.

Reviews

Dr. Zero (Offensive Security Researcher) — STRONG ACCEPT

Seeam and the RIT team drop a genuinely clever two-phase framework for Local Differential Privacy that stops noise amplification from destroying multi-attribute datasets. By weaponizing the post-processing property of differential privacy, they get correlated attributes for free on the exact same epsilon budget. It's mathematically sound, practical, and a massive upgrade over naive budget-splitting.

Heather Calloway (CISO) — SOLID

This is for your privacy engineering lead, not your board. It provides a mathematical framework for extracting accurate product analytics without holding the toxic, raw user data that creates breach liability.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026