Skip to main content

Differential Privacy Mechanisms for DAP
draft-wang-ppm-differential-privacy-00

Document Type Active Internet-Draft (individual)
Authors Junye Chen , Audra McMillan , Christopher Patton , Kunal Talwar , Shan Wang
Last updated 2023-10-23
RFC stream (None)
Intended RFC status (None)
Formats
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-wang-ppm-differential-privacy-00
Privacy Preserving Measurement                                   J. Chen
Internet-Draft                                               A. McMillan
Intended status: Informational                                Apple Inc.
Expires: 25 April 2024                                         C. Patton
                                                              Cloudflare
                                                               K. Talwar
                                                                 S. Wang
                                                              Apple Inc.
                                                         23 October 2023

                Differential Privacy Mechanisms for DAP
                 draft-wang-ppm-differential-privacy-00

Abstract

   Differential Privacy (DP) is a property of a secure aggregation
   mechanism that ensures that no single input measurement significantly
   impacts the distribution of the aggregate result.  This is a stronger
   property than what systems like the Distributed Aggregation Protocol
   (DAP) are designed to achieve.  This document describes a variety of
   DP mechansisms applicable to DAP, and, for a variety of common use
   cases, lifts DAP to a protocol that also achieves DP.

About This Document

   This note is to be removed before publishing as an RFC.

   The latest revision of this draft can be found at
   https://wangshan.github.io/draft-wang-ppm-differential-privacy/draft-
   wang-ppm-differential-privacy.html.  Status information for this
   document may be found at https://datatracker.ietf.org/doc/draft-wang-
   ppm-differential-privacy/.

   Discussion of this document takes place on the Privacy Preserving
   Measurement Working Group mailing list (mailto:ppm@ietf.org), which
   is archived at https://mailarchive.ietf.org/arch/browse/ppm/.
   Subscribe at https://www.ietf.org/mailman/listinfo/ppm/.

   Source for this draft and an issue tracker can be found at
   https://github.com/wangshan/draft-wang-ppm-differential-privacy.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

Chen, et al.              Expires 25 April 2024                 [Page 1]
Internet-Draft                   DP-PPM                     October 2023

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 25 April 2024.

Copyright Notice

   Copyright (c) 2023 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Conventions and Definitions . . . . . . . . . . . . . . . . .   5
   3.  Security Goals and Trust Model  . . . . . . . . . . . . . . .   6
     3.1.  Differential Privacy  . . . . . . . . . . . . . . . . . .   6
     3.2.  Sensitivity . . . . . . . . . . . . . . . . . . . . . . .   7
     3.3.  Trust Models  . . . . . . . . . . . . . . . . . . . . . .   7
       3.3.1.  OAMC: One-Aggregator-Most-Clients . . . . . . . . . .   8
       3.3.2.  OAOC: One-Aggregator-One-Client . . . . . . . . . . .   8
     3.4.  OC: One-Client  . . . . . . . . . . . . . . . . . . . . .   9
     3.5.  Hedging . . . . . . . . . . . . . . . . . . . . . . . . .   9
   4.  DP Mechanisms . . . . . . . . . . . . . . . . . . . . . . . .   9
     4.1.  Discrete Laplace  . . . . . . . . . . . . . . . . . . . .  11
     4.2.  Discrete Gaussian . . . . . . . . . . . . . . . . . . . .  11
     4.3.  Symmetric RAPPOR  . . . . . . . . . . . . . . . . . . . .  11
       4.3.1.  EPSILON_0-DP in Deletion-DP . . . . . . . . . . . . .  12
       4.3.2.  Reference Implementation  . . . . . . . . . . . . . .  13
   5.  DP Policies for VDAFs . . . . . . . . . . . . . . . . . . . .  14
     5.1.  Executing DP Policies with VDAFs  . . . . . . . . . . . .  16
     5.2.  Executing DP Policies in DAP  . . . . . . . . . . . . . .  17
   6.  Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . .  17

