Controlling data disclosure in computational PIR protocols

Private Information Retrieval (PIR) protocols allow users to learn data items stored at a server which is not fully trusted, without disclosing to the server the particular data element retrieved. Several PIR protocols have been proposed, which provide strong guarantees on user privacy. Nevertheless, in many application scenarios it is important to protect the database as well. In this paper, we investigate the amount of data disclosed by the the most prominent PIR protocols during a single run. We show that a malicious user can stage attacks that allow an excessive amount of data to be retrieved from the server. Furthermore, this vulnerability can be exploited even if the client follows the legitimate steps of the PIR protocol, hence the malicious request can not be detected and rejected by the server. We devise mechanisms that limit the PIR disclosure to a single data item