In information-theoretic private information retrieval (PIR), a client wants to retrieve one desired file out of $M$ files, stored across $N$ servers, 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 \leq 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.In information-theoretic private information retrieval (PIR), a client wants to retrieve one desired file out of$M$files, stored across$N$servers, 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 \leq 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.

arXiv:2501.11505IEEE International Symposium on Information Theory (ISIT)Jun 22, 20252 citations

On the Security of Doubly Efficient PIR.

Elette Boyle, Justin Holmgren, Fermi Ma +1 more

Jan 1, 20211 citation

A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol.

Carlos Aguilar Melchor, Philippe Gaborit

A PIR scheme is a scheme that allows an user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, using an NTRU-like approach, in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has worse communication performance than other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.A PIR scheme is a scheme that allows an user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, using an NTRU-like approach, in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has worse communication performance than other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.

Jan 1, 200798 citations

a Physics of Computation.

Wakefield Scott Stornetta

Jan 1, 19890 citations

On No Communication Theorems

Omer Dickstein

Dec 1, 20140 citations

Private Sum Computation: Trade-Offs Between Communication, Randomness, and Privacy

Rémi A. Chou, Jörg Kliewer, Aylin Yener

IEEE Transactions on Information TheoryJan 22, 20261 citation

In information-theoretic private information retrieval (PIR), a client wants to retrieve one desired file out of

M

files, stored across

N

servers, 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 \leq 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.