STAR: Secret Sharing for Private Threshold Aggregation Reporting
Alex Davidson (Brave Software), Peter Snyder (Brave Software), E.B. Quirk (Brave Software), Joseph Genereux (Brave Software), Benjamin Livshits (Imperial College London), Hamed Haddadi (Imperial College London, Brave Software) | Cryptography, Privacy
Threshold aggregation reporting systems promise a practical, privacy-preserving solution for developers to learn how their applications are used “in-the-wild”. Unfortunately, proposed systems to date prove impractical for wide scale adoption, suffering from a combination of requiring: i) prohibitive trust assumptions; ii) high computation costs; or iii) massive user bases. As a result, adoption of truly-private approaches has been limited to only a small number of enormous (and enormously costly) projects.
In this work, we improve the state of private data collection by proposing STAR, a highly efficient, easily deployable system for providing cryptographically-enforced đťś…-anonymity protections on user data collection. The STAR protocol is easy to implement and cheap to run, all while providing privacy properties similar to, or exceeding the current state of-the-art. Measurements of our open-source implementation of STAR find that STAR is 1773Ă— quicker, requires 62.4Ă— less communication, and is 24Ă— cheaper to run than the existing state-of-the-art.