TH4.R9.2

A Capacity Result on Weakly-Private Information Retrieval

song chen, Haobo Jia, Zhuqing Jia, Beijing University of Posts and Telecommunications, China

Session:
Private Information Retrieval 2

Track:
16: Private Information Retrieval

Location:
Lamda

Presentation Time:
Thu, 11 Jul, 16:45 - 17:05

Session Chair:
Viveck Cadambe, Pennsylvania State University
Abstract
The problem of weakly-private information retrieval(WPIR) is to allow the user to retrieve one out of K messages from a set of N distributed servers while guaranteeing that the information about the identity of the index of the desired message is leaked to the servers in a controlled manner, i.e., the privacy level cannot be less than a prescribed threshold as measured by a privacy metric. In this work, we consider the converse-induced privacy metric (CIPM) for WPIR proposed by Jia and fully settle the capacity, i.e., the supremum of the average number of desired message symbols retrieved per downloaded symbol, for the arbitrary number of messages K and the number of servers N . Our achievability scheme makes use of a symmetrized (with respect to the servers) version of the PIR codes due to Tian et al. by carefully designing the query distributions. It turns out that the optimal trade-off between the privacy level and the reciprocal of the retrieval rate in terms of the CIPM metric is linear for non-degenerate settings.
Resources