Two-Level Private Information Retrieval
share
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, where K_1 messages need to be retrieved privately against T_1 colluding servers, and all the messages need to be retrieved privately against T_2 colluding servers where T_2≤ T_1. We obtain a lower bound to the capacity by proposing two novel coding schemes, namely the non-uniform successive cancellation scheme and the non-uniform block cancellation 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.
READ FULL TEXT