Optimizing Leaky Private Information Retrieval Codes to Achieve O( K) Leakage Ratio Exponent

Abstract

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( 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.

Tasks

Reproductions