Private Information Retrieval

Check our latest papers:

• Allerton 2025: Leaky Multi-Message Private Information Retrieval with Differential Privacy Guarantees
• ISIT 2025: Optimizing Leaky Private Information Retrieval Codes to Achieve O(log K) Leakage Ratio Exponent
• IEEE Transactions on Information Theory: Weakly Private Information Retrieval from Heterogeneously Trusted Servers

Leaky Multi-Message Private Information Retrieval with Differential Privacy Guarantees

Abstract The Private Information Retrieval (PIR) problem aims to enable users to privately access data stored on remote servers. Recently, there has been a growing interest in leaky PIR schemes, which enable users to trade off higher rates for a controlled leakage of information about the identities of the downloaded messages. Motivated by applications that require the simultaneous retrieval of multiple data items, we focus on the ϵ-differential privacy framework for Leaky Multi-message PIR (LMPIR). Our paper complements the existing work on multi-message PIR, which has so far focused on perfect privacy. Our main contribution is the construction of an LMPIR scheme based on a randomized query and answer generation mechanism that carefully balances the tradeoff between privacy and efficiency, and is tailored to maximize the retrieval rate under the given privacy parameter \(\epsilon\). Our scheme requires a small degree of subpacketization L, which grows at most linearly with the number of servers. We also outline an information-theoretic upper bound on the maximum achievable rate for LMPIR. Our numerical results indicate that our scheme achieves a better privacy-efficiency tradeoff compared to alternatives, such as repeated application of leaky single-message PIR schemes.

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.