Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.07828 · IEEE Information Theory Workshop (ITW)

Digital Blind Box: Random Symmetric Private Information Retrieval

Zhusheng Wang, Şennur Ulukuş

Published Nov 1, 2022• 9 citations
arXivHTMLPDF

Abstract

We introduce the problem of random symmetric private information retrieval (RSPIR). In canonical PIR, a user downloads a message out of K messages from N non-colluding and replicated databases in such a way that no database can know which message the user has downloaded (user privacy). In SPIR, the privacy is symmetric, in that, not only that the databases cannot know which message the user has downloaded, the user itself cannot learn anything further than the particular message it has downloaded (database privacy). In RSPIR, different from SPIR, the user does not have an input to the databases, i.e., the user does not pick a specific message to download, instead is content with any one of the messages. In RSPIR, the databases need to send symbols to the user in such a way that the user is guaranteed to download a message correctly (random reliability), the databases do not know which message the user has received (user privacy), and the user does not learn anything further than the one message it has received (database privacy). This is the digital version of a blind box, also known as gachapon, which implements the above specified setting with physical objects for entertainment. This is also the blind version of 1-out-of-K oblivious transfer (OT), an important cryptographic primitive. We study the information-theoretic capacity of RSPIR for the case of N = 2 databases. We determine its exact capacity for the cases of K = 2,3,4 messages. While we provide a general achievable scheme that is applicable to any number of messages, the capacity for K ≥5 remains open.

DOI
10.1109/itw54588.2022.9965793

Related papers

The Capacity of Symmetric Private Information Retrieval

Hua Sun, Syed A. Jafar

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K - 1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N -1) bits per desired message bit, and zero otherwise.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2016•51 citations

The Capacity of Symmetric Private Information Retrieval

Hua Sun, Syed A. Jafar

Private information retrieval (PIR) is the problem of retrieving, as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K - 1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N -1) bits per desired message bit. Otherwise, if the amount of common randomness is less than 1/(N -1) bits per message bit, then the capacity of SPIR is zero. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.

IEEE Transactions on Information Theory•Jun 19, 2018•187 citations

The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems

Shreya Shrestha Meel, Şennur Ulukuş

In symmetric private information retrieval (SPIR), a user communicates with multiple servers to retrieve from them a message in a database, while not revealing the message index to any individual server (user privacy), and learning no additional information about the database (database privacy). We study the problem of SPIR on graph-replicated database systems, where each node of the graph represents a server and each link represents a message. Each message is replicated at exactly two servers; those at which the link representing the message is incident. To ensure database privacy, the servers share a set of common randomness, independent of the database and the user's desired message index. We study two cases of common randomness distribution to the servers: i) graph-replicated common randomness, and ii) fully-replicated common randomness. Given a graph-replicated database system, in i), we assign one randomness variable independently to every pair of servers sharing a message, while in ii), we assign an identical set of randomness variable to all servers, irrespective of the underlying graph. In both settings, our goal is to characterize the SPIR capacity, i.e., the maximum number of desired message symbols retrieved per downloaded symbol, and quantify the minimum amount of common randomness required to achieve the capacity. To this goal, in setting i), we derive a general lower bound on the SPIR capacity, and show it to be tight for path and regular graphs through a matching converse. Moreover, we establish that the minimum size of common randomness required for SPIR is equal to the message size. In setting ii), the SPIR capacity improves over the first, more restrictive setting. We show this through capacity lower bounds for a class of graphs, by constructing SPIR schemes from PIR schemes.

arXiv:2602.16700•IEEE Transactions on Information Theory•Jan 1, 2026•0 citations

Storage Constrained Information Theoretic Symmetric Private Information Retrieval

Deepak Kumar

Private information retrieval (PIR) is an important protocol in cryptographic community to ensure privacy of the user when retrieving information from untrusted databases. In a variation to this problem, symmetric private information retrieval (SPIR) is a protocol which ensures the privacy of user as well as databases. A major drawback for the majority of existing works on information theoretic PIR and SPIR is that they focus on scenarios where all databases store the entire data set (i.e. replicated databases). The goal of this thesis is to present PIR and SPIR schemes for storage constrained databases. For both PIR and SPIR, we present a systematic approach to utilize storage constrained databases. The technical contribution involves two main parts: (a) a careful storage scheme to split and store messages across databases; and (b) construction of information theoretic PIR and SPIR schemes from such databases. We also compare our results to the fully replicated scenario, as well as compare the differences between the communication overhead of PIR and SPIR schemes.

