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 Quantum Advantage in Information Theoretic Single-Server PIR

Dorit Aharonov, Zvika Brakerski, Kai-Min Chung +3 more

Lecture notes in computer scienceJan 1, 201918 citations

Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective

Zhusheng Wang, Karim Banawan, Şennur Ulukuş

We study the problem of private set intersection (PSI). In this problem, there are two entities $E_{i}$ , for $i=1, 2$ , each storing a set $\mathcal {P}_{i}$ , whose elements are picked from a finite set $\mathbb {S}_{K}$ , on $N_{i}$ replicated and non-colluding databases. It is required to determine the set intersection ${\mathcal {P}}_{1} \cap {\mathcal {P}} _{2}$ without leaking any information about the remaining elements to the other entity, and to do this with the least amount of downloaded bits. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem with certain added restrictions. Next, as a stand-alone result, we derive the information-theoretic sum capacity of MM-SPIR, $C_{MM-SPIR}$ . We show that with $K$ messages, $N$ databases, and a given size of the desired message set $P$ , the exact capacity of MM-SPIR is $C_{MM-SPIR} = 1 - \frac {1}{N}$ when $P \leq K-1$ , provided that the entropy of the common randomness $S$ satisfies $H(S) \geq \frac {P}{N-1}$ per desired symbol. When $P = K$ , the MM-SPIR capacity is trivially 1 without the need for any common randomness $S$ . This result implies that there is no gain for MM-SPIR over successive single-message SPIR (SM-SPIR). For the MM-SPIR problem, we present a novel capacity-achieving scheme which builds seamlessly over the near-optimal scheme of Banawan-Ulukus originally proposed for the multi-message PIR (MM-PIR) problem without any database privacy constraints. Surprisingly, our scheme here is exactly optimal for the MM-SPIR problem for any $P$ , in contrast to the scheme for the MM-PIR problem, which was proved only to be near-optimal. Our scheme is an alternative to the successive usage of the SM-SPIR scheme of Sun-Jafar. Based on this capacity result for the MM-SPIR problem, and after addressing the added requirements in its conversion to the PSI problem, we show that the optimal download cost for the PSI problem is given by $\min \left \{{\left \lceil{ \frac {P_{1} N_{2}}{N_{2}-1}}\right \rceil, \left \lceil{ \frac {P_{2} N_{1}}{N_{1}-1}}\right \rceil }\right \}$ , where $P_{i}$ is the cardinality of set ${\mathcal {P}}_{i}$ .We study the problem of private set intersection (PSI). In this problem, there are two entities$E_{i}$, for$i=1, 2$, each storing a set$\mathcal {P}_{i}$, whose elements are picked from a finite set$\mathbb {S}_{K}$, on$N_{i}$replicated and non-colluding databases. It is required to determine the set intersection${\mathcal {P}}_{1} \cap {\mathcal {P}} _{2}$without leaking any information about the remaining elements to the other entity, and to do this with the least amount of downloaded bits. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem with certain added restrictions. Next, as a stand-alone result, we derive the information-theoretic sum capacity of MM-SPIR,$C_{MM-SPIR}$. We show that with$K$messages,$N$databases, and a given size of the desired message set$P$, the exact capacity of MM-SPIR is$C_{MM-SPIR} = 1 - \frac {1}{N}$when$P \leq K-1$, provided that the entropy of the common randomness$S$satisfies$H(S) \geq \frac {P}{N-1}$per desired symbol. When$P = K$, the MM-SPIR capacity is trivially 1 without the need for any common randomness$S$. This result implies that there is no gain for MM-SPIR over successive single-message SPIR (SM-SPIR). For the MM-SPIR problem, we present a novel capacity-achieving scheme which builds seamlessly over the near-optimal scheme of Banawan-Ulukus originally proposed for the multi-message PIR (MM-PIR) problem without any database privacy constraints. Surprisingly, our scheme here is exactly optimal for the MM-SPIR problem for any$P$, in contrast to the scheme for the MM-PIR problem, which was proved only to be near-optimal. Our scheme is an alternative to the successive usage of the SM-SPIR scheme of Sun-Jafar. Based on this capacity result for the MM-SPIR problem, and after addressing the added requirements in its conversion to the PSI problem, we show that the optimal download cost for the PSI problem is given by$\min \left \{{\left \lceil{ \frac {P_{1} N_{2}}{N_{2}-1}}\right \rceil, \left \lceil{ \frac {P_{2} N_{1}}{N_{1}-1}}\right \rceil }\right \}$, where$P_{i}$is the cardinality of set${\mathcal {P}}_{i}$.

