Bo Jiang (TikTok Inc.), Wanrong Zhang (TikTok Inc.), Donghang Lu (TikTok Inc.), Jian Du (TikTok Inc.), Qiang Yan (TikTok Inc.)

Local Differential Privacy (LDP) protocols enable the collection of randomized client messages for data analysis, without the necessity of a trusted data curator. Such protocols have been successfully deployed in real-world scenarios by major tech companies like Google, Apple, and Microsoft. In this paper, we propose a Generalized Count Mean Sketch (GCMS) protocol that captures many existing frequency estimation protocols. Our method significantly improves the three-way trade-offs between communication, privacy, and accuracy. We also introduce a general utility analysis framework that enables optimizing parameter designs. Based on that, we propose an Optimal Count Mean Sketch (OCMS) framework that minimizes the variance for collecting items with targeted frequencies. Moreover, we present a novel protocol for collecting data within unknown domain, as our frequency estimation protocols only work effectively with known data domain. Leveraging the stability-based histogram technique alongside the Encryption-Shuffling-Analysis (ESA) framework, our approach employs an auxiliary server to construct histograms without accessing original data messages. This protocol achieves accuracy akin to the central DP model while offering local-like privacy guarantees and substantially lowering computational costs.

View More Papers

Cryptobazaar: Private Sealed-bid Auctions at Scale

Andrija Novakovic (Bain Capital Crypto), Alireza Kavousi (University College London), Kobi Gurkan (Bain Capital Crypto), Philipp Jovanovic (University College London)

Read More

From Reports to Insights: Challenges and Opportunities in Citizen-Driven...

Daan Vansteenhuyse (DistriNet, KU Leuven), Hadji Musaev (DistriNet, KU Leuven), Lieven Desmet (DistriNet, KU Leuven)

Read More

Demystifying the Access Control Mechanism of ESXi VMKernel

Yue Liu (Southeast University), Zexiang Zhang (National University of Defense Technology), Jiaxun Zhu (Zhejiang University), Hao Zheng (Independent Researcher), Jiaqing Huang (Independent Researcher), Wenbo Shen (Zhejiang University), Gaoning Pan (Hangzhou Dianzi University), Yuliang Lu (National University of Defense Technology), Min Zhang (National University of Defense Technology), Zulie Pan (National University of Defense Technology), Guang Cheng…

Read More