Differential Privacy Mechanisms for DAP

3.1. Differential Privacy

DP formalizes a property of any randomized algorithm that takes in a sequence of measurements, aggregates them, and outputs an aggregate result. Intuitively, this property guarantees that no single measurement significantly impacts the value of the aggregate result. This intuition is formalized by [DMNS06] as follows.¶

• CP: The following is might be too jargony for an informative RFC, but for now I think we're all just trying to agree on the definition. Once we have consensus among ourselves, we can punt this to the appendix and leave a less formal description here.¶

DP requires specifying the notion of "neighboring" datasets, that determines what information is being hidden. The most common notion for our setting would be the following:¶

We say that two batches of measurements D1 and D2 are "neighboring" if they are the same length and contain all the same measurements except one (i.e., the symmetric difference between the multisets contains two elements). We denote this definition as "replacement-DP" (or "substitution-DP"). Appendix B.2 discusses other notions of adjacency that may be appropriate in some settings.¶

Let p(S, D, r) denote the probability that randomized algorithm S, on input of measurements D, outputs aggregate result r.¶

A randomized algorithm S is called "EPSILON-DP" if for all neighboring D1 and D2 and all possible aggregate results r, the following inequality holds:¶

p(S, D1, r) <= exp(EPSILON) * p(S, D2, r)

In other words, the probability that neighboring inputs produce a given aggregate result differs by at most a constant factor, exp(EPSILON).¶

One can think of EPSILON as a measure of how much information about the measurements is leaked by the aggregate result: the smaller the EPSILON, the less information is leaked by S. For most DP applications, EPSILON will be a small constant, e.g. 0.1 or 0.5. See Appendix B for details.¶

This notion of EPSILON-DP is sometimes referred to as "pure-DP". The following is a relaxation of pure-DP, called "approximate-DP", from [DR14]. A randomized algorithm S is called "(EPSILON, DELTA)-DP" if for all neighboring D1 and D2 and all possible aggregate results r, the following inequality holds:¶

p(S, D1, r) <= exp(EPSILON) * p(S, D2, r) + DELTA

Compared to pure-DP, approximate-DP loses an additive factor of DELTA in the bound. DELTA can intuitively be understood as the probability that a piece of information is leaked (e.g. a Client measurement is leaked), so DELTA is typically taken to be polynomially small in the batch size or smaller, i.e., some value much smaller than 1 / batch_size. Allowing for a small DELTA can in many cases allow for much smaller noise compared to pure-DP mechanisms. See Section 4 for details.¶

Other variants of DP are possible; see the literature review in Appendix B for details.¶

3.2. Sensitivity

Differential privacy noise sometimes needs to be calibrated based on the SENSITIVITY of the aggregation function used to compute the aggregate result over Client measurements. Sensitivity characterizes how much a change in a Client measurement can affect the aggregate result. In this document, we focus on the L1 and L2 sensitivity. We define them as the maximum of some distance between two aggregate results computed from any neighboring datasets:¶

• L1 Sensitivity: the distance is defined as the sum of the absolute values of differences at all coordinates of the neighboring aggregate results.¶

• L2 Sensitivity: the distance is defined as the square root of the sum of squares of the differences at all coordinates of the neighboring aggregate results.¶

3.3. Trust Models

When considering whether a given DP policy is sufficient for DAP, it is not enough to consider the mechanisms used in isolation. It is also necessary to consider the process by which the policy is executed. In particular, our threat model for DAP considers an attacker that participates in the upload, aggregation, and collection protocols and may use its resources to attack the underlying cryptographic primitives (VDAF [VDAF], HPKE [RFC9180], and TLS [RFC8446]).¶

To account for such attackers, our goal for DAP is "computational-DP" as described by [MPRV09] (Definition 4, "SIM-CDP"). This formalizes the amount of information a computationally bounded attacker can glean about the measurements generated by honest Clients over the course of its attack on the protocol. We consider an attacker that controls the network and statically corrupts a subset of the parties.¶