arXiv:1912.13501IEEE Transactions on Information TheoryNov 2, 202156 citations

A Framework of Secure Source Coding using Mutual Information Security Criterion: Universal Coding, Strong Converse Theorem

Yasutada Oohama, Bagus Santoso

In this paper, we propose a framework of source encryption, where cryptographic processing is applied to a prescribed fixed length source code. The proposed source encryption framework is based on the secure communication framework of the Shannon cipher system. In the proposed framework, we use the mutual information as a measure of information leakage to an adversary. For the proposed framework, we explicitly establish the necessary and sufficient condition for reliable and secure communication under the condition that error probability and information leakage, respectively, are upper bounded by prescribed constants $ε\in (0,1)$ and $δ\in (0,\infty)$ . We also show that the obtained necessary and sufficient condition does not depend on the constants $ε\in (0,1)$ and $δ\in (0,\infty)$ , demonstrating that we have the strong converse theorem for the proposed framework of source encryption. We further prove the existence of encryption/decryption schemes, which are universal in the sense that they work effectively for any distributions of the plain text and those of the key used for the encryption.In this paper, we propose a framework of source encryption, where cryptographic processing is applied to a prescribed fixed length source code. The proposed source encryption framework is based on the secure communication framework of the Shannon cipher system. In the proposed framework, we use the mutual information as a measure of information leakage to an adversary. For the proposed framework, we explicitly establish the necessary and sufficient condition for reliable and secure communication under the condition that error probability and information leakage, respectively, are upper bounded by prescribed constants $ε\in (0,1)$ and $δ\in (0,\infty)$. We also show that the obtained necessary and sufficient condition does not depend on the constants $ε\in (0,1)$ and $δ\in (0,\infty)$, demonstrating that we have the strong converse theorem for the proposed framework of source encryption. We further prove the existence of encryption/decryption schemes, which are universal in the sense that they work effectively for any distributions of the plain text and those of the key used for the encryption.

arXiv:2605.04720May 6, 20260 citations

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.

We study the problem of private set intersection (PSI). In this problem, there are two entities

E_{i}

, for

i=1, 2

, each storing a set

\mathcal {P}_{i}

, whose elements are picked from a finite set

\mathbb {S}_{K}

, on

N_{i}

replicated and non-colluding databases. It is required to determine the set intersection

{\mathcal {P}}_{1} \cap {\mathcal {P}} _{2}

without leaking any information about the remaining elements to the other entity, and to do this with the least amount of downloaded bits. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem with certain added restrictions. Next, as a stand-alone result, we derive the information-theoretic sum capacity of MM-SPIR,

C_{MM-SPIR}

. We show that with

K

messages,

N

databases, and a given size of the desired message set

P

, the exact capacity of MM-SPIR is

C_{MM-SPIR} = 1 - \frac {1}{N}

when

P \leq K-1

, provided that the entropy of the common randomness

S

satisfies

H(S) \geq \frac {P}{N-1}

per desired symbol. When

P = K

, the MM-SPIR capacity is trivially 1 without the need for any common randomness

S

. This result implies that there is no gain for MM-SPIR over successive single-message SPIR (SM-SPIR). For the MM-SPIR problem, we present a novel capacity-achieving scheme which builds seamlessly over the near-optimal scheme of Banawan-Ulukus originally proposed for the multi-message PIR (MM-PIR) problem without any database privacy constraints. Surprisingly, our scheme here is exactly optimal for the MM-SPIR problem for any

P

, in contrast to the scheme for the MM-PIR problem, which was proved only to be near-optimal. Our scheme is an alternative to the successive usage of the SM-SPIR scheme of Sun-Jafar. Based on this capacity result for the MM-SPIR problem, and after addressing the added requirements in its conversion to the PSI problem, we show that the optimal download cost for the PSI problem is given by

\min \left \{{\left \lceil{ \frac {P_{1} N_{2}}{N_{2}-1}}\right \rceil, \left \lceil{ \frac {P_{2} N_{1}}{N_{1}-1}}\right \rceil }\right \}

, where

P_{i}

is the cardinality of set

{\mathcal {P}}_{i}

ε\in (0,1)

and

δ\in (0,\infty)

. We also show that the obtained necessary and sufficient condition does not depend on the constants

ε\in (0,1)

and

δ\in (0,\infty)

, demonstrating that we have the strong converse theorem for the proposed framework of source encryption. We further prove the existence of encryption/decryption schemes, which are universal in the sense that they work effectively for any distributions of the plain text and those of the key used for the encryption.