Paper 2022/1561
Vogue: Faster Computation of Private Heavy Hitters
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2022-11-10: approved
- 2022-11-09: received
- See all versions
- Short URL
- https://ia.cr/2022/1561
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1561,
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{https://eprint.iacr.org/2022/1561}},
url = {https://eprint.iacr.org/2022/1561}
}
