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.
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.
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.
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.
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 –1bit/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.
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.
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.
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.