Two-Level Private Information Retrieval

• Published in: IEEE journal on selected areas in information theory 2022-06, Vol.3 (2), p.337-349
• Main Authors: Zhou, Ruida, Tian, Chao, Sun, Hua, Plank, James S.
• Format: Article
• Language: English
• Subjects: Codes; Colluding; Information retrieval; Lower bounds; Messages; Privacy; Servers; Symbols; Upper bound; Upper bounds; Videos
• ISSN: 2641-8770; 2641-8770
• DOI: 10.1109/JSAIT.2022.3181216

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.