块设计在最优本地隐私分布估计中的必要性

摘要

本地差分隐私代表了在数据离开设备之前保护隐私的黄金标准，该模型下的分布估计已得到充分研究。最近，基于平衡不完全块设计构建的协议被证明能够实现该问题的最优误差。然而，其他构造是否也能达到最优仍属未知。我们通过证明任何达到最优误差的协议必须对应于某种平衡不完全块设计来解决这一问题。这一结果与先前工作相结合，完全刻画了该问题的最优协议集合。因此，仅基于对称平衡不完全块设计的协议才能同时实现最优误差和最优通信。

评论

这是被ITW 2025研讨会接受的一篇预印本论文。

主题

信息论（cs.IT）；密码学与安全（cs.CR）；数据结构与算法（cs.DS）

引用

arXiv:2508.05110 [cs.IT]
(或此版本的 arXiv:2508.05110v1 [cs.IT])
https://doi.org/10.48550/arXiv.2508.05110

提交历史

来自：Abigail Gentle [查看邮箱]
[v1] 2025年8月7日 星期四 07:44:04 UTC (81 KB)