On the Leaky Private Information Retrieval with Side Information

Abstract

This paper investigates the problem of Leaky Private Information Retrieval with Side Information (L-PIR-SI), providing a fundamental characterization of the trade-off among leaky privacy, side information, and download cost. We propose a unified probabilistic framework to design L-PIR-SI schemes under $\epsilon$-differential privacy variants of both $W$-privacy and $(W,S)$-privacy. Explicit upper bounds on the download cost are derived, which strictly generalize existing results: our bounds recover the capacity of perfect PIR-SI as $\epsilon \to 0$, and reduce to the known $\epsilon$-leaky PIR rate in the absence of side information. Furthermore, we conduct a refined analysis of the privacy--utility trade-off at the scaling-law level, demonstrating that the leakage ratio exponent scales as $\mathcal{O}(\log \frac{K}{M+1})$ under leaky $W$-privacy, and as $\mathcal{O}(\log K)$ under leaky $(W,S)$-privacy in the minimal non-trivial setting $M=1$, where $K$ and $M$ denote the number of messages and the side information size, respectively.

24 pages