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=FiBUDhQrBFs

Overview

In an era increasingly defined by data-driven insights, the challenge of leveraging vast datasets for research, service provision, and public statistics without compromising individual privacy has become paramount. This talk introduces Cohere, a novel system designed to address the complex challenges of deploying Differential Privacy (DP) in large-scale, multi-application environments. Presented by Nicolas Küchler and his co-authors, Cohere offers a sophisticated approach to enforcing system-wide DP guarantees by tracking and managing a shared privacy state across diverse applications, even when those applications are developed by different teams and utilize various DP libraries.

The talk highlights a critical gap in current DP implementations: while existing frameworks provide robust privacy guarantees for individual applications, they fail to account for the cumulative privacy loss when multiple applications interact with the same underlying user data. This oversight can lead to a significant underestimation of real privacy costs. Cohere tackles this by unifying the application layer, enhancing privacy analysis through a white-box view of mechanisms, and introducing innovative resource planning strategies, including user rotation and intelligent budget allocation. The system aims to enable organizations to derive maximum utility from their data while rigorously upholding privacy standards, preventing budget depletion, and optimizing resource distribution under complex preferences.

Background

▶ Watch: Introduction: Challenges of deploying differential privacy in large systems (0:00)

The concept of Differential Privacy (DP), introduced in 2006, has emerged as the state-of-the-art for formally defining and rigorously controlling privacy leakage in statistical data releases. Unlike heuristic anonymization techniques or simple aggregation, DP provides a strong, mathematical guarantee: the output of a computation will be "almost indistinguishable" whether an individual's data is included or excluded from the dataset. This property is achieved by introducing carefully calibrated noise into the computation, balancing data usefulness with privacy protection via parameters Epsilon ($\epsilon$) and Delta ($\delta$). A smaller $\epsilon$ and $\delta$ provide stronger privacy but may reduce data accuracy, necessitating a careful trade-off.

DP has progressed from academic interest to practical deployment, notably in the Google Chrome browser for telemetry data collection in 2014, and more significantly, in the US 2020 Census. Its recognition in privacy regulations underscores its importance. However, the practical deployment of DP in large organizations presents significant system-level challenges. The current developer ecosystem for DP is fragmented, with various libraries tailored for specific workloads. This fragmentation leads to a critical problem: existing frameworks provide only per-application guarantees. When multiple applications, possibly developed by different teams and using different DP libraries, all access the same user data, their individual privacy costs accumulate. Ignoring this cumulative impact risks underestimating the true privacy leakage and renders individual guarantees insufficient.

This cumulative privacy loss necessitates a system-wide DP guarantee, which Cohere aims to provide. Such a system must track a shared privacy state and manage a privacy budget—an acceptable level of leakage treated as a finite resource. The challenges involve coordinating between diverse applications, ensuring compatibility between different privacy analyses, allocating a scarce budget effectively under complex preferences, and enabling system continuity as the finite budget inevitably depletes over time. Cohere specifically targets these issues by proposing a unified approach to privacy accounting and resource management.

Key Findings

▶ Watch: History of DP adoption and fragmented tooling ecosystem (2:00)

Cohere introduces several key findings and contributions that significantly advance the practical deployment of Differential Privacy in large-scale systems. The core innovation lies in its ability to enforce system-wide DP guarantees by managing a shared privacy state across multiple, diverse applications.

1. Unified Application Layer and Improved Privacy Analysis: Cohere overcomes the fragmentation of DP tooling by providing a unified view of privacy mechanisms. Instead of treating applications as black boxes, it intercepts their noise plans and represents them using a common set of fundamental mechanisms. This allows for a joint white-box analysis that drastically improves the overall privacy guarantee compared to simple $\epsilon$-$\delta$ composition. The system leverages Renyi Differential Privacy (RDP) for superior composition guarantees, which is more efficient and supports a wider range of mechanisms.

