STAR: Distributed Secret Sharing for Private Threshold Aggregation Reporting

In practice and research, threshold aggregation systems~ -- ~that attempt to preserve client K-anonymity during data analysis~ -- ~incur significant implementation hurdles, including: i) use of trusted servers; ii) complex and expensive coordination between clients to ensure records are not identifying; and iii) protocols that are expensive in terms of computation, network use, or both. In this work, we present STAR (Distributed Secret Sharing for Threshold Aggregation Reporting): a performant solution allowing untrusted threshold aggregation of collected data, using techniques taken from $\kappa$-out-of-$\eta$ threshold secret sharing. Server-side aggregation in our protocol takes only 21 seconds for data received from 1,000,000 clients. Furthermore, it requires only a single message sent from each client to the untrusted aggregation server (at most 129 bytes), and no interaction between clients. Additionally, STAR is extensible in that clients can send additional data with their measurement, which is only revealed if the threshold check is satisfied. The STAR protocol supports multiple deployment scenarios. For instance, when client inputs come from a highly entropic input distribution STAR requires only a single untrusted server. When such guarantees cannot be made, STAR can be deployed using a second non-colluding randomness server, to provide clients with an outsourced method for generating shared randomness. Finally, this work makes novel cryptographic contributions in defining and constructing puncturable partially oblivious PRF (PPOPRF) protocols, which we expect to be useful in applications beyond STAR.