3. Types of Composition Techniques
Differential privacy is a framework for ensuring privacy in data analysis and statistical computations. It aims to provide a mathematical guarantee that the presence or absence of any individual data point does not significantly impact the outcome of a query or analysis. Composition techniques in differential privacy are methods used to combine multiple privacy-preserving computations while maintaining the overall privacy guarantee
Below are some common composition techniques:
1. Sequential Composition: Sequential composition deals with the privacy loss that accumulates when multiple queries are executed one after another. If each query satisfies a certain privacy parameter (like ε-differential privacy), then the overall privacy guarantee is scaled by the total privacy loss incurred across all the queries.
2. Parallel Composition: Parallel composition addresses the scenario where multiple queries are executed simultaneously or in parallel. If each query adheres to a certain privacy parameter, then the overall privacy guarantee is determined by the most stringent privacy parameter among the queries.
3. Advanced Composition Theorems: These theorems provide tighter bounds on privacy loss when multiple queries are performed. Some well-known advanced composition theorems include the ”Moments Accountant” and ”Rényi Differential Privacy” (RDP) composition, which can give more accurate privacy guarantees compared to basic sequential or parallel composition.
4. Post-processing and Composition: This technique considers the situation where the output of one differentially private algorithm is further processed before being used in subsequent computations. Post-processing can sometimes introduce additional privacy loss, and the composition of privacy guarantees must be carefully analyzed.
5. Renewal-Based Composition: This technique is useful when queries are repeated over time. It involves periodically ”renewing” the privacy guarantee to mitigate the accumulation of privacy loss over a long sequence of queries.
6. Hierarchical Composition: In cases where multiple data analysts or levels of access are involved, hierarchical composition ensures that the privacy guarantees are appropriately combined while considering the interactions between different levels.
7. Limited Queries Composition: This technique restricts the number of queries an adversary can make, thereby controlling the potential privacy loss due to repeated queries.
8. Adaptive Data Analysis: This technique accounts for the fact that an adversary’s queries might depend on the responses of previous queries. It involves designing mechanisms that dynamically adjust privacy parameters based on the adaptive behavior of the adversary.
9. Composition with Differential Privacy Mechanisms: When applying differentially private mechanisms (such as Laplace noise addition or exponential mechanism) to different queries, composition techniques ensure that the cumulative effect of applying multiple mechanisms is properly bounded.
Table 1.Key aspects of Popular Composition methods 6 ,7