1. Fine-Grained Privacy Analysis through Data Access Patterns: The system significantly enhances privacy analysis by exploiting how applications access data. It moves beyond traditional parallel composition by implementing block composition, which tracks costs for various subsets of users. Cohere innovates here by defining blocks not as specific user subsets but as hypothetical views of users differentiated by partitioning attributes (e.g., country, year of birth). This allows for a much finer-grained analysis without revealing sensitive user attributes, leading to more accurate results or support for more applications under the same privacy budget. Furthermore, amplification via subsampling is integrated, reducing privacy costs when only a percentage of the population is needed.

1. Ensuring System Continuity with User Rotation: A critical challenge with finite privacy budgets is their eventual depletion. Cohere addresses this by introducing a carefully implemented user rotation mechanism. Instead of undermining DP guarantees by periodically refreshing budgets for existing users, Cohere exploits the steady influx of new users in large systems. By retiring users whose privacy consumption reaches a threshold and replacing them with new users, the system replenishes the overall available budget, ensuring continuous operation while maintaining strong individual privacy guarantees. The talk acknowledges the complexities of implementing this without introducing bias or unclear semantics.

1. Sophisticated Resource Allocation for Privacy Budgets: Recognizing that the privacy budget is a scarce resource, Cohere formulates the allocation problem as a variant of the multi-dimensional knapsack problem. This allows for optimizing resource use under complex preferences, moving beyond simply maximizing the number of accepted requests to considering a more generic utility metric that factors in the relative priority and importance of an application's results at a given accuracy. To manage the high dimensionality introduced by fine-grained analysis with partitioning attributes, Cohere introduces a segmentation strategy, collapsing sets of identically treated blocks into single dimensions, making the optimization problem tractable.

These findings collectively enable Cohere to provide a robust, scalable, and efficient solution for managing differential privacy across large-scale, multi-tenant data systems, significantly improving utility while maintaining rigorous privacy guarantees.

Technical Deep Dive

▶ Watch: Introducing Cohere for system-wide DP guarantees and shared budget (3:25)

Cohere's technical architecture is meticulously designed to address the inherent complexities of system-wide differential privacy, focusing on unifying disparate DP frameworks, performing fine-grained privacy analysis, ensuring system continuity, and optimizing resource allocation.

Unifying the Application Layer with Renyi Differential Privacy (RDP)

The fundamental challenge in a multi-application DP environment is the fragmentation of existing DP libraries, each offering isolated guarantees. Cohere tackles this by intercepting the noise plans generated by these diverse frameworks. Instead of treating each application as a black box and relying on suboptimal $\epsilon$-$\delta$ composition, Cohere converts these plans into a unified representation based on a core set of fundamental DP mechanisms. This white-box view allows for a joint analysis of all applications as a global composition of these basic mechanisms.

For this joint analysis, Cohere utilizes Renyi Differential Privacy (RDP). RDP is a more powerful and efficient composition technique compared to standard $\epsilon$-$\delta$ composition. While it tracks slightly more information, it offers significantly better composition guarantees, meaning less noise needs to be added for the same privacy level, or a stronger privacy guarantee can be achieved with the same noise. RDP is particularly attractive from a systems perspective due to its broad support for various mechanisms and its relatively simple composition rule, making it ideal for Cohere's unified application layer.

Fine-Grained Privacy Analysis through Data Access Patterns

Cohere significantly improves privacy analysis by leveraging application-specific data access patterns.

Traditional DP composition often relies on parallel composition, where if applications access disjoint sets of users, the total privacy cost is simply the maximum cost of any single application. However, in practice, applications frequently access overlapping subsets of users.

To account for this, Cohere employs block composition, a more generalized accounting technique that tracks privacy costs for various subsets of users in "blocks." The innovation lies in how Cohere instantiates these blocks. Unlike existing work that equates blocks with specific user subsets, Cohere defines blocks based on hypothetical views of users differentiated by partitioning attributes. For instance, attributes like "country" or "year of birth" can define these blocks. This allows the system to track privacy costs separately for users belonging to different attribute-defined groups (e.g., French users vs. US users). Crucially, the system does not need to know or reveal which specific user belongs to which country; it only requires the schema of partitioning attributes to be known in advance. This fine-grained analysis massively benefits from application access patterns, enabling more applications to run or yielding more accurate results under the same privacy guarantees.

