通过置换矩阵隐藏在Birkhoff多面体中，实现多方比特求和的组合隐私保护。
Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes
- 将私有比特编码为置换矩阵，利用Birkhoff多面体结构隐藏信息。
- 压缩变体在中等信噪比下可实现非平凡的差分隐私，且通信开销为O(k)。
- 首次揭示了高安全性与强隐私保护之间的根本矛盾，适合密码学与隐私计算研究者。
我们提出PolyVeil协议，用于k个客户端间的私有布尔求和。该协议将私有比特编码为Birkhoff多面体中的置换矩阵。两层架构确保服务器具备完美模拟安全（统计距离为零），而独立聚合器则面临#P难的似然推断问题，涉及行列式与混合判别式。两种变体（全量与压缩）区别在于聚合器所见信息：全量变体中其观察到每个客户端的双随机矩阵，此时对数Lipschitz常数随$ n^4 K_t $增长，仅当私有信号不可检测时差分隐私保证才非平凡；压缩变体中聚合器仅见单个标量，一维密度比分析表明在中等信噪比下可得非平凡ε值，最优干扰数需权衡中心极限定理精度与噪声集中度。这揭示了一个基本张力：#P难性要求保留完整矩阵视图（显现Birkhoff结构），而非平凡差分隐私又要求标量视图（低维度）。两者能否同时在一变体中成立仍待解决。协议无需公钥基础设施，通信复杂度为O(k)，并输出精确聚合结果。
原文摘要 · Abstract (English)
We introduce PolyVeil, a protocol for private Boolean summation across $k$ clients that encodes private bits as permutation matrices in the Birkhoff polytope. A two-layer architecture gives the server perfect simulation-based security (statistical distance zero) while a separate aggregator faces \#P-hard likelihood inference via the permanent and mixed discriminant. Two variants (full and compressed) differ in what the aggregator observes. We develop a finite-sample $(\varepsilon,δ)$-DP analysis with explicit constants. In the full variant, where the aggregator sees a doubly stochastic matrix per client, the log-Lipschitz constant grows as $n^4 K_t$ and a signal-to-noise analysis shows the DP guarantee is non-vacuous only when the private signal is undetectable. In the compressed variant, where the aggregator sees a single scalar, the univariate density ratio yields non-vacuous $\varepsilon$ at moderate SNR, with the optimal decoy count balancing CLT accuracy against noise concentration. This exposes a fundamental tension. \#P-hardness requires the full matrix view (Birkhoff structure visible), while non-vacuous DP requires the scalar view (low dimensionality). Whether both hold simultaneously in one variant remains open. The protocol needs no PKI, has $O(k)$ communication, and outputs exact aggregates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。