Prio: Private, Robust, and Efficient Computation of Aggregate Statistics
Henry Corrigan-Gibbs came to give a talk on his NSDI paper on private computation of aggregate statistics. I’ll provide an overview of his work, but for more details, especially on the cryptography protocols, I refer you to the paper.
Today, an application provider aggregates cleartext user data to obtain statistics, so there is no privacy. Moreover, the application learns all of the user data rather than just the aggregate. Is there a way to preserve individual user’s data and allow the application to just learn the aggregated data?
Prio accomplishes this goal. At a high level, there are multiple providers, and clients send an encrypted share of their data to each aggregator, and the aggregators learn no private client data.
Prio has a scheme to provide exact correctness, privacy, and efficiency and supports a large range of aggregates. Finally, in order to provide robustness while maintaining efficiency, Prio uses secret-shared non-interactive proofs (SNIPs). The main idea behind it is that the client generates the transcripts that servers would have observed in a multi-party computation. It’s much easier for a server to check a transcript than generate it. The exact schemes are fairly involved, so I will let the reader check out the paper.
The evaluation of Prio shows that it is orders of magnitudes faster than previous approaches because it does not use any public-key cryptography, and Prio can cover a large class of statistics.
This is an interesting and practical way to do certain multi-party computations. For more information, I ask that you check out the paper.