标题： 增强的洗牌差分隐私协议用于大域分类和键值数据 显示英文标题

标题： Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data

摘要： 差分隐私（Differential Privacy）的洗牌协议通过引入一个随机洗牌数据的洗牌器，在分布式系统中提供高精度和隐私保护。 然而，大多数洗牌DP协议容易受到两种攻击：数据收集者和用户之间的共谋攻击以及数据中毒攻击。 最近的一项研究通过引入一种增强型洗牌DP协议来解决这个问题，其中用户不添加噪声，而洗牌器执行随机抽样和虚拟数据添加。 然而，它仅针对小域的类别数据频率估计，并由于通信和计算成本过高而无法应用于大域。 在本文中，我们通过引入一种名为FME（过滤-多重加密）的新型增强型洗牌DP协议来填补这一空白。 我们的FME协议使用哈希函数过滤掉不受欢迎的项目，然后对受欢迎的项目进行精确的频率计算。 为了在用户和洗牌器之间的一轮交互中完成此操作，我们的协议在使用多重加密的系统中仔细进行通信。 我们还应用我们的FME协议到更高级的KV（键值）统计估计中，并采用额外的技术来减少偏差。 对于类别数据和KV数据，我们证明了我们的协议提供计算DP、对上述两种攻击的高度鲁棒性、准确性以及效率。 我们通过与十二种现有协议的比较展示了我们方案的有效性。 显示英文摘要

摘要： 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.