We say the protocol is pure-DP (resp. approximate-DP) if the view of any computationally bounded attacker can be efficiently simulated by a simulator that itself is pure-DP (or approximate-DP) as defined above. (The simulator takes the measurements as input and outputs a value that should be computationally indistinguishable from the transcript of the protocol's execution in the presence of the attacker.)¶

Whether this property holds for a given DP policy depends on which parties can be trusted to execute the protocol correctly (i.e., which parties are not corrupted by the attacker). We consider three, increasingly pessimistic trust models.¶

• KT(issue#28): Here we seem to be assuming corrupted = malicious. Is there any benefit to a more refined distinction (i.e. honest-but-curious vs malicious). I suspect we would always want secure against malicious, but perhaps there are settings where we are OK with security against bad behavior that is not catchable during an audit.¶

3.4. OC: One-Client

Assume that all parties, including all but one Client, both Aggregators, and the Collector are controlled by the attacker. The best the honest Client can hope for is that its measurement has "local-DP". This property is defined the same way as pure- or approximate-DP, but the bound on EPSILON that we would aim to achieve for local-DP would typically be larger than that in a more optimistic trust model.¶

3.5. Hedging

If a trust model's assumptions turn out to be false in practice, then it is desirable for a DP policy to maintain some degree of privacy in a more pessimistic trust model. For example, a deployment of DAP might provide some mechanism to ensure that all reports that are consumed were generated by trusted Clients (e.g., a Trusted Execution Environment (TEE) at each Client). This gives us confidence that our assumptions in the OAMC trust model hold. But if this mechanism is broken (e.g., a flaw is found in the TEE), then it is desirable if the policy remains DP in the OAOC or OC model, perhaps with a weaker bound.¶

4.1. Discrete Laplace

• TODO: Specify a Laplace sampler from Algorithm 2 of [CKS20] (#10).¶

4.2. Discrete Gaussian

• TODO: Specify a Gaussian sampler from Algorithm 3 of [CKS20] (#10).¶

4.3. Symmetric RAPPOR

This section describes Symmetric RAPPOR, a DP mechanism first proposed in [EPK14], and refined in Appendix C.1 of [MJTB_22]. (The specification here reflects the refined version.) It is initialized with a parameter EPSILON_0. It takes in a bit vector and outputs a noisy version with randomly flipped bits.¶

Symmetric RAPPOR applies "binary randomized response mechanism" at each coordinate. Binary randomized response takes in a single bit x. The bit is flipped to 1 - x with probability 1 / (exp(EPSILON_0) + 1). For example, if EPSILON_0 is configured to be 3, and the input to binary randomized response is a 0, the bit will be flipped to be 1 with probability 1 / (exp(3) + 1), otherwise, it will stay as a 0.¶

Under OC trust model, by applying binary randomized response with EPSILON_0 parameter to its measurement, the Client gets EPSILON_0-DP with deletion (Definition II.4 of [EFMR_20], and Definition C.1 of [MJTB_22]). A formal definition of deletion-DP is elaborated in Section 4.3.1.¶

Symmetric RAPPOR generalizes binary randomized response mechanism by applying it independently at all coordinates of a Client's bit vector. Under OAMC trust model, it is proven in Appendix C.1.3 of [MJTB_22] that strong (EPSILON, DELTA)-DP can be achieved by aggregating a batch of noisy Client measurements, each of which is a bit vector with exactly one bit set, and is noised with symmetric RAPPOR. The final aggregate result needs to be "debiased" due to the noise added by the Clients. Although the raw aggregate result is a vector of integers, the debiased aggregate result is a vector of floats, because the best estimate of the true sum depends on exp(EPSILON_0), and generally won't be an integer.¶

Since the noise generated by each Client at each coordinate is independent, and as the number of Clients n grows, the noise distribution at each coordinate approximates a Gaussian distribution, with mean 0, and standard deviation sqrt(n * exp(EPSILON_0) / (exp(EPSILON_0) - 1)^2), as proved by Theorem C.2 of [MJTB_22].¶

-EPSILON_0 <= ln(P1(S, D, E) / P2(R, E)) <= EPSILON_0

import random

class SymmetricRappor(DpMechanism):
    DataType = list[int]
    # Debiasing produces an array of floats.
    DebiasedDataType = list[float]

    def __init__(self, eps0: float):
        self.eps0 = eps0
        self.p = 1.0 / (math.exp(eps0) + 1.0)

    def add_noise(self, data: DataType) -> DataType:
        # Apply binary randomized response at each coordinate, based
        # on Appendix C.1.1 of {{MJTB+22}}.
        return list(map(
            lambda x: 1 - x if self.coin_flip() else x,
            data
        ))

    def sample_noise(self, dimension: int) -> DataType:
        # Sample binary randomized response at each coordinate on an
        # all zero vector.
        return [int(self.coin_flip()) for coord in range(dimension)]

    def debias(self,
               data: DataType,
               meas_count: int) -> DebiasedDataType:
        # Debias the data based on Appendix C.1.2 of {{MJTB+22}}.
        exp_eps = math.exp(self.eps0)
        return list(map(
            lambda x: (x * (exp_eps + 1) / (exp_eps - 1) -
                       meas_count / (exp_eps - 1)),
            data
        ))

    def coin_flip(self):
        return random.random() < self.p

5.1. Executing DP Policies with VDAFs

The execution of DpPolicy with a Vdaf can thus be summarized by the following computational steps (these are carried out by DAP in a distributed manner):¶

def run_vdaf_with_dp_policy(
    dp_policy: DpPolicy,
    Vdaf: Vdaf,
    agg_param: Vdaf.AggParam,
    measurements: list[DpPolicy.Measurement],
):
    """Run the DP policy with VDAF on a list of measurements."""
    nonces = [gen_rand(Vdaf.NONCE_SIZE)
              for _ in range(len(measurements))]
    verify_key = gen_rand(Vdaf.VERIFY_KEY_SIZE)

    out_shares = []
    for (nonce, measurement) in zip(nonces, measurements):
        assert len(nonce) == Vdaf.NONCE_SIZE

        # Each Client adds Client randomization noise to its
        # measurement.
        noisy_measurement = \
            dp_policy.add_noise_to_measurement(measurement)
        # Each Client shards its measurement into input shares.
        rand = gen_rand(Vdaf.RAND_SIZE)
        (public_share, input_shares) = \
            Vdaf.shard(noisy_measurement, nonce, rand)

        # Each Aggregator initializes its preparation state.
        prep_states = []
        outbound = []
        for j in range(Vdaf.SHARES):
            (state, share) = Vdaf.prep_init(verify_key, j,
                                            agg_param,
                                            nonce,
                                            public_share,
                                            input_shares[j])
            prep_states.append(state)
            outbound.append(share)

        # Aggregators recover their output shares.
        for i in range(Vdaf.ROUNDS-1):
            prep_msg = Vdaf.prep_shares_to_prep(agg_param,
                                                outbound)

            outbound = []
            for j in range(Vdaf.SHARES):
                out = Vdaf.prep_next(prep_states[j], prep_msg)
                (prep_states[j], out) = out
                outbound.append(out)

        # The final outputs of the prepare phase are the output shares.
        prep_msg = Vdaf.prep_shares_to_prep(agg_param,
                                            outbound)
        outbound = []
        for j in range(Vdaf.SHARES):
            out_share = Vdaf.prep_next(prep_states[j], prep_msg)
            outbound.append(out_share)

        out_shares.append(outbound)

    num_measurements = len(measurements)
    # Each Aggregator aggregates its output shares into an
    # aggregate share, and adds any Aggregator randomization
    # mechanism to its aggregate share. In a distributed VDAF
    # computation, the aggregate shares are sent over the network.
    agg_shares = []
    for j in range(Vdaf.SHARES):
        out_shares_j = [out[j] for out in out_shares]
        agg_share_j = Vdaf.aggregate(agg_param, out_shares_j)
        # Each Aggregator independently adds noise to its aggregate
        # share.
        noised_agg_share_j = \
            dp_policy.add_noise_to_agg_share(agg_share_j)
        agg_shares.append(noised_agg_share_j)

    # Collector unshards the aggregate.
    agg_result = Vdaf.unshard(agg_param, agg_shares,
                              num_measurements)
    # Debias aggregate result.
    debiased_agg_result = dp_policy.debias_agg_result(
        agg_result, num_measurements
    )
    return debiased_agg_result

5.2. Executing DP Policies in DAP

• TODO: Specify integration of a DpPolicy into DAP.¶

6.1. Histograms

Many applications require aggregating histograms in which each Client submits a bit vector with exactly one bit set, also known as, "one-hot vector".¶

We describe two policies that achieve (EPSILON, DELTA)-DP for this use case. The first uses only a Client randomization mechanism and targets the OAMC trust model. The second uses only an Aggregator randomization mechanism and targets the more stringent OAOC trust model. We discover that both policies in different settings of EPSILON and DELTA provide comparable utility, except that the policy in the OAOC trust model requires all Aggregators to independently add noise, so we lose some utility when more than one Aggregator is honest.¶

class MultiHotHistogramWithClientRandomization(DpPolicy):
    Field = MultiHotHistogram.Field
    Measurement = MultiHotHistogram.Measurement
    AggShare = list[Field]
    AggResult = MultiHotHistogram.AggResult
    DebiasedAggResult = SymmetricRappor.DebiasedDataType

    def __init__(self, eps0: float):
        # TODO(junyechen1996): Justify how eps0 + batch_size can
        # achieve `(EPSILON, DELTA)`-DP.
        self.rappor = SymmetricRappor(eps0)

    def add_noise_to_measurement(self,
                                 meas: Measurement,
                                 ) -> Measurement:
        return self.rappor.add_noise(meas)

    def debias_agg_result(self,
                          agg_result: AggResult,
                          meas_count: int,
                          ) -> DebiasedAggResult:
        return self.rappor.debias(agg_result, meas_count)

class HistogramWithAggregatorRandomization(DpPolicy):
    Field = Histogram.Field
    # A measurement is an unsigned integer, indicating an index less
    # than `Histogram.length`.
    Measurement = Histogram.Measurement
    AggShare = list[Field]
    AggResult = Histogram.AggResult
    # The final aggregate result should be a vector of signed
    # integers, because discrete Gaussian could produce negative
    # noise that may have a larger absolute value than the count
    # before noise.
    DebiasedAggResult = list[int]

    def __init__(self, epsilon: float, delta: float):
        # TODO(junyechen1996): Consider using fixed precision or large
        # decimal for parameters like `epsilon` and `delta`. (#23)
        # Transforming an one-hot vector into another will affect two
        # coordinates, e.g. from [1, 0, 0] to [0, 1, 0], so the change
        # in L2-sensitivity is `sqrt(1 + 1) = sqrt(2)`.
        dgauss_sigma = agm.calibrateAnalyticGaussianMechanism(
            epsilon, delta, math.sqrt(2.0)
        )
        self.dgauss_mechanism = \
            DiscreteGaussianWithZeroMean(dgauss_sigma)

    def add_noise_to_agg_share(self,
                               agg_share: AggShare,
                               ) -> AggShare:
        """
        Sample discrete Gaussian noise, and merge it with the
        aggregate share.
        """
        noise_vec = self.dgauss_mechanism.sample_noise(len(agg_share))
        result = []
        for (agg_share_i, noise_vec_i) in zip(agg_share, noise_vec):
            if noise_vec_i < 0:
                noise_vec_i = Field.MODULUS + noise_vec_i
            result.append(agg_share_i + self.Field(noise_vec_i))
        return result

    def debias_agg_result(self,
                          agg_result: AggResult,
                          meas_count: int,
                          ) -> DebiasedAggResult:
        # TODO(junyechen1996): Interpret large unsigned integers as
        # negative values or 0 properly. For now, directly return it,
        # since we haven't fully implemented discrete Gaussian
        # mechanism (#10).
        return agg_result

B.1. Differential privacy levels

• KT: I think we should distinguish between the randomizer and the DP guarantee. So I have attempted to use Client randomizer and Aggregator randomizer to describe the noise addition by those two, and Local DP and Aggregator DP to refer to the privacy guarantee. The distinction is important because Client randomizer + aggregate gives an aggregator DP guarantee.¶

There are two levels of privacy protection: local differential privacy (local DP) and aggregator differential privacy (aggregator DP).¶

• OPEN ISSUE: or call it secure aggregator dp, or central dp.¶

In the local-DP settings, Clients apply noise to their own measurements. In this way, Clients have some control to protect the privacy of their own data. Any measurement uploaded by a Client will be have local dp, Client's privacy is protected even if none of the Aggregators is honest (although this protection may be weak). Furthermore, one can analyze the aggregator DP guarantee with privacy amplification by aggregation, assuming each Client has added the required amount of local DP noise, and there are at least minimum batch size number of Clients in the aggregation.¶

In Aggregator randomization settings, an Aggregator applies noise on the aggregation. This approach relies on the server being secure and trustworthy. Aggregators built using DAP protocol is ideal for this setting because DAP ensures no server can access any individual data, but only the aggregation.¶

If there are no local DP added from client, noise added to the aggregation provides the privacy guarantee of the aggregation.¶

• JC: For now, we have been assuming either Client randomization or Aggregator randomization gives the target DP parameters. Theoretically one can use the Aggregator randomization together with Client randomization to achieve DP. For example, if the DP guarantee can be achieved with Client randomization from a batch size number of Clients, and batch size is not reached when a data collection task expires, each Aggregator can "compensate" the remaining noise, by using the same Client randomizer, on the missing number of Clients being the gap between actual number of Clients and target batch size.¶

B.2. How to define neighboring batches

There are primarily two models in the literature for defining two "neighboring batches": deletion (or removal) of one measurement, and replacement (or substitution) of one measurement with another [KM11]. In the DAP setting, the protocol leaks the number of measurements in each batch collected and the appropriate version of deletion-DP considers substitution by a fixed value (e.g. zero). In other words, two batches of measurements D1 and D2 are "neighboring" for deletion-DP if D2 can be obtained from D1 by replacing one measurement by a fixed reference value.¶

In some cases, a weaker notion of adjacency may be appropriate. For example, we may be interested in hiding single coordinates of the measurement, rather than the whole vector of measurements. In this case, neighboring datasets differ in one coordinate of one measurement.¶

B.3. Protected entity

• TODO: Chris P to fill: user or report, given time¶

B.4. Privacy budget and accounting

There are various types of DP guarantees and budgets that can be enforced. Many applications need to query the Client data multiple times, for example:¶

• Federated machine learning applications require multiple aggregates to be computed over the same underlying data, but with different machine learning model parameters.¶

• [MJTB_22] describes an interactive approach of building histograms over multiple iterations, and Section 4.3 describes a way to track Client-side budget when the Client data is queried multiple times.¶

• TODO: have citations for machine learning¶

It’s hard for Aggregator(s) to keep track of the privacy budget over time, because different Clients can participate in different data collection tasks, and only Clients know when their data is queried. Therefore, Clients must enforce the privacy budget.¶

There could be multiple ways to compose DP guarantees, based on different DP composition theorems. In the various example DP guarantees below, we describe the following:¶

• A formal definition of the DP guarantee.¶

• Composition theorems that apply to the DP guarantee.¶

B.5. Pure EPSILON-DP, or (EPSILON, DELTA)-approximate DP

Pure EPSILON-DP was first proposed in [DMNS06], and a formal definition of (EPSILON, DELTA)-DP can be found in Definition 2.4 of [DR14].¶

The EPSILON parameter quantifies the "privacy loss" of observing the outcomes of querying two databases differing by one element. The smaller EPSILON is, the stronger the privacy guarantee is, that is, the outcomes of querying two adjacent databases are more or less the same. The DELTA parameter provides a small probability of the privacy loss exceeding EPSILON.¶

One can compose multiple (EPSILON, DELTA)-approximate DP guarantees, per Theorem 3.4 of [KOV15]. One can also compose the guarantees in other types of guarantee first, such as Rényi DP Appendix B.5.1, and then convert the composed guarantee to approximate DP guarantee.¶

B.6. Data type and Noise type

Differential Privacy guarantee can only be achieved if data type is applied with the correct noise type.¶

• TODO: Junye to fill, mention DAP is expected to ensure the right pair of VDAF and DP mechanism¶

• TODO: Chris P: we will mention Prio3SumVec because that's what we use to describe aggregator DP with amplification¶