•Jun 25, 2018•0 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}$.

arXiv:1912.13501•IEEE Transactions on Information Theory•Nov 2, 2021•56 citations

On PIR and SPIR Over Gaussian MAC

Or Elimelech, Asaf Cohen

This paper revisits the problems of Private Information Retrieval (PIR) and Symmetric PIR (SPIR). In PIR, a user retrieves a desired message fromNreplicated, non-communicating databases, each storing the sameMmessages, while preserving the privacy of the requested message index. SPIR extends this notion further by additionally protecting the privacy of the databases, ensuring that the user learns no information beyond the requested message. In this paper, we assume a block-fading Additive White Gaussian Noise Multiple Access Channel (AWGN MAC) linking the user and the databases. Previous work presented a joint channel-PIR scheme utilizing the Compute and Forward (C&F) protocol, demonstrating the potential of a joint PIR-channel coding scheme over a separated one, yet still lagging behind the channel capacity and requiring significant computational complexity. We propose an improved scheme that offers reduced computational complexity while improving the achievable rate for finite parameters, as well as its scaling laws. Specifically, the achievable rate outperforms the C&F-based approach and scales with the number of databasesNand the powerPsimilarly to the channel capacitywithout the privacy constraint. Furthermore, the analysis demonstrates that the improved rate exhibits only a finite gap from this unconstrained channel capacity –$1~bit/sec/Hz$asNincreases. Finally, we provide two SPIR schemes. The first is a modification for our PIR scheme to attain SPIR with no rate loss, which is accomplished by introducing shared common randomness among databases. The second is a novel joint channel-SPIR scheme that utilizes the channel and lattice codes characteristics to nontrivially achieve SPIR without requiring common randomness, at the price of a loss in the achievable rate.

