Paper 2022/1561

Vogue: Faster Computation of Private Heavy Hitters

Pranav Jangir, New York University
Nishat Koti, Indian Institute of Science Bangalore
Varsha Bhat Kukkala, Indian Institute of Science Bangalore
Arpita Patra, Indian Institute of Science Bangalore
Bhavish Raj Gopal, Indian Institute of Science Bangalore
Somya Sangal

Consider the problem of securely identifying τ -heavy hitters, where given a set of client inputs, the goal is to identify those inputs which are held by at least τ clients in a privacy-preserving manner. Towards this, we design a novel system Vogue, whose key highlight in comparison to prior works, is that it ensures complete privacy and does not leak any information other than the heavy hitters. In doing so, Vogue aims to achieve as efficient a solution as possible. To showcase these efficiency improvements, we benchmark our solution and observe that it requires around 14 minutes to compute the heavy hitters for τ = 900 on 256-bit inputs when considering 400K clients. This is in contrast to the state of the art solution that requires over an hour for the same. In addition to the static input setting described above, Vogue also accounts for streaming inputs and provides a protocol that outperforms the state-of-the-art therein. The efficiency improvements witnessed while computing heavy hitters in both, the static and streaming input settings, are attributed to our new secure stable compaction protocol, whose round complexity is independent of the size of the input array to be compacted

Note: This is the full version of the poster accepted to CCS'22.

Available format(s)
Cryptographic protocols
Publication info
private heavy hitters secure stable compaction secure multiparty computation
Contact author(s)
jangir pranav @ gmail com
kotis @ iisc ac in
varshak @ iisc ac in
arpita @ iisc ac in
bhavishraj @ iisc ac in
somyasangal1996 @ gmail com
2022-11-10: approved
2022-11-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pranav Jangir and Nishat Koti and Varsha Bhat Kukkala and Arpita Patra and Bhavish Raj Gopal and Somya Sangal},
      title = {Vogue: Faster Computation of Private Heavy Hitters},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1561},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.