Cohere: Managing Differential Privacy in Large Scale Systems

Cohere: Managing Differential Privacy in Large Scale Systems

Speakers: Nicolas Küchler; Emanuel Opel; Hidde Lycklama; Alexander Viand; Anwar Hithnawi

Conference: IEEE S&P

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

Overview

The talk "Cohere: Managing Differential Privacy in Large Scale Systems" by Nicolas Küchler and his co-authors addresses the significant challenges organizations face when attempting to deploy Differential Privacy (DP) across multiple, interacting applications that share user data. While DP offers a rigorous framework for guaranteeing privacy in statistical data releases, its practical implementation in complex, real-world systems often leads to suboptimal privacy guarantees, inefficient resource allocation, and a lack of continuity. This presentation introduces Cohere, a novel system designed to overcome these hurdles by providing system-wide DP guarantees.

Cohere tackles the critical problem of cumulative privacy loss, which arises when individual applications, each with their own DP mechanisms, draw from a shared pool of user data. Existing DP frameworks typically offer only per-application guarantees, failing to account for the aggregated privacy cost. The speakers highlight that without a coordinated approach, the true privacy leakage can be severely underestimated, undermining the very purpose of DP. Cohere's innovative approach unifies diverse DP libraries, leverages fine-grained data access patterns, and introduces sophisticated budget management strategies to ensure robust, system-wide privacy.

This work is particularly important for any organization that collects and analyzes sensitive user data, from government agencies releasing public statistics to tech companies gathering telemetry or training machine learning models. By offering a solution that not only enforces strong privacy guarantees but also optimizes data utility and ensures the long-term viability of DP deployments, Cohere provides a crucial blueprint for responsible and effective data stewardship in the era of big data and increasing privacy regulations.

Background

▶ Watch: Introduction to Differential Privacy and its challenges (0:00)

The fundamental problem that Differential Privacy seeks to address is the desire to extract valuable insights from datasets containing sensitive individual information without compromising the privacy of any single person. This challenge is pervasive across various domains: academic researchers often need access to industry data, service providers publish public statistics, and government agencies like the US Census Bureau must balance data utility with individual privacy. Historically, attempts to solve this via anonymization techniques or reporting only aggregate statistics have proven inadequate, repeatedly failing to prevent re-identification attacks. The speakers emphasize that these "best effort" or heuristic privacy measures are insufficient in practice.

Introduced in 2006, Differential Privacy (DP) emerged as the state-of-the-art solution, offering a formal, mathematical definition of privacy in the context of statistical data releases. DP requires that the output of an analysis remains "almost indistinguishable" whether an arbitrary individual's data is included or excluded from the dataset. This property is quantified by privacy parameters Epsilon (ε) and Delta (δ), where smaller values indicate stronger privacy. To achieve this, DP mechanisms introduce carefully calibrated noise into computations, just enough to mask individual contributions while preserving aggregate trends. A critical aspect of DP is the noise-accuracy trade-off: stronger privacy (smaller ε) means more noise and thus less accurate results, while weaker privacy (larger ε) yields more accurate results but provides less meaningful guarantees. Choosing the appropriate ε and δ is paramount to ensuring both data usefulness and robust privacy.

DP has gained significant traction since its inception. Early notable deployments include Google Chrome's collection of telemetry data in 2014, and more recently, its impactful use in the US 2020 Census. DP has also found its way into privacy regulations as a recommended practice. The increasing adoption by industry players since 2017 has spurred efforts in developing specialized tooling. However, the current ecosystem for DP development is fragmented, with various libraries enabling DP computations for specific workloads. The core issue Cohere addresses stems from this fragmentation: while individual DP frameworks provide near-optimal privacy guarantees in isolation, they fail to account for the cumulative privacy impact when multiple applications access the same users' data. This leads to a risk of underestimating the real privacy costs and necessitates a system-wide approach to manage a shared privacy budget as a scarce resource across all DP applications.

Key Findings

▶ Watch: Introducing Cohere: System-wide differential privacy solution (3:00)

Cohere's central contribution is the establishment of a system-wide differential privacy management framework that addresses the inherent complexities of deploying DP in large-scale, multi-application environments. The system achieves this by tracking a shared privacy state across all applications, moving beyond the limitations of per-application privacy guarantees.

A key finding is Cohere's ability to unify the application layer despite the diversity of existing DP frameworks. Instead of treating applications as black boxes, Cohere intercepts their internal "noise plans" – the sequence of fundamental DP mechanisms they employ – and presents them in a standardized, unified manner. This allows for a joint white-box analysis across different systems, which is vastly superior to simply composing individual Epsilon-Delta guarantees. Critically, Cohere leverages Renyi Differential Privacy (RDP) for composition, which offers significantly better guarantees and efficiency compared to traditional Epsilon-Delta composition, especially for complex workloads.

