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