Chen, et al.              Expires 25 April 2024                 [Page 2]
Internet-Draft                   DP-PPM                     October 2023

     6.1.  Histograms  . . . . . . . . . . . . . . . . . . . . . . .  18
       6.1.1.  Prio3MultiHotHistogram with Client Randomization  . .  18
       6.1.2.  Prio3Histogram with Aggregator Randomization  . . . .  21
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  23
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  23
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  23
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  23
     9.2.  Informative References  . . . . . . . . . . . . . . . . .  24
   Appendix A.  Contributors . . . . . . . . . . . . . . . . . . . .  26
   Appendix B.  Overview of Differential Privacy . . . . . . . . . .  26
     B.1.  Differential privacy levels . . . . . . . . . . . . . . .  26
     B.2.  How to define neighboring batches . . . . . . . . . . . .  27
     B.3.  Protected entity  . . . . . . . . . . . . . . . . . . . .  28
     B.4.  Privacy budget and accounting . . . . . . . . . . . . . .  28
     B.5.  Pure EPSILON-DP, or (EPSILON, DELTA)-approximate DP . . .  28
       B.5.1.  (ALPHA, TAU)-Rényi DP . . . . . . . . . . . . . . . .  29
       B.5.2.  Zero Concentrated-DP  . . . . . . . . . . . . . . . .  29
     B.6.  Data type and Noise type  . . . . . . . . . . . . . . . .  29
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  29

1.  Introduction

   [TO BE REMOVED BY RFC EDITOR: The source for this draft and and the
   reference implementations of mechanisms and policies can be found at
   https://github.com/wangshan/draft-wang-ppm-differential-privacy.]

   Multi-party computation systems like the Distributed Aggregation
   Protocol [DAP] enable secure aggregation of measurements generated by
   individuals without handling the measurements in the clear.  This is
   made possible by using a Verifiable Distributed Aggregation Function
   [VDAF], the core cryptographic component of DAP.  Execution of A VDAF
   involves: a large set of "Clients" who produce cryptographically
   protected measurements, called "reports"; a small number of
   "Aggregators" who consume reports and produce the cryptographically
   protected aggregate; and a "Collector" who consumes the plaintext
   aggregate result.  Distributing the computation of the aggregate in
   this manner ensures that, as long as one Aggregator is honest, no
   attacker can learn an honest Client's measurement.

Chen, et al.              Expires 25 April 2024                 [Page 3]
Internet-Draft                   DP-PPM                     October 2023

   Depending on the application, protecting the measurements may not be
   sufficient for privacy, since the aggregate itself can reveal
   privacy-sensitive information.  As an illustrative example, consider
   using DAP/VDAF to summarize the distribution of the heights of
   respondents to a survey.  If one of the respondents is especially
   short or tall, then their contribution is likely to skew the summary
   statistic in a way that reveals their height.  Ideally, no individual
   measurement would have such a significant impact on the aggregate
   result, but in general such leakage is inevitable for exact
   aggregates.  Adding some carefully chosen noise to the aggregates can
   however help hide the contribution of one respondent.

   This intuition can be formalized by the notion of differential
   privacy [DMNS06].  Differentially privacy is a property of an
   algorithm or protocol that computes some function of a set of
   measurements.  We say the algorithm or protocol is "differentially
   private", or "DP", if the probability of observing a particular
   output does not change significantly as a result of removing one of
   the measurements (or substituting it with another).

   VDAFs are not DP on their own, but they can be composed with a
   variety of mechanisms that endow them with this property.  All such
   mechanisms work by introducing noise into the computation that is
   carefully calibrated for a number of application-specific parameters,
   including the structure and number of measurements, the desired
   aggregation function, and the degree of "utility" required.
   Intuitively, a high degree of privacy can be achieved by adding a lot
   of noise; but adding too much noise can reduce the usefulness of the
   aggregate result.

   Noise can be introduced at various steps at the computation, and by
   various parties.  Depending on the mechanism: the Clients might add
   noise to their own measurements; and the Aggregators might add noise
   to their aggregate shares (the values they produce for the
   Collector).

   In this document, we shall refer to the composition of DP mechanisms
   into a scheme that provides (some notion of) DP as a "DP policy".
   For some policies, noise is added only by the Clients or only by the
   Aggregators, but for others, both Clients and Aggregators may
   participate in generating the noise.

   The primary goal of this document is to specify how DP policies are
   implemented in DAP.  It does so in the following stages:

   1.  Section 3 describes the notion(s) of DP that are compatible with
       DAP.  Security is defined in a few different "trust models" in
       which we assume that some fraction of the parties execute the

Chen, et al.              Expires 25 April 2024                 [Page 4]
Internet-Draft                   DP-PPM                     October 2023

       protocol honestly.  Of course in reality, whether such
       assumptions hold is usually outside of our control.  Thus our
       goal is to design DP policies that still provide some degree of
       protection in more pessimistic trust models.  (We call this
       "hedging".)

   2.  Section 4 specifies various mechanisms required for building DP
       systems, including algorithms for sampling from discrete Laplace
       and Gaussian distributions.

   3.  Section 5 defines DP policies that are implemented with DP
       mechanisms, their composition with VDAFs, and their execution
       semantics for DAP.  Section 5.1 then demonstrates how to execute
       VDAFs with DP policies.

   4.  Section 6 specifies compositions of concrete VDAFs with concrete
       DP policies for achieving DP for specific DAP use cases.

   The following considerations are out-of-scope for this document:

   1.  DP policies have a few parameters that need to be tuned in order
       to meet the privacy/utility tradeoff required by the application.
       This document provides no guidance for this process.

   2.  This document describes a particular class of narrowly-scoped DP
       policies.  Other, more sophisticated policies are possible.
       [TODO: Add citations.  Here we're thinking of things like DPrio,
       which may be more appropriate to specify as DAP report
       extensions.]

   3.  The mechanisms described in Section 4 are intended for use beyond
       DAP/VDAF.  However, this document does not describe general-
       purpose DP policies; those described in Section 5 are tailored to
       specific VDAFs or classes of VDAFs.

2.  Conventions and Definitions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in
   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

   This document uses Python3 for describing algorithms.

   Let exp(EPSILON) denote raising the numeric constant e to the power
   of EPSILON.

Chen, et al.              Expires 25 April 2024                 [Page 5]
Internet-Draft                   DP-PPM                     October 2023

3.  Security Goals and Trust Model

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.

Chen, et al.              Expires 25 April 2024                 [Page 6]
Internet-Draft                   DP-PPM                     October 2023

   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 a function over two neighboring Client measurements:

   *  L1 Sensitivity: the sum of the absolute values of differences at
      all coordinates of the neighboring Client measurements.

   *  L2 Sensitivity: the sum of the squares of the differences at all
      coordinates of the neighboring Client measurements.

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]).

