Discussion: How to integrate differential privacy into janus?

[MxmUrw]

Since https://github.com/divviup/libprio-rs/pull/578 is now merged, I would like to start the discussion about how to integrate dp into janus:

The architectural additions from that PR amount to:

• There is a new trait

  trait AggregatorWithNoise<K,N,DPStrategy> : Aggregator<K,N>

  which inherits from Aggregator but additionally takes a DP strategy as type parameter. It requires the following method to be implemented:

  /// Adds noise to an aggregate share such that the aggregate result is differentially private
  /// as long as one Aggregator is honest.
  fn add_noise_to_agg_share(
      &self,
      dp_strategy: &DPStrategy,
      agg_param: &Self::AggregationParam,
      agg_share: &mut Self::AggregateShare,
      num_measurements: usize,
  ) -> Result<(), VdafError>;

  This method has to be called from janus by both leader and helper, on aggregate shares, with an appropriate dp_strategy argument.

• Regarding DP strategies: a DP strategy allows the user to configure the mechanism for noising, and the amount of noise added. It is a combination of choice of budget type and choice of distribution. Examples are: ZCdpDiscreteGaussian or ApproximateDpLaplace. Different VDAFs may choose to support different DP strategies. The runtime representation of a strategy is its budget, also called the privacy parameter(s). For example, the concept of zCDP-differential privacy has a single parameter $\epsilon$, while approximate differential privacy has two, $\epsilon$ and $\delta$.

What I think we need to do is:

• Extend the definition of a Task with a field for DP strategy. Since implementers of the DPStrategy trait are distinct types, we need to combine them into an enum, similar to how VdafOps can contain any vdaf.
• The call to add_noise_to_agg_share needs to be done somewhere in janus after summing the shares. @tgeoghegan suggested to do it in aggregator::aggregate_share::compute_aggregate_share.

Question

The main question I have right now is: How do we dispatch the add_noise_to_agg_share call correctly?

I see two possible approaches:

1. Replace, in relevant places, the occurrence of Aggregator<K,N> by AggregatorWithNoise<K,N,S>. Relevant places would include handle_aggregate_share_generic. Then the strategy parameter would be handled similarly to the VERIFY_KEY_SIZE and NONCE_SIZE parameters, and dispatch could be mostly handled by the vdaf_ops! macro. This means that if a VDAF wanted to implement two different DP strategies, there would be one enum variant for each strategy. I assume that usually there is one preferable way to do dp for a given aggregation, so the dispatch blow-up should be minimal. Another consequence is that every VDAF would have to support at least one DP strategy. Thus we would create a NoDpStrategy for VDAFs which do not need dp.
2. Create an additional dispatch mechanism for AggregatorWithNoise and instances of DPStrategy. I am not sure how this would exactly look like, but this would allow AggregatorWithNoise to be opt-in, with VDAFs only having to implement it if they do need dp.

Note that in both cases there has to be code which forwards the user chosen DP strategy (runtime enum value) to the AggregatorWithNoise (compiletime type), and throws an error if this particular strategy is not implemented by that VDAF. (This is implied by both approaches above, but I wanted to make it explicit.)

Comments? Opinions?

[branlwyd]

1 fits with the existing implementation strategy, and won't slow down compilation as long as the assumption that there will be one-DP-strategy-per-VDAF holds true. To be clear, we would need to replace Aggregator with AggregatorWithNoise roughly everywhere that calls (directly or indirectly) into compute_aggregate_share, correct? How would we deal with VDAFs that don't support DP at all -- a blanked implementation of AggregatorWithNoise for NoDpStrategy?

[MxmUrw]

To be clear, we would need to replace Aggregator with AggregatorWithNoise roughly everywhere that calls (directly or indirectly) into compute_aggregate_share, correct?

Yes, though it seems at first glance that no indirect calls need to be replaced! The only calls into compute_aggregate_share happen in aggregator::handle_aggregate_share_generic and collection_job_driver::step_collection_job_generic. In both cases the Aggregator type parameter comes from the vdaf_dispatch! macro, which means that it is "locally generated".

Note that currently compute_aggregate_share does not take an argument of type Aggregator, so in practice we either would have to add an AggregatorWithNoise argument, or instead write our own function which is going to be called directly after compute_aggregate_share at both call-sites I mentioned above.

How would we deal with VDAFs that don't support DP at all -- a blanked implementation of AggregatorWithNoise for NoDpStrategy?

Correct, any VDAF which doesn't support DP would need to implement AggregatorWithNoise<_,_,NoDpStrategy>. EDIT: And yes, the implementation would essentially be the identity function.

[MxmUrw]

We have implemented approach 1 here: #1892. Personally I think it fits quite well with the current janus architecture. See that PR for a summary of changes, comments welcome!

[tgeoghegan]

The related PRs have landed across libprio and Janus. I don't believe there's any further work to do here so I'm going to close. Maxim, Olivia, please feel free to re-open if there's more you want to discuss here.