[tor-dev] Proposal 288: Privacy-Preserving Statistics with Privcount in Tor (Shamir version)

[Aaron Johnson]

>> in Prio, servers use a generic secure multi-party computation (MPC) protocol to compute the circuits. If Tor is going to do that, why not just run a generic MPC protocol over all of the inputs? Doing so would allow Tor statistics aggregations to be robust to inputs that are likely “incorrect” given the values of the other inputs (see “robust statistics” for a wide variety of useful such computations, including for example median, trimmed mean, least trimmed squares, maximum likelihood estimation). Applying MPC over all inputs would only require implementing the “offline” phase of the computation (e.g. producing the “multiplication triples”, which are supplied by the client in Prio). There are reasonably efficient protocols for doing so, including SDPZ and TinyOT [1].
> 
> If I understand you correctly, you are saying that we can add
> a secure multiparty computation to the Tally Reporters without
> changes on the Data Collectors?

Yes, that is correct. The MPC servers would get the (secret-shared) inputs, and then instead of just adding them and publishing the result, they would perform an MPC computation on them.

Now, we could in theory improve Data Collectors so that they can obliviously maintain statistics that aren’t just counts. For example, this would enable us to store a maximum of observed values (e.g. most streams per circuit seen over all circuits through that exit). How that could be done with adequate efficiency isn’t clear to me, though (it seems like a research question).

Best,
Aaron