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

Improved Achievable Rate for Single-Server SPIR over Binary Erasure Channels

Amirhossein Shekofteh, Rémi A. Chou

Published Sep 17, 2025• 0 citations
OpenAlex

Abstract

In 1-out-of-D Symmetric Private Information Retrieval (SPIR) protocols, the client privately selects and retrieves one of the D files stored on a server, learns nothing about the remaining D − 1 files, and keeps its choice hidden from the server. We propose an achievable rate scheme for 1-out-of- D SPIR in a single-server setting over a binary erasure channel (BEC) with parameter ϵ, where the server controls the BEC input and the client observes the output. Existing 1-out-of-D SPIR protocols over BEC that build on repeated 1-out-of-2 primitives define the achievable rate as the number of bits transmitted per channel use. We propose a 1-out-of-D SPIR scheme over the BEC by repeating a novel 1-out-of-M SPIR scheme where [Editor’s note: see paper for mathematical equation]. Our derived achievable rate surpasses existing rates for ϵ ∈ [1/2, 1], and achieves the SPIR capacity for D = 2, and for D > 2 when [Editor’s note: see paper for mathematical equation].

Related papers

Dual-Source SPIR Over a Noiseless MAC Without Data Replication or Shared Randomness

Rémi A. Chou

Information-theoretically secure Symmetric Private Information Retrieval (SPIR) from a single server is known to be infeasible over noiseless channels. Known solutions to overcome this infeasibility involve additional resources such as database replication, shared randomness, or noisy channels. In this paper, we propose an alternative approach for achieving SPIR with information-theoretic security guarantees, without relying on shared randomness, noisy channels, or data replication. Specifically, we demonstrate that it is sufficient to use a noiseless binary adder multiple-access channel, where inputs are controlled by two non-colluding servers and the output is observed by the client, alongside a public noiseless communication channel between the client and the servers. Furthermore, in this setting, we characterize the optimal file rates, i.e., the file lengths normalized by the number of channel uses, that can be transferred.

arXiv:2503.14682•IEEE Transactions on Information Theory•Dec 8, 2025•3 citations

Capacity of K-out-of-N Oblivious Transfer over the Binary Erasure Channel

Amirhossein Shekofteh, Rémi A. Chou

We study K-out-of-N oblivious transfer (OT) over a binary erasure channel (BEC) and a public noiseless channel, under an honest-but-curious model. In this setting, a client retrieves K out of N messages stored by a server; the protocol must guarantee that the unselected messages remain private to the server and that the client’s choices remain hidden from the server. We show that the K-out-of-N OT capacity over a BEC with erasure probability ϵ is $C = \min \left({\frac{{K\varepsilon }}{{N - K}},1 - \varepsilon }\right).$ This characterization recovers the known capacity for 1-out-of-2 OT and, for 1-out-of-N OT, recovers the established capacity when $\frac{{N - 1}}{N} \leq \varepsilon $ while further establishing the capacity for all ϵ ∈ [0,1]. We also show that the naive K-out-of-N OT construction obtained by repeating an optimal 1-out-of-N OT protocol K times is suboptimal.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•1 citation

The Capacity of Oblivious Transfer with Replicated Databases and Binary Erasure Multiple Access Channel

Tianyou Pei, Wei Kang, Nan Liu

Both the oblivious transfer (OT) problem and the symmetric private information retrieval (SPIR) problem studies the scenario where a client retrieves information privately and securely from databases, i.e., the privacy of the client is protected from the databases, and the undesired information is protected from the client. The OT problem studies the case of one database plus additional noisy resources between the database and the client. The SPIR problem studies the case of multiple replicated and non-colluding databases. In this paper, we combine the two models and propose a new problem of oblivious transfer (OT) with two replicated databases and a binary erasure multiple access channel connecting the databases and the client. We first provide an upper bound on the OT capacity. We then propose a protocol which achieves the upper bound. Therefore, we obtain the capacity of OT for this model. In our achievability and converse proofs, we utilized the techniques from both traditional OT and PIR. Compared to schemes that utilizes only techniques from OT, we see a 100% increase in the achieved OT rate.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•2 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•3 citations

Private Set Intersection Using a Binary Erasure Channel

Amirhossein Shekofteh, Rémi A. Chou

We consider a Private Set Intersection (PSI) problem, where a server holds an arbitrary number of private subsets and a client holds a private subset of size K over a universe of size N. The client wants to compute the intersection of its set with each private subset of the server, learning only these intersections, while the server learns nothing about the client’s private set. The server controls the input of a binary erasure channel (BEC) with parameter ϵ, whose output is observed by the client, and both client and server can communicate over a noiseless channel. We define the PSI rate as the ratio of the number of server subsets to the number of BEC uses and characterize the information-theoretic PSI capacity as ${C_{{\text{PSI}}}} = \min \left( {\frac{\varepsilon }{{N - K}},\frac{{1 - \varepsilon }}{K}} \right)$. Our result is obtained by reducing the PSI problem to a K-out-of-N oblivious transfer problem and proving that this reduction is optimal.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

Dual-Source Symmetric PIR Without Data Replication or Shared Randomness

Rémi A. Chou