Furthermore, Cohere significantly enhances privacy analysis by exploiting data access patterns. It moves beyond basic parallel composition for disjoint user groups to more sophisticated block composition. Its innovation lies in defining blocks not by specific user subsets, but by hypothetical views of users differentiated by partitioning attributes (e.g., country, year of birth). This fine-grained analysis allows the system to run more applications or achieve more accurate results for the same privacy budget, as it better models the actual privacy cost based on which specific user attributes are touched. The system also incorporates amplification via subsampling, reducing privacy costs when only a percentage of the population is required for an analysis.

Finally, Cohere tackles the critical challenge of privacy budget management and continuity. Recognizing the privacy budget as a finite and scarce resource, Cohere formulates the allocation problem as a variant of the multi-dimensional knapsack program, where each block corresponds to a dimension. To make this high-dimensional problem tractable, it introduces a segmentation strategy that collapses related blocks into single dimensions for optimization. To ensure system continuity and prevent budget depletion without undermining DP guarantees (as periodic budget refreshes would), Cohere proposes a user rotation mechanism. This exploits the steady influx of new users in large systems, retiring users whose privacy budget consumption reaches a threshold and replacing them with new ones, while carefully managing potential biases.

In its evaluation, Cohere demonstrated substantial improvements over existing approaches like PrivateCube. For a mixed workload of machine learning and analytics tasks, Cohere achieved a 1.5x improvement in the percentage of accepted requests when optimizing for quantity. More impressively, when optimizing for a realistic utility metric that factors in the value and priority of applications, Cohere yielded a 9x increase in overall utility, underscoring the profound impact of its fine-grained privacy analysis and sophisticated allocation strategies.

Technical Deep Dive

▶ Watch: Cohere's key challenges: budget allocation and continuity (3:40)

Cohere's technical innovations span several layers, from unifying diverse DP frameworks to sophisticated budget management and resource allocation.

Unifying the Application Layer

The core challenge in integrating multiple DP applications is the fragmentation of the existing DP ecosystem. Different frameworks support varying queries, domain-specific techniques, and privacy analysis methods. Simply composing their individual Epsilon-Delta guarantees often leads to highly suboptimal overall privacy costs. Cohere addresses this by adopting a white-box analysis approach.

Instead of treating each application as a black box, Cohere intercepts the internal "noise plan" of each DP application. These noise plans are essentially a sequence of fundamental DP mechanisms (e.g., Laplace mechanism, Gaussian mechanism) that are applied to introduce noise. By representing these plans in a unified manner, Cohere can perform a joint analysis across diverse DP systems as a global composition of a small number of fundamental mechanisms.

Crucially, this white-box view allows Cohere to move beyond the inefficient Epsilon-Delta composition. Instead, it utilizes Renyi Differential Privacy (RDP). RDP is a more powerful privacy accounting framework that tracks a "Renyi divergence" instead of just Epsilon and Delta. It offers significantly tighter composition guarantees for a wide range of mechanisms, making it an attractive choice for system-level privacy analysis where many mechanisms are composed. RDP is relatively efficient and provides a simple composition rule, which is beneficial from a systems perspective.

Enhancing Privacy Analysis at the System Level

Beyond unifying the application layer, Cohere further enhances privacy analysis by leveraging the way applications access data.

1. Parallel Composition: A well-known property of DP is that if mechanisms are applied to data from disjoint groups of users, the total privacy cost is simply the maximum cost incurred by any single group. This is known as parallel composition. Cohere can model this separation effectively.

1. Block Composition: In practice, applications often access overlapping subsets of users. To account for this, Cohere employs block composition, a generalized accounting technique that tracks privacy costs for various subsets of users, organized into "blocks." The effectiveness of block composition heavily depends on how these blocks are instantiated.

• Cohere's Innovation: Partitioning Attributes: Existing work often equates blocks with specific subsets of users. Cohere takes a more abstract approach: blocks correspond to hypothetical views of users differentiated by their attributes. For example, instead of specific user IDs, blocks could be defined by "users from France" or "users born in 1990." These are called partitioning attributes. The only requirement is that the schema for these attributes (e.g., the list of all possible countries) is known in advance. The system does not need to know which specific user belongs to which country; it just defines the potential partitions. This fine-grained prior analysis allows Cohere to massively benefit from applications' actual access patterns, improving the overall analysis by allowing more applications to run or achieving more accurate results for the same privacy guarantees.

1. Amplification via Subsampling: Many analytical tasks do not require access to the entire population of users to be useful. When an analysis can be performed on a percentage of the population (e.g., 10% of users), Cohere applies amplification via subsampling. This technique significantly reduces the privacy cost of each application, thereby improving the joint privacy analysis even further.

