Secure Private Information Retrieval from Colluding Databases with Eavesdroppers
Qiwen Wang, Mikael Skoglund · 2018
The problem of private information retrieval (PIR) is to retrieve one message out of K messages replicated at N databases, without revealing the identity of the desired message to the databases. We consider the problem of PIR with colluding databases and eavesdroppers, named ETPIR. Specifically, any T out of N databases may collude, that is, they may communicate their interactions with the user to guess the identity of the requested message. An eavesdropper is curious to know the content of the messages and can tap in on the incoming and outgoing transmissions of any E databases with the user. The databases share some common randomness unknown to the eavesdropper and the user, and use the common randomness to generate the answers, such that the eavesdropper can learn no information about the K messages. The capacity is defined as the maximum retrieval rate, i.e. the number of information bits of the desired message retrieved per downloaded bit. In our previous work [1], we found that when E ≥ T, the capacity equals 1-[E/N]. In this work, we focus on the case when E ≤ T. We find an outer bound (converse bound) and an inner bound (achievability) on the optimal achievable rate. The gap between the derived inner and outer bounds vanishes as the number of messages K tends to infinity.