用中国剩余定理降低隐私计算通信成本，同时提升抗攻击能力。
Private Frequency Estimation Via Residue Number Systems
- 用户用互质模数编码数据，仅上传一个扰动余数和索引。
- 通信量从约 ω log₂(k/ω) 降至 ⌈log₂ℓ⌉ + ⌈log₂mⱼ⌉ 位，实测加速解码。
- 在相同隐私下精度媲美先进方法，且更难被逆向攻击，适合高敏感数据场景。
我们提出 extsf{ModularSubsetSelection}（MSS），一种用于本地差分隐私（LDP）频率估计的新算法。给定大小为 $k$ 的全域和 $n$ 个用户，我们的 $\varepsilon$-LDP 机制通过在 $\ extit{ extellip}$ 个两两互质的模数 $m_0, \ldots, m_{\ell-1}$ 上使用中国剩余定理（RNS）编码每个输入，并报告一个随机选择的索引 $j \in [\ell]$ 及对应的扰动余数，采用统计最优的 extsf{SubsetSelection}（SS）机制。该设计将用户通信成本从标准 SS 所需的 $Θ(ω\log_2(k/ω))$ 位降低至 $⌈\log_2 ℓ⌉ + ⌈\log_2 m_j⌉$ 位，其中 $m_j < k$。服务端解码时间复杂度为 $Θ(n + r k ℓ)$，其中 $r$ 为 LSMR（Fong and Saunders 2011）迭代次数。实践中，若模数条件良好（即常数 $r$ 且 $\ell = Θ(\log k)$），则解码时间为 $Θ(n + k \log k)$。我们证明，MSS 在最坏情况下的均方误差（MSE）与当前最优协议如 SS 和 extsf{ProjectiveGeometryResponse}（PGR）（Feldman et al. 2022）相差常数因子，同时避免了 PGR 所需的代数基础和动态规划解码器。实验表明，在真实 $(k, \varepsilon)$ 设置下，MSS 的估计精度与 SS、PGR 及 extsf{RAPPOR}（Erlingsson, Pihur, and Korolova 2014）相当，且解码速度优于 PGR，用户消息长度短于 SS。最后，通过从多个模数中采样并仅报告单一扰动余数，MSS 在所有评估的 LDP 协议中实现了最低的重构攻击成功率。
原文摘要 · Abstract (English)
We present \textsf{ModularSubsetSelection} (MSS), a new algorithm for locally differentially private (LDP) frequency estimation. Given a universe of size $k$ and $n$ users, our $\varepsilon$-LDP mechanism encodes each input via a Residue Number System (RNS) over $\ell$ pairwise-coprime moduli $m_0, \ldots, m_{\ell-1}$, and reports a randomly chosen index $j \in [\ell]$ along with the perturbed residue using the statistically optimal \textsf{SubsetSelection} (SS) (Wang et al. 2016). This design reduces the user communication cost from $Θ\bigl(ω\log_2(k/ω)\bigr)$ bits required by standard SS (with $ω\approx k/(e^\varepsilon+1)$) down to $\lceil \log_2 \ell \rceil + \lceil \log_2 m_j \rceil$ bits, where $m_j < k$. Server-side decoding runs in $Θ(n + r k \ell)$ time, where $r$ is the number of LSMR (Fong and Saunders 2011) iterations. In practice, with well-conditioned moduli (\textit{i.e.}, constant $r$ and $\ell = Θ(\log k)$), this becomes $Θ(n + k \log k)$. We prove that MSS achieves worst-case MSE within a constant factor of state-of-the-art protocols such as SS and \textsf{ProjectiveGeometryResponse} (PGR) (Feldman et al. 2022) while avoiding the algebraic prerequisites and dynamic-programming decoder required by PGR. Empirically, MSS matches the estimation accuracy of SS, PGR, and \textsf{RAPPOR} (Erlingsson, Pihur, and Korolova 2014) across realistic $(k, \varepsilon)$ settings, while offering faster decoding than PGR and shorter user messages than SS. Lastly, by sampling from multiple moduli and reporting only a single perturbed residue, MSS achieves the lowest reconstruction-attack success rate among all evaluated LDP protocols.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。