优化检索模式概率分布，实现对数级隐私泄露率，显著提升私密信息检索效率。
Optimizing Leaky Private Information Retrieval Codes to Achieve ${O}(\log K)$ Leakage Ratio Exponent
- 联合优化所有检索模式的概率分配，构建分层概率结构。
- 隐私泄露率指数降至 O(log K)，相较之前 Θ(K) 显著降低。
- 适用于高消息数场景下的高效私密检索系统设计。
本文研究泄漏型私密信息检索（L-PIR）问题，其中隐私泄露量由纯差分隐私参数衡量，即泄露比指数。与此前仅调整低开销检索模式概率的方案不同，本文联合优化所有检索模式的概率分配。结果表明最优概率分布具有复杂分层结构：汉明权重较低的随机密钥对应检索模式应分配更高概率。新方案在固定下载成本 D 和服务器数 N 条件下，实现 O(log K) 的泄露比指数，优于先前方案的 Θ(K)，其中 K 为消息总数。
原文摘要 · Abstract (English)
We study the problem of leaky private information retrieval (L-PIR), where the amount of privacy leakage is measured by the pure differential privacy parameter, referred to as the leakage ratio exponent. Unlike the previous L-PIR scheme proposed by Samy et al., which only adjusted the probability allocation to the clean (low-cost) retrieval pattern, we optimize the probabilities assigned to all the retrieval patterns jointly. It is demonstrated that the optimal retrieval pattern probability distribution is quite sophisticated and has a layered structure: the retrieval patterns associated with the random key values of lower Hamming weights should be assigned higher probabilities. This new scheme provides a significant improvement, leading to an ${O}(\log K)$ leakage ratio exponent with fixed download cost $D$ and number of servers $N$, in contrast to the previous art that only achieves a $Θ(K)$ exponent, where $K$ is the number of messages.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。