Chen, et al.              Expires 25 April 2024                 [Page 7]
Internet-Draft                   DP-PPM                     October 2023

   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.3.1.  OAMC: One-Aggregator-Most-Clients

   Assume that most Clients and one Aggregator are honest and that the
   other Aggregator (DAP involves just two Aggregators) and the
   Collector are controlled by the attacker.  When all Clients are
   honest, this corresponds to the same trust model as the base DAP
   protocol.  The degree of privacy provided (i.e., the value of EPSILON
   for pure-DP) for most protocols in this setting would degrade
   gracefully as the number of honest Clients decreases.

3.3.2.  OAOC: One-Aggregator-One-Client

   Assume that at least one Aggregator is honest.  The other Aggregator,
   the Collector, and all but one Clients are controlled by the
   attacker.  The goal is to provide protection for the honest Client's
   measurement.

Chen, et al.              Expires 25 April 2024                 [Page 8]
Internet-Draft                   DP-PPM                     October 2023

      TODO(issue#15) For the simple Aggregator-noise mechanism, if the
      malicious Aggregator cheats by not adding noise, then the
      aggregate result is not DP from the point of view of the honest
      Aggregator, unless the honest Aggregator "forgets" the randomness
      it used.  Describe this "attack" in "Security Considerations" and
      say why it's irrelevant.

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.  DP Mechanisms

   This section describes various mechanisms required for implementing
   DP policies.  The algorithms are designed to securely expand a short,
   uniform random seed into a sample from the target given distribution.

      TODO For now we don't actually expand a seed into a sample; we
      just use coin flips that are local to the relevant algorithm.
      Update the API so that take a random seed instead so that we can
      derive test vectors.

Chen, et al.              Expires 25 April 2024                 [Page 9]
Internet-Draft                   DP-PPM                     October 2023

   Each mechanism has internal parameters that determine how much noise
   will be added to its input data.  Note that a mechanism that is
   initialized with its internal parameters can achieve different
   combinations of DP parameters, e.g.  (EPSILON, DELTA)-DP, or
   (EPSILON', DELTA')-DP, where EPSILON < EPSILON' and DELTA > DELTA',
   because if we make EPSILON larger (i.e., weaker privacy), we may
   achieve a smaller DELTA and thereby a smaller overall DP bound (i.e.,
   stronger privacy).

   A concrete DP mechanism implements the following methods:

   *  DpMechanism.add_noise(data: DataType) -> DataType adds noise to
      the input data (i.e., a measurement or an aggregate share).  Some
      DP mechanisms apply noise based on the input data.

   *  DpMechanism.sample_noise(dimension: int) -> DataType samples noise
      of length dimension, with the DP mechanism.  The interpretation of
      dimension generally depends on the data type.  It may be called by
      DpMechanism.add_noise().

   *  DpMechanism.debias(data: DataType, meas_count: int) ->
      DebiasedDataType debiases the noised data based on the number of
      measurements meas_count.  Note that not all mechanisms will
      implement this method.  Some do, such as Section 4.3.

   Putting this together a DP mechanism is a concrete subclass of
   DPMechanism defined below:

Chen, et al.              Expires 25 April 2024                [Page 10]
Internet-Draft                   DP-PPM                     October 2023

  class DpMechanism:
      # The data type applicable to this `DpMechanism`. The type is the
      # same for the noised data and the un-noised data.
      DataType = None
      # Debiased data type after removing bias added by the noise. For
      # most of the mechanisms, `DebiasedDataType == DataType`.
      DebiasedDataType = None

      def add_noise(self, data: DataType) -> DataType:
          """Add noise to a piece of input data. """
          raise NotImplementedError()

      def sample_noise(self, dimension: int) -> DataType:
          """
          Sample noise with the initialized `DpMechanism`. `dimension`
          is used to determine the length of the output if `DataType` is
          a list.
          """
          raise NotImplementedError()

      def debias(self,
                 data: DataType,
                 meas_count: int) -> DebiasedDataType:
          """
          Debias the data due to the added noise, based on the number of
          measurements `meas_count`. This doesn't apply to all DP
          mechanisms. Some Client randomization mechanisms need this
          functionality.
          """
          return data

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 that with randomly flipped bits.

Chen, et al.              Expires 25 April 2024                [Page 11]
Internet-Draft                   DP-PPM                     October 2023

   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.  The debiased data type is expressed as a
   vector of floats, because of floating point arithmetic.  [CP:
   "because of floating point arithmetic" is a bit vague.]

   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].

4.3.1.  EPSILON_0-DP in Deletion-DP

      JC: We only add a definition of deletion-DP here since this is
      likely the only mechanism that provides deletion-DP in the OC
      trust model.  Putting it in overview might confuse readers early
      on, because we said only replacement-DP applies to DAP.

   Let P1(S, D, E) denote the probability that a randomized algorithm S,
   on an input measurement D, outputs a noisy measurement E.  Let P2(R,
   E) denote the probability that a reference noisy output R is equal to
   E.  A randomized algorithm S is said to be EPSILON_0-DP in the
   deletion-DP model, if there exists a reference distribution R, such
   that for all possible Client measurements D, and all possible noisy
   outputs E, we have:

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

Chen, et al.              Expires 25 April 2024                [Page 12]
Internet-Draft                   DP-PPM                     October 2023

   Intuitively, if we think of the reference distribution R as an
   average, noisy Client measurement, deletion-DP makes it hard to
   distinguish the Client measurement D from the measurement from an
   average Client.

4.3.2.  Reference Implementation

   Symmetric RAPPOR is specified by the DP mechanism SymmetricRappor
   below.

      TODO: We could make the sampler more efficient if we use binomial.

Chen, et al.              Expires 25 April 2024                [Page 13]
Internet-Draft                   DP-PPM                     October 2023

   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.  DP Policies for VDAFs

   The section defines a generic interface for DP policies for VDAFs.  A
   DP policy composes the following operations with execution of a VDAF:

   1.  An optional Client randomization mechanism that adds noise to
       Clients' measurements prior to sharding.

   2.  An optional Aggregator randomization mechanism that adds noise to
       an Aggregator's aggregate share prior to unsharding.

Chen, et al.              Expires 25 April 2024                [Page 14]
Internet-Draft                   DP-PPM                     October 2023

   3.  An optional debiasing step that removes the bias in DP mechanisms
       (i.e.  DpMechanism.debias) after unsharding.

   The composition of Client and Aggregator randomization mechanisms
   defines the DP policy for a VDAF, and enforces the DP guarantee.  In
   particular, a concrete DP policy is a subclass of DpPolicy:

   class DpPolicy:
       # Client measurement type.
       Measurement = None
       # Aggregate share type, owned by an Aggregator.
       AggShare = None
       # Aggregate result type, unsharded result from all Aggregators.
       AggResult = None
       # Debiased aggregate result type.
       DebiasedAggResult = None

       def add_noise_to_measurement(self,
                                    meas: Measurement,
                                    ) -> Measurement:
           """
           Add noise to measurement, if required by the Client
           randomization mechanism. The default implementation is to do
           nothing.
           """
           return meas

       def add_noise_to_agg_share(self,
                                  agg_share: AggShare,
                                  ) -> AggShare:
           """
           Add noise to aggregate share, if required by the Aggregator
           randomization mechanism. The default implementation is to do
           nothing.
           """
           return agg_share

       def debias_agg_result(self,
                             agg_result: AggResult,
                             meas_count: int,
                             ) -> DebiasedAggResult:
           """
           Debias aggregate result, if either of the Client or
           Aggregator randomization mechanism requires this operation,
           based on the number of measurements `meas_count`. The default
           implementation is to do nothing.
           """
           return agg_result

