Secure symmetric private information retrieval from colluding databases with adversaries
Qiwen Wang, Mikael Skoglund · 2017
The problem of symmetric private information retrieval (SPIR) from replicated databases with colluding servers and adversaries is studied. Specifically, the database comprises K files, which are replicatively stored among N servers. A user wants to retrieve one file from the database by communicating with the N servers, without revealing the identity of the desired file to any server. Furthermore, the user shall learn nothing about the other K - 1 files in the database. Any T out of N servers may collude, that is, they may communicate their interactions with the user to guess the identity of the requested file. An adversary in the system can tap in on or even try to corrupt the communication. Three types of adversaries are considered: a Byzantine adversary who can overwrite the transmission of any B servers to the user; a passive eavesdropper who can tap in on the incoming and outgoing transmissions of any E servers; and a combination of both - an adversary who can tap in on a set of any E nodes, and overwrite the transmission of a set of any B nodes. The problems of SPIR with colluding servers and the three types of adversaries are named T-BSPIR, T-ESPIR and T-BESPIR respectively. The capacity of the problem is defined as the maximum number of information bits of the desired file retrieved per downloaded bit. We show that the information-theoretical capacity of the T-BSPIR problem equals 1 - 2B+T/N, if the servers share common randomness (unavailable at the user) with amount at least 2B+T/N-2B-T times the file size. Otherwise, the capacity equals zero. The information-theoretical capacity of the T-ESPIR problem is proved to equal 1 - max(T, E)/N if the servers share common randomness with amount at least max(T, E)/N - max(T, E) times the file size. Finally, for the problem of T-BESPIR, the capacity is proved to be 1 - 2B+max(T, E)/N where the common randomness shared by the servers should be at least 2B+max(T, E)/N-2B-max(T, E) times the file size. The results resemble those of secure network coding problems with adversaries and eavesdroppers.