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

BSFuzzer: Context-Aware Semantic Fuzzing for BLE Logic Flaw Detection

Ting Yang (Xidian University and Kanazawa University), Yue Qin (Central University of Finance and Economics), Lan Zhang (Northern Arizona University), Zhiyuan Fu (Hainan University), Junfan Chen (Hainan University), Jice Wang (Hainan University), Shangru Zhao (University of Chinese Academy of Sciences), Qi Li (Tsinghua University), Ruidong Li (Kanazawa University), He Wang (Xidian University), Yuqing Zhang (University…

Read More

Anchors of Trust: A Usability Study on User Awareness,...

Xin Zhang (Fudan University), Xiaohan Zhang (Fudan University), Huijun Zhou (Fudan University), Bo Zhao (Fudan University)

Read More

Success Rates Doubled with Only One Character: Mask Password...

Yunkai Zou (Nankai University), Ding Wang (Nankai University), Fei Duan (Nankai University)

Read More