Report
Optimizing Leaky Private Information Retrieval Codes to Achieve ${O}(\log K)$ Leakage Ratio Exponent
| العنوان: | Optimizing Leaky Private Information Retrieval Codes to Achieve ${O}(\log K)$ Leakage Ratio Exponent |
|---|---|
| المؤلفون: | Zhao, Wenyuan, Huang, Yu-Shin, Tian, Chao, Sprintson, Alex |
| سنة النشر: | 2025 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Information Retrieval, Computer Science - Information Theory |
| الوصف: | 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 $\Theta(K)$ exponent, where $K$ is the number of messages. Comment: Long version of the paper submitted to ISIT 2025. 8 pages, 2 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2501.12310 |
| رقم الانضمام: | edsarx.2501.12310 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |