Private Information Retrieval

Check our latest paper:

• ISIT 2025: Optimizing Leaky Private Information Retrieval Codes to Achieve O(log K) Leakage Ratio Exponent
• ISIT 2024: Weakly Private Information Retrieval from Heterogeneously Trusted Servers

Leaky Private Information Retrieval

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.

Heterogeneous Weakly Private Information Retrieval

Private information retrieval (PIR) systems were motivated by the necessity to safeguard user privacy during information retrieval. In the standard PIR framework, a user wishes to retrieve a desired message from N non-colluding servers efficiently, such that the identity of the desired message is not leaked in a significant manner. We study the problem of weakly PIR when there is heterogeneity in servers’ trustfulness, i.e. some servers can be more trustworthy than others, under the maximal leakage (Max-L) metric and mutual information (MI) metric. A code construction is proposed for this setting and optimized the probability distribution for this construction.