Chen, et al.              Expires 25 April 2024                [Page 15]
Internet-Draft                   DP-PPM                     October 2023

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 = []

Chen, et al.              Expires 25 April 2024                [Page 16]
Internet-Draft                   DP-PPM                     October 2023

             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.  Use Cases

Chen, et al.              Expires 25 April 2024                [Page 17]
Internet-Draft                   DP-PPM                     October 2023

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.

6.1.1.  Prio3MultiHotHistogram with Client Randomization

   Client randomization allows Clients to protect their privacy by
   adding noise to their measurements directly, as described in
   Appendix B.1.  Analyses ([FMT20] and [FMT22]) have shown that, in the
   OAMC trust model, we get good approximate-DP by aggregating noisy
   Clients' measurements with Client randomization.  In this policy, we
   will describe how to achieve approximate-DP, with each Client
   applying symmetric RAPPOR to its measurement.

   Our target VDAF is Prio3Histogram as specified in [VDAF].  This uses
   the Histogram circuit to enforce one-hotness of the measurement.  Due
   to the noising mechanism, a less strict circuit is required that
   tolerates a bounded number of non-0 entries in the vector.  We call
   this Prio3MultiHotHistogram.

      JC: Specify Prio3MultiHotHistogram.  This may end up in the base
      VDAF draft.  In the meantime, there is a reference implementation
      here: https://github.com/cfrg/draft-irtf-cfrg-vdaf/blob/main/poc/
      vdaf_prio3.py

   The Client randomization we will use here is the symmetric RAPPOR
   mechanism of Section 4.3, which is initialized with a EPSILON_0
   parameter.  We get (EPSILON, DELTA)-DP in the aggregate result, as
   long as there are at least batch_size number of honest Clients, each
   of which applies symmetric RAPPOR to its measurement, and contributes
   the noisy measurement to the batch.  The (EPSILON, DELTA)-DP degrades
   gracefully as the number of honest Clients decreases, i.e., we can
   still achieve (EPSILON', DELTA)-DP, where EPSILON' is larger than
   EPSILON.

Chen, et al.              Expires 25 April 2024                [Page 18]
Internet-Draft                   DP-PPM                     October 2023

      TODO(junyechen1996): Justify why RR with EPSILON_0 + batch_size
      can achieve (EPSILON, DELTA)-DP in the aggregate result.

   Because applying symmetric RAPPOR to an one-hot Client measurement
   can cause the noisy measurement to have multiple bits set, we need to
   check the noisy measurement has at most m number of 1s, per
   Section 4.5 of [TWMJ_23], to ensure robustness against malicious
   Clients, who attempt to bias the final histogram by setting many
   coordinates to be 1.

   Assume the length of the Client measurement is d, and there is
   exactly one bit set.  For the d - 1 coordinates with 0s, the
   probability p_0 of changing a coordinate from 0 to 1 is 1 /
   (exp(EPSILON_0) + 1) per Section 4.3, so we can model the number of
   1s in the noisy measurement as a binomial random variable C with
   number of trials d - 1, and probability p_0, plus the one bit that is
   already set.  Our goal is to ensure the probability p of 1 + C
   exceeding m is small enough, i.e., the false positive rate of a noisy
   measurement from an honest Client having more than m bits is at most
   p.  This is equivalent to finding m and p, such that the cumulative
   distribution function (CDF) satisfies Pr(C <= m - 1) >= 1 - p.

   Once we find m, we will use it to instantiate Prio3MultiHotHistogram
   to perform verification and aggregation.  The final aggregate result
   is debiased based on the number of measurements according to
   Section 4.3, in order to reduce the bias introduced during Client
   randomization.

Chen, et al.              Expires 25 April 2024                [Page 19]
Internet-Draft                   DP-PPM                     October 2023

   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)

6.1.1.1.  Utility

   As discussed in Section 4.3, as the number of Clients n increases,
   the noise at each coordinate of the debiased aggregate result
   approximates a Gaussian distribution with mean 0, and standard
   deviation sqrt(n * exp(EPSILON_0) / (exp(EPSILON_0) - 1)^2).  We will
   look at the standard deviation generated by symmetric RAPPOR from n
   Clients, in order to achieve various combinations of (EPSILON,
   DELTA)-DP.

      +=========+=======+====================+=====================+
      | EPSILON | DELTA | Standard deviation | Internal Parameters |
      +=========+=======+====================+=====================+
      | 0.317   | 1e-9  | 26.1337            | n = 100000,         |
      |         |       |                    | EPSILON_0 = 5.0     |
      +---------+-------+--------------------+---------------------+
      | 0.906   | 1e-9  | 12.2800            | n = 100000,         |
      |         |       |                    | EPSILON_0 = 6.5     |
      +---------+-------+--------------------+---------------------+
      | 1.528   | 1e-9  | 9.5580             | n = 100000,         |
      |         |       |                    | EPSILON_0 = 7.0     |
      +---------+-------+--------------------+---------------------+

            Table 1: Utility of Pure Client Randomization for
                           histogram use case.