Collectively, these techniques create a management layer that supports a fine-grained privacy accounting scheme, maintaining a concurrent privacy filter using RDP for each block to enforce a system-wide privacy budget. Applications express their requirements as a noise plan, filter conditions on partitioning attributes, and a percentage for subsampling.

Privacy Budget Management and Continuity

Even with a fine-grained analysis, the finite privacy budget is a scarce resource that needs careful allocation and continuity guarantees.

1. User Rotation for Continuity: In practical deployments, the issue of budget depletion is often "solved" by periodically refreshing user privacy budgets. However, this fundamentally undermines the long-term guarantees of DP. Cohere proposes an innovative solution: user rotation. Large systems typically have a steady influx of new users. While individual user budgets must be finite, Cohere exploits this influx by retiring users whose past privacy consumption reaches a predefined threshold and replacing them with new users. This replenishes the overall available budget without violating individual privacy guarantees. The speakers acknowledge that this rotation must be carefully implemented to minimize additional tracking, maintain balanced budget usage, and provide clear semantics for DP applications, specifically addressing the risk of creating a biased population of "active" users. The insight is that these active groups of users can be seen as another dimension in the blocking scheme, allowing Cohere to integrate this into its existing fine-grained privacy analysis.

1. Resource Allocation: Given a set of application requests, each with its privacy and data requirements, Cohere must determine which combination of requests to allow without violating the budget constraints from the shared privacy state.

• Objective Function: Simply maximizing the number of accepted applications is suboptimal, as low privacy costs often imply higher error rates. Cohere aims to maximize a more generic utility metric that encodes the value of a result of a given accuracy to an organization, factoring in the relative priority of the application.
• Optimization Problem: Due to DP composition with partitioning attributes, determining the optimal combination of requests is non-trivial. Cohere formulates this as a variant of the multi-dimensional knapsack program. Each block (defined by partitioning attributes and potentially user rotation groups) corresponds to a dimension in the knapsack problem.
• Taming Dimensionality with Segmentation: A challenge arises because, to achieve the most fine-grained analysis, there can be a massively high number of dimensions, dependent on the domain size of the partitioning attributes. Cohere addresses this with a segmentation strategy. A "segment" is defined as a set of blocks that will be treated identically by any allocation and captures the content requests. By analyzing past allocations and current requests, Cohere can collapse the potentially large number of blocks within a segment into a single dimension in the knapsack problem. This significantly reduces the dimensionality of the optimization problem, making it far more manageable to solve in practice.

Cohere therefore provides a holistic system for managing differential privacy, unifying diverse applications, optimizing privacy analysis through fine-grained data access patterns, and ensuring both efficient budget allocation and long-term system continuity.

Demo / Proof of Concept

▶ Watch: Unifying application layer with white-box analysis and Renyi DP (4:40)

While the talk did not feature a live demonstration of Cohere in action, the speakers presented a comprehensive evaluation of the system's performance through simulations. This evaluation was designed to compare Cohere's effectiveness against existing approaches in realistic scenarios involving complex workloads and preferences.

The simulation involved a scenario with weekly allocations of privacy budget over a period of 40 weeks. Cohere was benchmarked against PrivateCube, a related work that extends the Kubernetes orchestration system for privacy resources. PrivateCube, while also addressing multi-dimensional knapsack problems for allocation, does not support Cohere's fine-grained privacy analysis capabilities.

Both Cohere and PrivateCube were instantiated with three different approaches to solve the underlying optimization problem:

1. A greedy first-come-first-serve baseline.
2. Two heuristic-based approaches designed to optimize resource allocation.

The workload used in the evaluation was a mixture of machine learning and analytics tasks, reflecting the diverse demands typically found in large-scale systems. The results were presented in two key areas:

1. Maximizing the number of accepted requests: In this scenario, where the goal was simply to accommodate as many applications as possible under a fixed privacy budget, Cohere achieved a 1.5x improvement in the percentage of accepted requests compared to PrivateCube. This demonstrates Cohere's superior ability to efficiently utilize the privacy budget due to its unified and fine-grained analysis.

1. Optimizing for a realistic utility metric: Recognizing that not all requests are equally valuable, the evaluation also considered a more realistic utility metric that encodes the importance and value of an application's output at a given accuracy level. When optimizing for this complex utility metric, Cohere demonstrated a remarkable 9x increase in overall utility for the mixed workload.

These evaluation results strongly highlight the importance and effectiveness of Cohere's fine-grained privacy analysis and sophisticated allocation strategies for mixed workloads with complex preferences. The substantial gains in both accepted requests and, more importantly, overall utility, underscore Cohere's potential to enable significantly more valuable data insights while rigorously upholding system-wide privacy guarantees.

