Two-Level Private Information Retrieval

Ruida Zhou, Texas A&M University, Chao Tian, Texas A&M University, Hua Sun, University of North Texas, James S. Plank, EECS Department, University of Tennessee.

IEEE Journal on Selected Areas in Information Theory, 3(2), June, 2022.

Link from the IEEE to the paper.


In the conventional robust T-colluding private information retrieval (PIR) system, the user needs to retrieve one of the possible messages while keeping the identity of the requested message private from any T colluding servers. Motivated by the possible heterogeneous privacy requirements for different messages, we consider the (N,T1 : K1,T2 : K2) two-level PIR system with a total of K2 messages in the system, where T1≥T2 and K1≤K2 . Any one of the K1 messages needs to be retrieved privately against T1 colluding servers, and any one of the full set of K2 messages needs to be retrieved privately against T2 colluding servers. We obtain a lower bound to the capacity by proposing two novel coding schemes, namely the non-uniform successive cancelation scheme and the non-uniform block cancelation scheme. A capacity upper bound is also derived. The gap between the upper bound and the lower bounds is analyzed, and shown to vanish when T1=T2 . Lastly, we show that the upper bound is in general not tight by providing a stronger bound for a special setting.

Citation Information