Chen, et al.              Expires 25 April 2024                [Page 20]
Internet-Draft                   DP-PPM                     October 2023

6.1.2.  Prio3Histogram with Aggregator Randomization

   Aggregator Randomization requires Aggregators to add noise to their
   aggregate shares before outputting them.  Under OAOC trust model, we
   can achieve good EPSILON-DP, or (EPSILON, DELTA)-DP, as long as at
   least one of the Aggregators is honest.  The amount of noise needed
   by the Aggregator randomizer typically depends on the target DP
   parameters EPSILON and DELTA, and also the SENSITIVITY Section 3.2 of
   the aggregation function.

   In this section, we describe how to achieve (EPSILON, DELTA)-DP for
   Prio3Histogram Section 7.4.4 of [VDAF] by asking each Aggregator to
   independently add discrete Gaussian noise to its aggregate share.

   We use the discrete Gaussian mechanism described in Section 4.2,
   which has a mean of 0, and is initialized with a SIGMA parameter that
   stands for the standard deviation of the Gaussian distribution.  In
   order to achieve (EPSILON, DELTA)-DP in the OAOC trust model, all
   Aggregators need to independently add discrete Gaussian noise to all
   coordinates of their aggregate shares.

   Theorem 8 in [BW18] shows how to compute SIGMA parameter for
   continuous Gaussian, based on the given (EPSILON, DELTA)-DP
   parameters and L2-sensitivity, and Theorem 7 in [CKS20] shows a
   similar result for discrete Gaussian.  For the current use case, the
   L2-sensitivity is sqrt(2), because transforming an one-hot vector
   into another will affect two coordinates, e.g., transforming an one-
   hot vector [1, 0] to [0, 1] changes L2-sensitivity by sqrt((1 - 0)^2
   + (0 - 1)^2) = sqrt(2).  Algorithm 1 in [BW18] elaborates on how to
   compute SIGMA, and we will refer to the calculation in the open
   sourced code [AGM].

      JC: We will need to provide an explanation of the parameter
      calculation in the draft itself, instead of merely referring to
      the code.

      KT: [CKS20] mentions in Theorem 7 about the difference of
      approximate-DP achieved by discrete [CKS20] and continuous
      Gaussian [BW18] that: The discrete and continuous Gaussian attain
      almost identical guarantees for large SIGMA, but the
      discretization creates a small difference that becomes apparent
      for small SIGMA.  Therefore, if we use Algorithm 1 from [BW18], we
      will need to be careful when SIGMA is small, i.e., the desired
      (EPSILON, DELTA)-DP is weak.

Chen, et al.              Expires 25 April 2024                [Page 21]
Internet-Draft                   DP-PPM                     October 2023

      JC: It's also worth exploring the utility of discrete Gaussian
      proven by Definition 3 in [CKS20], which defines the concentrated-
      DP achieved by discrete Gaussian.  Concentrated-DP is then
      converted to approximate-DP, which is our target here.  As a first
      draft, we won't overwhelm readers with other types of DP.

  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,

Chen, et al.              Expires 25 April 2024                [Page 22]
Internet-Draft                   DP-PPM                     October 2023

                            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

6.1.2.1.  Utility

   We will demonstrate the utility of this policy in the table below in
   terms of the standard deviation SIGMA in discrete Gaussian needed to
   achieve various combinations of (EPSILON, DELTA)-DP, based on the
   open-sourced code in [AGM].

   It's worth noting that if more than one Aggregator is honest, we will
   lose some utility because each Aggregator is independently adding
   noise.  The standard deviation in the aggregate result thus becomes
   SIGMA * sqrt(c), where c is the number of honest Aggregators.  In the
   table below, the numbers in "Standard deviation" column assume c = 2.
   The numbers in "Standard deviation (OAOC)" column assume only one
   Aggregator is honest.

   +=========+=======+====================+===========================+
   | EPSILON | DELTA | Standard deviation | Standard deviation (OAOC) |
   +=========+=======+====================+===========================+
   | 0.317   | 1e-9  | 33.0788            | 23.3903                   |
   +---------+-------+--------------------+---------------------------+
   | 0.906   | 1e-9  | 12.0777            | 8.5402                    |
   +---------+-------+--------------------+---------------------------+
   | 1.528   | 1e-9  | 7.3403             | 5.1904                    |
   +---------+-------+--------------------+---------------------------+

     Table 2: Utility of Pure Aggregator Randomization for histogram
                                use case.