Further enhancing the fine-grained analysis, Cohere incorporates amplification via subsampling. In many analytical tasks, useful insights can be gleaned from a percentage of the user population rather than the entire dataset. By applying subsampling, the privacy cost of each application can be reduced, thereby improving the joint privacy analysis even further.

At the management layer, Cohere maintains a concurrent privacy filter using RDP for each block to enforce the system-wide privacy budget. Applications express their privacy requirements as noise plans and their data requirements as filter conditions on partitioning attributes and subsampling percentages.

Ensuring System Continuity with User Rotation

A critical challenge for any system managing a finite privacy budget is its eventual depletion. Cohere addresses this without undermining DP guarantees (which would occur if budgets were simply refreshed). The core insight is that large systems typically experience a steady influx of new users. Cohere implements a user rotation mechanism where users are "retired" once their past privacy consumption reaches a predefined threshold, and new users replenish the overall available budget.

The paper details how this user rotation must be carefully implemented to avoid biasing the population of active users or introducing unclear semantics. The active groups of users can be seen as another dimension in Cohere's blocking scheme, further refining the privacy analysis by allowing the system to track privacy costs for different "cohorts" of users (e.g., newly active vs. older active users).

Resource Allocation as a Multi-Dimensional Knapsack Problem

Even with sophisticated privacy analysis, the demand for data releases will likely exceed the available privacy budget. Cohere treats the acceptable privacy leakage as a budget that must be carefully allocated across competing applications. The system aims to optimize for a generic utility metric, which encodes the value of an application's result at a given accuracy to the organization, thus factoring in the relative priority of applications.

Because of the fine-grained 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 problem, where each block (defined by partitioning attributes and potentially user cohorts) corresponds to a dimension. A naive approach would result in a massively high-dimensional problem, as the number of blocks depends on the domain size of the partitioning attributes.

To manage this complexity, Cohere introduces a segmentation strategy. It collapses the allocation problem into "segments," where a segment is a set of blocks that will be treated identically by any allocation and captures the content of requests competing for those blocks. For example, if multiple requests compete for the same set of 21 blocks, those blocks can be collapsed into a single dimension within the knapsack problem. By analyzing past allocations, budget constraints for each segment can be established, significantly reducing the dimensionality and making the optimization problem far more manageable.

Demo / Proof of Concept

▶ Watch: Cohere's solution: Unified white-box analysis across frameworks (4:15)

While the talk did not present a live demonstration of Cohere, the speakers detailed an extensive evaluation and simulation of the system's performance. The researchers experimented with various workloads, simulating a scenario with weekly allocations over 40 weeks. Cohere was benchmarked against Private Cube, a related work that extends the Kubernetes orchestration system for privacy resources. Private Cube, while also formulating its allocation problem as a multi-dimensional knapsack problem, does not support Cohere's fine-grained privacy analysis.

The evaluation instantiated both Cohere and Private Cube with three optimization approaches: a greedy first-come, first-serve baseline and two heuristic-based approaches. In a workload comprising a mixture of machine learning and analytics tasks, Cohere demonstrated significant improvements. When optimizing solely for the number of accepted requests, Cohere achieved a 1.5x improvement over the baselines. However, recognizing that not all requests are equally valuable, the evaluation also optimized for a more realistic utility metric that considers the relative importance of applications. In this scenario, Cohere showed an impressive 9x increase in utility for the mixed workload. These results powerfully highlight the importance and effectiveness of Cohere's fine-grained privacy analysis and sophisticated resource allocation strategies in practical deployments.

Defensive Implications

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

The Cohere system offers critical insights and actionable strategies for organizations grappling with the deployment of Differential Privacy in large-scale, multi-tenant environments. Defenders and data privacy officers should consider the following implications:

1. Adopt a System-Wide Privacy Budget Mindset: The talk underscores the inadequacy of per-application DP guarantees. Organizations must shift towards managing a system-wide privacy budget as a shared, finite resource. This necessitates a centralized approach to privacy accounting, as advocated by Cohere, to prevent cumulative privacy leakage and ensure rigorous compliance.