arXiv:2401.15912•IEEE Transactions on Communications•Aug 11, 2025•2 citations
We introduce the problem of random symmetric private information retrieval (RSPIR). In canonical PIR, a user downloads a message out of K messages from N non-colluding and replicated databases in such a way that no database can know which message the user has downloaded (user privacy). In SPIR, the privacy is symmetric, in that, not only that the databases cannot know which message the user has downloaded, the user itself cannot learn anything further than the particular message it has downloaded (database privacy). In RSPIR, different from SPIR, the user does not have an input to the databases, i.e., the user does not pick a specific message to download, instead is content with any one of the messages. In RSPIR, the databases need to send symbols to the user in such a way that the user is guaranteed to download a message correctly (random reliability), the databases do not know which message the user has received (user privacy), and the user does not learn anything further than the one message it has received (database privacy). This is the digital version of a blind box, also known as gachapon, which implements the above specified setting with physical objects for entertainment. This is also the blind version of 1-out-of-K oblivious transfer (OT), an important cryptographic primitive. We study the information-theoretic capacity of RSPIR for the case of N = 2 databases. We determine its exact capacity for the cases of K = 2,3,4 messages. While we provide a general achievable scheme that is applicable to any number of messages, the capacity for K ≥5 remains open.
Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K - 1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N -1) bits per desired message bit, and zero otherwise.
Private information retrieval (PIR) is the problem of retrieving, as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K - 1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N -1) bits per desired message bit. Otherwise, if the amount of common randomness is less than 1/(N -1) bits per message bit, then the capacity of SPIR is zero. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.
In symmetric private information retrieval (SPIR), a user communicates with multiple servers to retrieve from them a message in a database, while not revealing the message index to any individual server (user privacy), and learning no additional information about the database (database privacy). We study the problem of SPIR on graph-replicated database systems, where each node of the graph represents a server and each link represents a message. Each message is replicated at exactly two servers; those at which the link representing the message is incident. To ensure database privacy, the servers share a set of common randomness, independent of the database and the user's desired message index. We study two cases of common randomness distribution to the servers: i) graph-replicated common randomness, and ii) fully-replicated common randomness. Given a graph-replicated database system, in i), we assign one randomness variable independently to every pair of servers sharing a message, while in ii), we assign an identical set of randomness variable to all servers, irrespective of the underlying graph. In both settings, our goal is to characterize the SPIR capacity, i.e., the maximum number of desired message symbols retrieved per downloaded symbol, and quantify the minimum amount of common randomness required to achieve the capacity. To this goal, in setting i), we derive a general lower bound on the SPIR capacity, and show it to be tight for path and regular graphs through a matching converse. Moreover, we establish that the minimum size of common randomness required for SPIR is equal to the message size. In setting ii), the SPIR capacity improves over the first, more restrictive setting. We show this through capacity lower bounds for a class of graphs, by constructing SPIR schemes from PIR schemes.
Private information retrieval (PIR) is an important protocol in cryptographic community to ensure privacy of the user when retrieving information from untrusted databases. In a variation to this problem, symmetric private information retrieval (SPIR) is a protocol which ensures the privacy of user as well as databases. A major drawback for the majority of existing works on information theoretic PIR and SPIR is that they focus on scenarios where all databases store the entire data set (i.e. replicated databases). The goal of this thesis is to present PIR and SPIR schemes for storage constrained databases. For both PIR and SPIR, we present a systematic approach to utilize storage constrained databases. The technical contribution involves two main parts: (a) a careful storage scheme to split and store messages across databases; and (b) construction of information theoretic PIR and SPIR schemes from such databases. We also compare our results to the fully replicated scenario, as well as compare the differences between the communication overhead of PIR and SPIR schemes.
We study the problem of private set intersection (PSI). In this problem, there are two entitiesEiE_{i}Ei​, fori=1,2i=1, 2i=1,2, each storing a setPi\mathcal {P}_{i}Pi​, whose elements are picked from a finite setSK\mathbb {S}_{K}SK​, onNiN_{i}Ni​replicated and non-colluding databases. It is required to determine the set intersectionP1∩P2{\mathcal {P}}_{1} \cap {\mathcal {P}} _{2}P1​∩P2​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,CMM−SPIRC_{MM-SPIR}CMM−SPIR​. We show that withKKKmessages,NNNdatabases, and a given size of the desired message setPPP, the exact capacity of MM-SPIR isCMM−SPIR=1−1NC_{MM-SPIR} = 1 - \frac {1}{N}CMM−SPIR​=1−N1​whenP≤K−1P \leq K-1P≤K−1, provided that the entropy of the common randomnessSSSsatisfiesH(S)≥PN−1H(S) \geq \frac {P}{N-1}H(S)≥N−1P​per desired symbol. WhenP=KP = KP=K, the MM-SPIR capacity is trivially 1 without the need for any common randomnessSSS. 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 anyPPP, 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 bymin⁡{⌈P1N2N2−1⌉,⌈P2N1N1−1⌉}\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 \}min{⌈N2​−1P1​N2​​⌉,⌈N1​−1P2​N1​​⌉}, wherePiP_{i}Pi​is the cardinality of setPi{\mathcal {P}}_{i}Pi​.
This paper revisits the problems of Private Information Retrieval (PIR) and Symmetric PIR (SPIR). In PIR, a user retrieves a desired message fromNreplicated, non-communicating databases, each storing the sameMmessages, while preserving the privacy of the requested message index. SPIR extends this notion further by additionally protecting the privacy of the databases, ensuring that the user learns no information beyond the requested message. In this paper, we assume a block-fading Additive White Gaussian Noise Multiple Access Channel (AWGN MAC) linking the user and the databases. Previous work presented a joint channel-PIR scheme utilizing the Compute and Forward (C&F) protocol, demonstrating the potential of a joint PIR-channel coding scheme over a separated one, yet still lagging behind the channel capacity and requiring significant computational complexity. We propose an improved scheme that offers reduced computational complexity while improving the achievable rate for finite parameters, as well as its scaling laws. Specifically, the achievable rate outperforms the C&F-based approach and scales with the number of databasesNand the powerPsimilarly to the channel capacitywithout the privacy constraint. Furthermore, the analysis demonstrates that the improved rate exhibits only a finite gap from this unconstrained channel capacity –1 bit/sec/Hz1~bit/sec/Hz1 bit/sec/HzasNincreases. Finally, we provide two SPIR schemes. The first is a modification for our PIR scheme to attain SPIR with no rate loss, which is accomplished by introducing shared common randomness among databases. The second is a novel joint channel-SPIR scheme that utilizes the channel and lattice codes characteristics to nontrivially achieve SPIR without requiring common randomness, at the price of a loss in the achievable rate.