Information-theoretically secure Symmetric Private Information Retrieval (SPIR) is known to be infeasible over noiseless channels with a single server. Previous solutions in-volved additional resources such as database replication, shared randomness, or noisy channels. This paper demonstrates that, using a noiseless multiple access channel, SPIR with information-theoretic security guarantees is feasible without shared random-ness, a noisy channel, or data replication. Specifically, we leverage a noiseless binary adder channel and employ two non-colluding servers with independent content. Furthermore, we characterize the optimal file rates, i.e., the file lengths normalized by the number of channel uses, that can be transferred.

IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•3 citations
In 1-out-of-D Symmetric Private Information Retrieval (SPIR) protocols, the client privately selects and retrieves one of the D files stored on a server, learns nothing about the remaining D − 1 files, and keeps its choice hidden from the server. We propose an achievable rate scheme for 1-out-of- D SPIR in a single-server setting over a binary erasure channel (BEC) with parameter ϵ, where the server controls the BEC input and the client observes the output. Existing 1-out-of-D SPIR protocols over BEC that build on repeated 1-out-of-2 primitives define the achievable rate as the number of bits transmitted per channel use. We propose a 1-out-of-D SPIR scheme over the BEC by repeating a novel 1-out-of-M SPIR scheme where [Editor’s note: see paper for mathematical equation]. Our derived achievable rate surpasses existing rates for ϵ ∈ [1/2, 1], and achieves the SPIR capacity for D = 2, and for D > 2 when [Editor’s note: see paper for mathematical equation].
Information-theoretically secure Symmetric Private Information Retrieval (SPIR) from a single server is known to be infeasible over noiseless channels. Known solutions to overcome this infeasibility involve additional resources such as database replication, shared randomness, or noisy channels. In this paper, we propose an alternative approach for achieving SPIR with information-theoretic security guarantees, without relying on shared randomness, noisy channels, or data replication. Specifically, we demonstrate that it is sufficient to use a noiseless binary adder multiple-access channel, where inputs are controlled by two non-colluding servers and the output is observed by the client, alongside a public noiseless communication channel between the client and the servers. Furthermore, in this setting, we characterize the optimal file rates, i.e., the file lengths normalized by the number of channel uses, that can be transferred.
We study K-out-of-N oblivious transfer (OT) over a binary erasure channel (BEC) and a public noiseless channel, under an honest-but-curious model. In this setting, a client retrieves K out of N messages stored by a server; the protocol must guarantee that the unselected messages remain private to the server and that the client’s choices remain hidden from the server. We show that the K-out-of-N OT capacity over a BEC with erasure probability ϵ is C=min⁡(KεN−K,1−ε).C = \min \left({\frac{{K\varepsilon }}{{N - K}},1 - \varepsilon }\right).C=min(N−KKε​,1−ε). This characterization recovers the known capacity for 1-out-of-2 OT and, for 1-out-of-N OT, recovers the established capacity when $\frac{{N - 1}}{N} \leq \varepsilon $ while further establishing the capacity for all ϵ ∈ [0,1]. We also show that the naive K-out-of-N OT construction obtained by repeating an optimal 1-out-of-N OT protocol K times is suboptimal.
Both the oblivious transfer (OT) problem and the symmetric private information retrieval (SPIR) problem studies the scenario where a client retrieves information privately and securely from databases, i.e., the privacy of the client is protected from the databases, and the undesired information is protected from the client. The OT problem studies the case of one database plus additional noisy resources between the database and the client. The SPIR problem studies the case of multiple replicated and non-colluding databases. In this paper, we combine the two models and propose a new problem of oblivious transfer (OT) with two replicated databases and a binary erasure multiple access channel connecting the databases and the client. We first provide an upper bound on the OT capacity. We then propose a protocol which achieves the upper bound. Therefore, we obtain the capacity of OT for this model. In our achievability and converse proofs, we utilized the techniques from both traditional OT and PIR. Compared to schemes that utilizes only techniques from OT, we see a 100% increase in the achieved OT rate.
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.
We consider a Private Set Intersection (PSI) problem, where a server holds an arbitrary number of private subsets and a client holds a private subset of size K over a universe of size N. The client wants to compute the intersection of its set with each private subset of the server, learning only these intersections, while the server learns nothing about the client’s private set. The server controls the input of a binary erasure channel (BEC) with parameter ϵ, whose output is observed by the client, and both client and server can communicate over a noiseless channel. We define the PSI rate as the ratio of the number of server subsets to the number of BEC uses and characterize the information-theoretic PSI capacity as CPSI=min⁡(εN−K,1−εK){C_{{\text{PSI}}}} = \min \left( {\frac{\varepsilon }{{N - K}},\frac{{1 - \varepsilon }}{K}} \right)CPSI​=min(N−Kε​,K1−ε​). Our result is obtained by reducing the PSI problem to a K-out-of-N oblivious transfer problem and proving that this reduction is optimal.
Information-theoretically secure Symmetric Private Information Retrieval (SPIR) is known to be infeasible over noiseless channels with a single server. Previous solutions in-volved additional resources such as database replication, shared randomness, or noisy channels. This paper demonstrates that, using a noiseless multiple access channel, SPIR with information-theoretic security guarantees is feasible without shared random-ness, a noisy channel, or data replication. Specifically, we leverage a noiseless binary adder channel and employ two non-colluding servers with independent content. Furthermore, we characterize the optimal file rates, i.e., the file lengths normalized by the number of channel uses, that can be transferred.