In information-theoretic private information retrieval (PIR), a client wants to retrieve one desired file out of
Mfiles, stored across
Nservers, while keeping the index of the desired file private from each
T-sized subset of servers. A PIR protocol must ideally maximize the rate, which is the ratio of the file size to the total quantum of the download from the servers, while ensuring such privacy. In Weak-PIR (WPIR), the criterion of perfect information-theoretic privacy is relaxed. This enables higher rates to be achieved, while some information about the desired file index leaks to the servers. This leakage is captured by various known privacy metrics. By leveraging the well-established capacity-achieving schemes of Sun and Jafar under non-colluding (
T=1) and colluding (
1<T≤N) scenarios, we present WPIR protocols for these scenarios. We also present a new WPIR scheme for the MDS scenario, by building upon the scheme by Banawan and Ulukus for this scenario. We present corresponding explicit rate-privacy trade-offs for these setups, under the mutual-information and the maximal leakage privacy metrics. In the collusion-free setup, our presented rateprivacy trade-off under maximal leakage matches that of the previous state of the art. With respect to the MDS scenario under the maximal leakage metric, we compare with the non-explicit trade-off in the literature, and show that our scheme performs better for some numerical examples. For the
T-collusion setup (under both privacy metrics) and for the MDS setup under the mutual information metric, our rate-privacy trade-offs are the first in the literature, to the best of our knowledge.
Abstract Private information retrieval (PIR) is one of the promising techniques to preserve user privacy in the presence of trusted-but-curious servers. The information theoretically private query construction assures the highest user privacy over curious and unbounded computation servers. Therefore, the need for information-theoretic private retrieval was fulfilled by various schemes in a variety of PIR settings. But, there is a lack of efficient encryption switching scheme which supports efficient switching between information-theoretic to/from computationally bounded PIRs. We propose a combination of new bit connection methods called rail-shape and signal-shape and new quadratic residuosity assumption based family of trapdoor functions for generic single database private block retrieval (PBR). The main goal of this work is to show that the possibility of mapping from computationally bounded privacy to information theoretic privacy or vice-versa in a single database setting using newly constructed bit connection and trapdoor function combinations. Notably, the proposed schemes are single round, memoryless and plain database schemes (at their basic constructions).
In this paper, we investigate query processes and reconstruction functions for unconditionally secure 2-server 1-round binary private information retrieval (PIR) schemes. We begin by formulating a simplified model for PIR schemes which is equivalent to the usual model. We show that a query is equivalent to a boolean function of two variables, and we give a precise characterization of the boolean functions that can be used as "query pairs" to the two servers. We also consider several notions of "privacy" and we make a few remarks about the communication complexity of PIR schemes.