7.  Security Considerations

   TODO Security

8.  IANA Considerations

   This document has no IANA actions.

9.  References

9.1.  Normative References

Chen, et al.              Expires 25 April 2024                [Page 23]
Internet-Draft                   DP-PPM                     October 2023

   [DAP]      Geoghegan, T., Patton, C., Rescorla, E., and C. A. Wood,
              "Distributed Aggregation Protocol for Privacy Preserving
              Measurement", Work in Progress, Internet-Draft, draft-
              ietf-ppm-dap-07, 14 September 2023,
              <https://datatracker.ietf.org/doc/html/draft-ietf-ppm-dap-
              07>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

   [RFC8446]  Rescorla, E., "The Transport Layer Security (TLS) Protocol
              Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
              <https://www.rfc-editor.org/rfc/rfc8446>.

   [RFC9180]  Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid
              Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180,
              February 2022, <https://www.rfc-editor.org/rfc/rfc9180>.

   [VDAF]     Barnes, R., Cook, D., Patton, C., and P. Schoppmann,
              "Verifiable Distributed Aggregation Functions", Work in
              Progress, Internet-Draft, draft-irtf-cfrg-vdaf-07, 31
              August 2023, <https://datatracker.ietf.org/doc/html/draft-
              irtf-cfrg-vdaf-07>.

9.2.  Informative References

   [AGM]      "analytic-gaussian-mechanism", n.d.,
              <https://github.com/BorjaBalle/analytic-gaussian-
              mechanism>.

   [BS16]     Bun, M. and T. Steinke, "Concentrated Differential
              Privacy: Simplifications, Extensions, and Lower Bounds",
              2016, <https://arxiv.org/abs/1605.02065>.

   [BW18]     Balle, B. and Y. Wang, "Improving the Gaussian Mechanism
              for Differential Privacy: Analytical Calibration and
              Optimal Denoising", 2018,
              <https://arxiv.org/abs/1805.06530>.

   [CKS20]    Canonne, C. L., Kamath, G., and T. Steinke, "The Discrete
              Gaussian for Differential Privacy", 2020,
              <https://arxiv.org/abs/2004.00010>.

Chen, et al.              Expires 25 April 2024                [Page 24]
Internet-Draft                   DP-PPM                     October 2023

   [DMNS06]   Dwork, C., McSherry, F., Nissim, K., and A. Smith,
              "Calibrating Noise to Sensitivity in Private Data
              Analysis", 2006,
              <https://link.springer.com/chapter/10.1007/11681878_14>.

   [DR14]     Dwork, C. and A. Roth, "The Algorithmic Foundations of
              Differential Privacy", 2014,
              <https://www.cis.upenn.edu/~aaroth/Papers/
              privacybook.pdf>.

   [EFMR_20]  Erlingsson, Ú., Feldman, V., Mironov, I., Raghunathan, A.,
              Song, S., Talwar, K., and A. Thakurta, "Encode, Shuffle,
              Analyze Privacy Revisited: Formalizations and Empirical
              Evaluation", 2020, <https://arxiv.org/abs/2001.03618>.

   [EPK14]    Erlingsson, Ú., Pihur, V., and A. Korolova, "RAPPOR:
              Randomized Aggregatable Privacy-Preserving Ordinal
              Response", 2014, <https://arxiv.org/abs/1407.6981>.

   [FMT20]    Feldman, V., McMillan, A., and K. Talwar, "Hiding Among
              the Clones: A Simple and Nearly Optimal Analysis of
              Privacy Amplification by Shuffling", 2020,
              <https://arxiv.org/abs/2012.12803>.

   [FMT22]    Feldman, V., McMillan, A., and K. Talwar, "Stronger
              Privacy Amplification by Shuffling for Rényi and
              Approximate Differential Privacy", 2022,
              <https://arxiv.org/abs/2208.04591>.

   [KM11]     Kifer, D. and A. Machanavajjhala, "No free lunch in data
              privacy", 2011,
              <https://dl.acm.org/doi/abs/10.1145/1989323.1989345>.

   [KOV15]    Kairouz, P., Oh, S., and P. Viswanath, "The Composition
              Theorem for Differential Privacy", 2015,
              <http://proceedings.mlr.press/v37/kairouz15.pdf>.

   [Mir17]    Mironov, I., "Rényi Differential Privacy", 2017,
              <https://arxiv.org/abs/1702.07476>.

   [MJTB_22]  McMillan, A., Javidbakht, O., Talwar, K., Briggs, E.,
              Chatzidakis, M., Chen, J., Duchi, J., Feldman, V., Goren,
              Y., Hesse, M., Jina, V., Katti, A., Liu, A., Lyford, C.,
              Meyer, J., Palmer, A., Park, D., Park, W., Parsa, G.,
              Pelzl, P., Rishi, R., Song, C., Wang, S., and S. Zhou,
              "Private Federated Statistics in an Interactive Setting",
              2022, <https://arxiv.org/abs/2211.10082>.

