Subject: [Ppm] Background

From: Eric Rescorla <[email-masked]>
Date: Fri, 27 Aug 2021 18:58:28 -0700

Welcome to PPM,

Hi folks, welcome to the PPM list. I just wanted to send out
a bit of introduction/background.

There are a lot of cases where one wants to take measurements of
values that are sensitive individually but not in aggregate, and the
person/entity taking the measurement doesn't care about people's
individual values. These cases include both technical measurements as
well as non-technical ones, for instance:

- Medical status of various kinds
- Financial status
- Web sites that don't render properly or cause an error of
  some kind

Historically, the options for taking this kind of measurement were
fairly limited: in a few cases the person taking the measurement could
credibly convince people their data would be kept confidential and in
others you could use Randomized Response or similar techniques such as
RAPPOR. You could also sometimes send anonymous reports over some sort
of proxy network like Tor or Apple's Private Relay. However, there are
a lot of situations where these options don't work well.

In the past few years, cryptographic techniques have emerged that
allow for efficient measurement of aggregates without requiring trust
in a single party. The basic idea is that there are two independent
servers and the client takes their reported value and divides it up
into 2 or more secret shares, sending one to each server. The servers
then independently aggregate (e.g., add up) the reports and then
exchange the aggregates to get the final value. Because each server
only has a share, as long as at least one server is trustworthy, the
user's value is never revealed [Technical Note: each share also comes
with a zero-knowledge proof of validity which prevents clients from
reporting values which would invalidate the result.  For instance, we
might allow clients to report that they had incomes up to 10^9 but not
10^100th. This lines up with other surveying techniques which attempt
to prevent plainly invalid responses but still allow people to lie.]

The available techniques [CB17][BBCGI21] allow for a variety of
aggregation tasks, including:

- Sum/Mean/geometric mean
- Other statistics such as variance that can be computed by
  addition of values
- Histograms
- Finding the most common strings out of a collection of client-submitted
  values ("heavy hitters")

There have already been two prototype deployments of one of these
techniques (Prio), one by Mozilla and the other by Apple, Google,
ISRG, NCI, and MITRE, so we have some evidence they can be deployed at
scale. There's already a fair amount of interest in these technologies
and ISRG has already announced that they plan to offer a public
Prio service https://www.abetterinternet.org/post/introducing-prio-services/
.

We're looking to standardize these technologies for Privacy Preserving
Measurement. The idea would be to have a protocol in IETF that
described the networking pieces and then work in CFRG to define the
crypto pieces. A draft of the protocol can be found at:
https://abetterinternet.github.io/prio-documents/draft-ppm-protocol.html
The CFRG pieces are still in development.

We've asked for a BOF at IETF 112:
https://datatracker.ietf.org/doc/bofreq-privacy-preserving-measurement/

Happy to answer any questions people might have.

-Ekr

[CB17] Corrigan-Gibbs and Boneh, "Prio: Private, Robust, and Scalable
Computation of Aggregate Statistics"
https://www.usenix.org/system/files/conference/nsdi17/nsdi17-corrigan-gibbs.pdf

[BBCGI21] Boneh, Boyle, Corrigan-Bibbs, Gilboa, Ishai, "Lightweight
Techniques for Private Heavy Hitters", https://eprint.iacr.org/2021/017