Can / should VDAF support DP shufflers?

[csharrison]

Shuffle differential privacy (https://arxiv.org/pdf/1811.12469.pdf and many other papers) is a type of differential privacy where the privacy mechanism can be thought of as a composition of two pieces:

1. A local randomizer applying some local noise to data (and stripping identifiers, etc)
2. A central curator that takes as input a batch of client data and simply applies a permutation on it

The power of the shuffle DP is that the server-side mechanism is simple and general purpose. The exact same shuffler can be used for different applications measuring different kinds of things. Privacy guarantees are based on two things:

1. The level of local noise added to the data
2. The number of clients that participate in a shuffle

At an intuitive level, the more reports you have, and the more noise is injected into the reports, the more a given client's input is "hidden in the crowd".

Is this a good fit for VDAFs? Shuffling is conceptually a very simple task to ask a 2-party MPC protocol to do. I could imagine slotting this into the VDAF structure like:

• Clients split their local data D into "shares" where Helper 1 gets Enc2(D) and Helper 2 gets Enc1(null). (Which helper gets the real message can be randomized). Note that nested encryption is used so that no helper can see any raw data before it is shuffled.
• When each helper gets its batch of data, it will run it through a shuffle step, and send the shuffle results to the other helper
• After the exchange, the helpers shuffle the exchanged batches one more time (ensuring all data is shuffled twice, once by each helper).
• Helpers can then decrypt the data and share each shuffled batch to the collector

Possible concerns:

• In the simple example above, helpers learn a shuffled version of the true data (i.e. a DP release). The protocol is not zero-knowledge. This could probably be fixed, there is no need for helpers to learn any raw data.
• We rely exclusively on DP for the protection. Whether this can be called "aggregation" is maybe subject for debate. Certainly you can say that (if the batches are large enough, with enough noise), that no individual's data can be learned
• The splitting of shares and helpers independently shuffling partial batches is a bit awkward. Probably the ideal mechanism would be for clients to send all data to Helper 1, which shuffles and sends to Helper 2, which sends data to the collector. Parallel shuffling buys us nothing.
• Some shuffle protocols may want some kind of "label" in the clear, with minimum batch sizes per label.

Anyways, thoughts appreciated! Shuffling can be a simple and effective way to achieve good privacy with very simple mechanisms, but it doesn't fit so well into VDAFs.

cc @schoppmp

[cjpatton]

Interesting idea! This does indeed sound like a practical way to get good privacy. Even without DP, you get unlinkability of measurements to the client that sent them. This is basically what a mixnet does.

• From a syntax perspective, this kind of construction doesn't fit because it requires the aggregation phase to be interactive. Currently the VDAF syntax permits interaction only during the preparation phase. More to the point, shuffling requires O(n) space to compute the aggregate result, where n is the number of measurements. On the other hand, evaluating the prio3 or hits VDAF requires just O(1) space.
• From a security perspective, unlinkability of measurements to senders is useful, but is weaker than what we hope to achieve for, say, prio3 or hits, which is that they learn only the aggregate result. Perhaps there's a way to patch the scheme to prevent leaking the set of measurements, as you suggest. But suppose we manage to ensure that all the aggregators learn is the aggregate result: then what does shuffling buy us?
• Broadening our perspective a bit, consider that VDAFs are special purpose in the sense that a particular VDAF is only suitable for as particular (class of) aggregation functions. On the other hand, the shuffling scheme you're proposing is general purpose: pretty much any aggregation function can be computed this way, you just need to be able to define a "null" input. I think the purpose of this document should be to standardize an interface between general purpose "wrapper" protocols, like PPM, to special purpose schemes that are all ensure some baseline notion of security.

My own conclusion is that this protocol shape isn't appropriate for the VDAF document, however this may well be in-scope for what the PPM working group does.

What do you think @bifurcation?

[cjpatton]

By the way, I'm reading https://eprint.iacr.org/2021/1490.pdf right now. This protocol seems to have some shuffling, but also seems to aim for a security property stronger than unlinkability. I think if we can achieve the same security for this protocol as for prio3/hits, I think it's worth considering including it here.

[csharrison]

Thanks @cjpatton , this makes sense to me. A few quick responses below:

From a security perspective, unlinkability of measurements to senders is useful, but is weaker than what we hope to achieve for, say, prio3 or hits, which is that they learn only the aggregate result. Perhaps there's a way to patch the scheme to prevent leaking the set of measurements, as you suggest. But suppose we manage to ensure that all the aggregators learn is the aggregate result: then what does shuffling buy us?

One thing shuffling buys you is flexibility. Let's say all my users input data in [0, 10]. You could imagine a couple of different ways of aggregating this data, e.g. reporting the sum, median, percentiles, etc. With a shuffled version of the data, you can compute all of these on the collector side without embedding the computations in the aggregators.

There is also flexibility in terms of data used. In principle (as long as you trust the clients), the aggregators can just be shuffling opaque bytes. Clients could update to submit different kinds of data without any behavior update needed on the aggregator side. For instance, rather than shuffling integers they could shuffle sketches or some other data structure.

By the way, I'm reading https://eprint.iacr.org/2021/1490.pdf right now. This protocol seems to have some shuffling, but also seems to aim for a security property stronger than unlinkability. I think if we can achieve the same security for this protocol as for prio3/hits, I think it's worth considering including it here.

This proposal is interesting but it isn't the same kind of general purpose shuffling I'm discussing here. That paper only discusses computing histograms.

[cjpatton]

I agree the flexibility is attractive. My point about shuffling alone doesn't prevent aggregators from learning the set of measurements. Indeed, this is what makes it so flexible!

[csharrison]

I agree the flexibility is attractive. My point about shuffling alone doesn't prevent aggregators from learning the set of measurements. Indeed, this is what makes it so flexible!

Oh sorry I missed this point. It should be easy to ensure that the shuffled data is not visible to the aggregators if they don't collude with the collector - just ensure all the data is also encrypted to the collector's key. The requirement is just that the MPC shuffles opaque blobs.

[cjpatton]

Right, but the collector would see the set of measurements in the clear, right? All the aggregators have done is permuted them.

[csharrison]

The collector sees the set of measurements "in the clear", but the technique is designed to be combined with local noise so it isn't really accurate to say that the final release contains the all of the original measurements.

[cjpatton]

Yes, true enough!

[cjpatton]

We are beginning to see the emergence of MPC techniques that involve some sort of in-MPC "shuffling" or "ordering" of the reports being aggregated. Example:

• IPA: https://github.com/private-attribution/ipa
• @schoppmp's shuffling protocol for sparse histograms: https://eprint.iacr.org/2022/920

I think where we're landing is that this architecture is sufficiently different from VDAFs that we should not try to shoe-horn them into this particular document.