[Ppm] Whisper: Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs

[Christopher Patton <[e-mail]>]

Hi gang,

I wanted to make folks aware of a new paper, from Henry Corrigan-Gibbs and
friends, that has a couple of really cool features that are relevant to
this group:
https://eprint.iacr.org/2024/666

The first is a new batched verification technique that reduces the
Leader-Helper communication for Prio3. Supporting this would require
changes to DAP, though they might not be that bad (
https://github.com/ietf-wg-ppm/draft-ietf-ppm-dap/issues/561) The main
downside is that the communication cost increases as the number of
malicious clients increases: in the worst case the cost is about the same
as it is today. The implication is that there is an efficient DoS vector
that we'd have to engineer around.

The second exciting piece of this paper is a new approach to heavy hitters.
Whereas Poplar1 requires a round of aggregation per bit of input, Whisper
runs in just one round of aggregation, like Prio3 does. Plus, we can get
this benefit without changes to DAP if we forego batched verification. The
downside here is higher Client-Aggregator communication, plus the result is
only approximately correct (Poplar1 gives you an exact solution).

I'd love to hear folks' thoughts on this. I'd especially like to understand
if there's an appetite for doing batched verification.

Chris P.