Paper 2026/747

MDSS-STAR: Private Heavy-Hitters through Multi-Dealer Secret Sharing

Aditya Hegde, Johns Hopkins University

Brennon Brimhall, Johns Hopkins University

Gabrielle Beck, French National Centre for Scientific Research

Matthew Green, Johns Hopkins University

Abstract

We propose a new private telemetry system for computing t-heavy hitters in the STAR (Davidson et al., CCS 2022) and POPSTAR (Li et al., USENIX 2024) model. In this setting, each client generates a report with the assistance of a lightweight Randomness Server and submits it to a central Aggregation Server, which can then locally compute only the heavy hitters. As compared to STAR and POPSTAR---which reveal either the full (pseudonymized) frequency histogram or a complex function of it---our protocol reduces leakage: the Aggregation Server learns non-heavy-hitter values only if their frequency exceeds a well-defined threshold. Additionally, while STAR and POPSTAR are insecure in the face of an Aggregation Server that colludes with clients, our protocol provides optimal security against such a colluding server. To achieve these privacy guarantees, our protocol efficiently adapts multi-dealer secret sharing (Eldridge et al., USENIX 2024) to the STAR/POPSTAR model and introduces a novel oblivious secret-share sampling protocol to ensure security against a colluding Aggregation Server. We implement and benchmark the performance of our protocol and find that it is practical for a number of use cases. Moreover, we show that it supports a tunable three-way tradeoff between correctness, efficiency and privacy.

@misc{cryptoeprint:2026/747,
      author = {Harry Eldridge and Aditya Hegde and Brennon Brimhall and Gabrielle Beck and Matthew Green},
      title = {{MDSS}-{STAR}: Private Heavy-Hitters through Multi-Dealer Secret Sharing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/747},
      year = {2026},
      url = {https://eprint.iacr.org/2026/747}
}