Weakly Private Information Retrieval from Heterogeneously Trusted Servers
Yu-Shin Huang, Wenyuan Zhao, Texas A&M University, United States; Ruida Zhou, University of California, Los Angeles, United States; Chao Tian, Texas A&M University, United States
Session:
Private Information Retrieval 2
Track:
16: Private Information Retrieval
Location:
Lamda
Presentation Time:
Thu, 11 Jul, 16:25 - 16:45
Session Chair:
Viveck Cadambe, Pennsylvania State University
Abstract
THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. We study the problem of weakly private information retrieval (PIR) when there is heterogeneity in servers' trustfulness under the maximal leakage (Max-L) metric. 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; however, some servers can be more trustworthy than others. We propose a code construction for this setting and optimize the probability distribution for this construction. It is shown that the optimal probability allocation for the proposed scheme essentially separates the delivery patterns into two parts: a completely private part that has the same download overhead as the capacity-achieving PIR code, and a non-private part that allows complete privacy leakage but has no download overhead by downloading only from the most trustful server. The optimal solution is established through a sophisticated analysis of the underlying convex optimization problem, and a reduction between the homogeneous setting and the heterogeneous setting.