Two-Level Private Information Retrieval
Ruida Zhou, Chao Tian, Hua Sun, James S. Plank · IEEE Journal on Selected Areas in Information Theory · 2022
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, T_{1}~:~K_{1}, T_{2}~:~K_{2})$two-level PIR system with a total of$K_{2}$messages in the system, where$T_{1}\geq T_{2}$and$K_{1}\leq K_{2}$. Any one of the$K_{1}$messages needs to be retrieved privately against$T_{1}$colluding servers, and any one of the full set of$K_{2}$messages needs to be retrieved privately against$T_{2}$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$T_{1}=T_{2}$. Lastly, we show that the upper bound is in general not tight by providing a stronger bound for a special setting.