Defensive Implications

▶ Watch: Enhancing privacy analysis with parallel and block composition (6:10)

The insights and solutions presented by Cohere have profound defensive implications for organizations grappling with the complexities of data privacy in large-scale systems. Defenders, responsible for safeguarding sensitive user data and ensuring compliance, should consider the following:

1. Acknowledge Cumulative Privacy Loss: The most critical takeaway is to move beyond the illusion of safety provided by per-application DP guarantees. Organizations must recognize that every application accessing shared user data contributes to a cumulative privacy loss. A system-wide approach like Cohere is essential to accurately account for this and prevent unintended privacy breaches.

1. Implement System-Wide DP Management: Instead of relying on fragmented DP libraries, organizations should invest in or develop a centralized system for managing their privacy budget. This involves tracking a shared privacy state across all data-consuming applications, ensuring consistent enforcement of privacy parameters (Epsilon and Delta).

1. Adopt Advanced Privacy Accounting: Organizations should transition from simpler Epsilon-Delta composition methods to more robust and efficient techniques like Renyi Differential Privacy (RDP). RDP offers tighter composition guarantees, allowing for more utility from the same privacy budget, or stronger privacy for the same utility.

1. Leverage Data Access Patterns: Defenders should encourage the design of applications that clearly articulate their data access patterns. By utilizing partitioning attributes (e.g., geographic regions, demographic groups) and amplification via subsampling where appropriate, organizations can optimize their privacy budget allocation, allowing for more analyses or higher accuracy without compromising privacy. This requires a deeper understanding of how data is accessed and used.

1. Plan for Privacy Budget Continuity: The notion of a finite privacy budget necessitates a long-term strategy for continuity. Instead of risky periodic budget resets, organizations should explore user rotation mechanisms as proposed by Cohere. This requires careful system design to manage user lifecycles, track individual privacy consumption, and ensure that new users can replenish the overall budget without introducing bias or undermining DP guarantees.

1. Prioritize Based on Utility: When allocating privacy budget, organizations should move beyond a simple "first-come, first-served" or "maximize accepted requests" approach. Instead, they should define and optimize for a generic utility metric that reflects the strategic importance and value of each application's output. This ensures that the most critical insights are prioritized while maintaining privacy.

1. Embrace Multi-Dimensional Optimization: The allocation problem is complex, resembling a multi-dimensional knapsack problem. Defenders should understand that sophisticated techniques, potentially involving segmentation strategies, are required to manage this complexity and allocate resources effectively, especially in environments with numerous data attributes and application requests.

By adopting these defensive strategies, organizations can build more robust, privacy-preserving data ecosystems that not only comply with regulations but also foster trust and enable valuable data-driven decision-making without jeopardizing individual privacy.

Key Takeaways

• System-wide DP Management is Crucial: Relying on per-application Differential Privacy guarantees is insufficient; organizations must adopt a system-wide approach to account for cumulative privacy loss when multiple applications access shared user data.
• Cohere Unifies Diverse DP Frameworks: The system effectively integrates applications built with different DP libraries by intercepting noise plans and using Renyi Differential Privacy (RDP) for superior, white-box composition guarantees.
• Fine-Grained Analysis Maximizes Utility: Cohere leverages data access patterns, particularly partitioning attributes and amplification via subsampling, to enable a more precise privacy analysis, leading to significantly more utility (e.g., more applications or accurate results) from the same privacy budget.
• Budget Allocation as a Multi-Dimensional Knapsack Problem: The finite privacy budget is a scarce resource managed through a sophisticated allocation strategy formulated as a multi-dimensional knapsack problem, optimized using a segmentation strategy to handle high dimensionality.
• User Rotation Ensures Budget Continuity: Cohere addresses budget depletion by implementing a user rotation mechanism that exploits the influx of new users, retiring old users and replenishing the overall privacy budget without compromising DP guarantees.
• Significant Performance Gains: Evaluations show Cohere achieving a 1.5x improvement in accepted requests and a remarkable 9x increase in utility for mixed machine learning and analytics workloads compared to existing approaches like PrivateCube, demonstrating the tangible benefits of its design.

About the Speaker(s)

The talk was presented by Nicolas Küchler, Emanuel Opel, Hidde Lycklama, Alexander Viand, and Anwar Hithnawi. While specific biographical details were not provided during the presentation, their collective research focuses on the intersection of privacy, systems, and large-scale data management, particularly in the context of designing and deploying robust Differential Privacy solutions for complex, real-world applications. Their work aims to bridge the gap between theoretical privacy guarantees and practical system challenges.