Paper 2024/221

Mastic: Private Weighted Heavy-Hitters and Attribute-Based Metrics

Dimitris Mouris, Nillion, University of Delaware
Christopher Patton, Cloudflare
Hannah Davis, Seagate
Pratik Sarkar, Supra Research
Nektarios Georgios Tsoutsos, University of Delaware

Insight into user experience and behavior is critical to the success of large software systems and web services. Yet gaining such insights, while preserving user privacy, is a significant challenge. Recent advancements in multi-party computation have made it practical to compute verifiable aggregates over secret shared data. One important use case for these protocols is heavy hitters, where the servers compute the most popular inputs held by the users without learning the inputs themselves. The Poplar protocol (IEEE S&P 2021) focuses on this use case, but cannot support other aggregation tasks. Another such protocol, Prio (NSDI 2017), supports a wider variety of statistics but is unsuitable for heavy hitters. We introduce Mastic, a flexible protocol for private and verifiable general-purpose statistics based on function secret sharing and zero-knowledge proofs on secret shared data. Mastic is the first to solve the more general problem of weighted heavy-hitters, enabling new use cases, not supported by Prio or Poplar. In addition, Mastic allows grouping general-purpose metrics by user attributes, such as their geographic location or browser version, without sacrificing privacy or incurring high-performance costs, which is a major improvement over Prio. We demonstrate Mastic's benefits with two real-world applications, private network error logging and browser telemetry, and compare our protocol with Prio and Poplar on a wide area network. Overall, we report over one order of magnitude performance improvement over Poplar for heavy hitters and $1.5-2\times$ improvement over Prio for attribute-based metrics.

Note: Our implementation of Mastic is open-source:

Available format(s)
Cryptographic protocols
Publication info
Function secret sharinghistogramsheavy hittersprivacy-enhancing technologiessecure multiparty computation
Contact author(s)
dimitris @ nillion com
cpatton @ cloudflare com
hannahedavis @ protonmail com
pratik93 @ bu edu
tsoutsos @ udel edu
2024-02-16: approved
2024-02-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dimitris Mouris and Christopher Patton and Hannah Davis and Pratik Sarkar and Nektarios Georgios Tsoutsos},
      title = {Mastic: Private Weighted Heavy-Hitters and Attribute-Based Metrics},
      howpublished = {Cryptology ePrint Archive, Paper 2024/221},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.