Paper 2021/576

Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares

Surya Addanki
Kevin Garbe
Eli Jaffe
Rafail Ostrovsky
Antigoni Polychroniadou

This paper introduces Prio+, a privacy-preserving system for the collection of aggregate statistics, with the same model and goals in mind as the original and highly influential Prio paper by Henry Corrigan-Gibbs and Dan Boneh (USENIX 2017). As in the original Prio, each client holds a private data value (e.g. number of visits to a particular website) and a small set of servers privately compute statistical functions over the set of client values (e.g. the average number of visits). To achieve security against faulty or malicious clients, Prio+ clients use Boolean secret-sharing instead of zero-knowledge proofs to convince servers that their data is of the correct form and Prio+ servers execute a share conversion protocols as needed in order to properly compute over client data. This allows us to ensure that clients’ data is properly formatted essentially for free, and the work shifts to novel share-conversion protocols between servers, where some care is needed to make it efficient. While our overall approach is a fairly simple observation in retrospect, it turns out that Prio+ strategy reduces the client’s computational burden by up to two orders of magnitude (or more depending on the statistic) while keeping servers costs comparable to Prio. Prio+ permits computation of exactly the same wide range of complex statistics as the original Prio protocol, including high-dimensional linear regression over private values held by clients. We report detailed benchmarks of our Prio+ implementation and compare these to both the original Go implementation of Prio and the Mozilla implementation of Prio. Our Prio+ software is open-source and released with the same license as Prio.

Note: Fixed minor typos, mostly references to edaBit-based protocol removed during previous edits. Also updated to reflect the paper's publication at SCN 2022.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. SCN 2022 (Security and Cryptography for Networks)
priomulti-party computationanonymitydistributed cryptographysecret-sharingzero knowledgeimplementation
Contact author(s)
jaffe eli96 @ gmail com
2023-08-24: last of 3 revisions
2021-05-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Surya Addanki and Kevin Garbe and Eli Jaffe and Rafail Ostrovsky and Antigoni Polychroniadou},
      title = {Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares},
      howpublished = {Cryptology ePrint Archive, Paper 2021/576},
      year = {2021},
      doi = {10.1007/978-3-031-14791-3_23},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.