Chen, et al.              Expires 25 April 2024                [Page 25]
Internet-Draft                   DP-PPM                     October 2023

   [MPRV09]   Mironov, I., Pandey, O., Reingold, O., and S. Vadhan,
              "Computational Differential Privacy", n.d.,
              <https://link.springer.com/
              chapter/10.1007/978-3-642-03356-8_8>.

   [TWMJ_23]  Talwar, K., Wang, S., McMillan, A., Jina, V., Feldman, V.,
              Basile, B., Cahill, A., Chan, Y., Chatzidakis, M., Chen,
              J., Chick, O., Chitnis, M., Ganta, S., Goren, Y.,
              Granqvist, F., Guo, K., Jacobs, F., Javidbakht, O., Liu,
              A., Low, R., Mascenik, D., Myers, S., Park, D., Park, W.,
              Parsa, G., Pauly, T., Priebe, C., Rishi, R., Rothblum, G.,
              Scaria, M., Song, L., Song, C., Tarbe, K., Vogt, S.,
              Winstrom, L., and S. Zhou, "Samplable Anonymous
              Aggregation for Private Federated Data Analysis", 2023,
              <https://arxiv.org/abs/2307.15017>.

Appendix A.  Contributors

   Pierre Tholoniat Columbia University pierre@cs.columbia.edu

Appendix B.  Overview of Differential Privacy

   Differential privacy is a set of techniques used to protect the
   privacy of individuals when analyzing user's data.  It provides a
   mathematical framework that ensures the analysis of a dataset does
   not reveal identifiable information about any specific individuals.
   The advantage of differential privacy is that it provides a strong,
   quantifiable and composable privacy guarantee.  The main idea of
   differential privacy is to add carefully calibrated noise to the
   results, which makes it difficult to determine with high certainty
   whether a specific individual's data was included in the results or
   not.

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.

Chen, et al.              Expires 25 April 2024                [Page 26]
Internet-Draft                   DP-PPM                     October 2023

   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.

Chen, et al.              Expires 25 April 2024                [Page 27]
Internet-Draft                   DP-PPM                     October 2023

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.

Chen, et al.              Expires 25 April 2024                [Page 28]
Internet-Draft                   DP-PPM                     October 2023

   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.5.1.  (ALPHA, TAU)-Rényi DP

   A formal definition of Rényi DP can be found in Definitions 3 and 4
   of [Mir17].

   The intuition behind Rényi-DP is to use TAU parameter to measure the
   divergence of probability distributions of querying two adjacent
   databases, given Rényi order parameter ALPHA.  The smaller the TAU
   parameter, the harder it is to distinguish the outputs from querying
   two adjacent databases, and thus the stronger the privacy guarantee
   is.

   One can compose multiple Rényi DP guarantees based on Proposition 1
   of [Mir17].  After composition, one can convert the (ALPHA, TAU)-
   Rényi DP guarantee to (EPSILON, DELTA)-approximate DP, per
   Proposition 12 of [CKS20].

B.5.2.  Zero Concentrated-DP

   A formal definition of zero Concentrated-DP can be found in
   Definition 1.1 of [BS16].

   Zero Concentrated-DP uses different parameters from Rényi-DP, but
   uses a similar idea to measure the output distribution divergence of
   querying two adjacent databases.

   One can compose multiple zCDP guarantees, per Lemma 1.7 of [BS16].

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

Authors' Addresses

   Junye Chen
   Apple Inc.

Chen, et al.              Expires 25 April 2024                [Page 29]
Internet-Draft                   DP-PPM                     October 2023

   Email: junyec@apple.com

   Audra McMillan
   Apple Inc.
   Email: audra_mcmillan@apple.com

   Christopher Patton
   Cloudflare
   Email: chrispatton+ietf@gmail.com

   Kunal Talwar
   Apple Inc.
   Email: ktalwar@apple.com

   Shan Wang
   Apple Inc.
   Email: shan_wang@apple.com

Chen, et al.              Expires 25 April 2024                [Page 30]