Takao Murakami (ISM/AIST/RIKEN AIP), Yuichi Sei (UEC), Reo Eriguchi (AIST)

Shuffle DP (Differential Privacy) protocols provide high accuracy and privacy by introducing a shuffler who randomly shuffles data in a distributed system. However, most shuffle DP protocols are vulnerable to two attacks: collusion attacks by the data collector and users and data poisoning attacks. A recent study addresses this issue by introducing an augmented shuffle DP protocol, where users do not add noise and the shuffler performs random sampling and dummy data addition. However, it focuses on frequency estimation over categorical data with a small domain and cannot be applied to a large domain due to prohibitively high communication and computational costs.

In this paper, we fill this gap by introducing a novel augmented shuffle DP protocol called the FME (Filtering-with-Multiple-Encryption) protocol. Our FME protocol uses a hash function to filter out unpopular items and then accurately calculates frequencies for popular items. To perform this within one round of interaction between users and the shuffler, our protocol carefully communicates within a system using multiple encryption. We also apply our FME protocol to more advanced KV (Key-Value) statistics estimation with an additional technique to reduce bias. For both categorical and KV data, we prove that our protocol provides computational DP, high robustness to the above two attacks, accuracy, and efficiency. We show the effectiveness of our proposals through comparisons with twelve existing protocols.

View More Papers

ANONYCALL: Enabling Native Private Calling in Mobile Networks

Hexuan Yu (Virginia Polytechnic Institute and State University), Chaoyu Zhang (Virginia Polytechnic Institute and State University), Yang Xiao (University of Kentucky), Angelos D. Keromytis (Georgia Institute of Technology), Y. Thomas Hou (Virginia Polytechnic Institute and State University), Wenjing Lou (Virginia Polytechnic Institute and State University)

Read More

SoK: Analysis of Accelerator TEE Designs

Chenxu Wang (Research Institute of Trustworthy Autonomous Systems, Southern University of Science and Technology, China, Department of Computer Science and Engineering, Southern University of Science and Technology, China and Department of Computing, The Hong Kong Polytechnic University, China), Junjie Huang (Department of Computer Science and Engineering, Southern University of Science and Technology, China), Yujun Liang…

Read More