Weakly Private Information Retrieval Under the Maximal Leakage Metric

In the canonical private information retrieval (PIR) problem, a user retrieves a message from a set of databases without allowing any individual database to obtain any knowledge regarding the identity of the requested message. This perfect privacy requirement may be too stringent in many cases, and the user may only wish to control the amount of the privacy leakage to below a given level, and in return, can retrieve the message at a lower communication cost. In this work, we study the tradeoff between the download cost and the amount of privacy leakage under the maximal leakage metric. A new scheme is proposed by allowing a more flexible query structure and probability distributions in a code previously proposed by Tian et al., which utilized a fixed query set and a uniform distribution. It is shown that the optimal probability distribution in the proposed scheme has a particularly simple structure, which leads to a closed form achievability bound for the optimal tradeoff between the download cost and the privacy leakage. The proposed scheme includes several known schemes, such as those proposed by Lin et al., by Samy et al., and by Jia, as special cases.