1. Implement Unified Privacy Accounting: The fragmentation of DP libraries and the resulting "black-box" approach to composition are detrimental. Defenders should push for a unified privacy accounting scheme that can interpret and combine noise plans from diverse DP frameworks. Leveraging techniques like Renyi Differential Privacy (RDP) for composition can significantly improve the efficiency of privacy budgets, allowing for more data utility or stronger privacy guarantees.

1. Leverage Data Access Patterns for Finer-Grained Analysis: Cohere demonstrates the power of exploiting application-specific data access patterns. Organizations should investigate how their applications access data and identify potential partitioning attributes (e.g., demographics, usage patterns) that can define hypothetical user groups. Implementing block composition based on these attributes can enable a much more accurate and efficient privacy analysis, allowing more valuable insights to be extracted from the same privacy budget without revealing sensitive user data. Similarly, considering amplification via subsampling where applicable can further reduce privacy costs.

1. Plan for Privacy Budget Continuity: The finite nature of privacy budgets is a practical reality. Defenders need to establish mechanisms for system continuity that do not compromise DP guarantees. Cohere's user rotation mechanism, which cycles out users whose budgets are depleted and introduces new users, provides a robust model for replenishing the overall budget. Implementing such a strategy requires careful design to avoid bias and maintain clear semantics.

1. Prioritize Privacy Budget Allocation Based on Utility: Simply accepting requests on a first-come, first-serve basis or maximizing the number of accepted requests is often suboptimal. Organizations should develop a generic utility metric that reflects the business value and priority of different data releases. By framing privacy budget allocation as a multi-dimensional knapsack problem (and employing Cohere's segmentation strategy to manage complexity), defenders can optimize resource distribution to achieve maximum organizational utility while adhering to privacy constraints.

1. Invest in Centralized DP Orchestration Tools: The challenges highlighted by Cohere point to the need for advanced tooling that can orchestrate DP across an entire data ecosystem. This includes capabilities for noise plan interception, unified privacy state management, dynamic budget allocation, and user rotation. Organizations should evaluate existing and emerging solutions that offer these system-wide capabilities to ensure consistent and robust DP deployment.

By adopting these principles and considering Cohere's architectural innovations, defenders can move beyond isolated DP deployments to build truly privacy-preserving, large-scale data systems that effectively balance data utility with stringent privacy guarantees.

Key Takeaways

• Cumulative Privacy Loss is a Critical Problem: Existing Differential Privacy (DP) frameworks provide only per-application guarantees, underestimating the total privacy cost when multiple applications interact with the same user data. A system-wide approach is essential.
• Cohere Unifies DP Analysis: The system addresses tooling fragmentation by intercepting noise plans from diverse DP libraries, presenting them in a unified manner, and performing a joint white-box analysis using Renyi Differential Privacy (RDP) for significantly better composition guarantees.
• Fine-Grained Analysis Improves Utility: Cohere leverages data access patterns, implementing block composition with partitioning attributes (hypothetical user views) and amplification via subsampling to conduct a much more precise privacy analysis, allowing for more applications or higher accuracy under the same privacy budget.
• System Continuity Through User Rotation: To prevent privacy budget depletion, Cohere introduces a carefully implemented user rotation mechanism, retiring users with depleted budgets and replacing them with new users, thus ensuring continuous system operation without compromising DP guarantees.
• Optimized Resource Allocation: Privacy budget allocation is treated as a multi-dimensional knapsack problem, optimized for a generic utility metric that considers application priority and accuracy. A segmentation strategy is used to manage the high dimensionality of fine-grained analysis.
• Significant Performance Gains: Evaluations against related work (Private Cube) show Cohere achieving a 1.5x improvement in accepted requests and an impressive 9x increase in utility when optimizing for realistic preferences, demonstrating the value of its fine-grained analysis and allocation strategies.

About the Speaker(s)

The talk "Cohere: Managing Differential Privacy in Large Scale Systems" was primarily presented by Nicolas Küchler. He is one of the listed speakers, alongside Emanuel Opel, Hidde Lycklama, Alexander Viand, and Anwar Hithnawi, who are co-authors of the work. While the transcript does not provide specific titles or affiliations for all speakers, Nicolas Küchler led the presentation, detailing the challenges and Cohere's innovative solutions for deploying differential privacy at scale.