Single-server Multi-message Private Information Retrieval with Side Information: the General Cases

The single-server multi-message private information retrieval with side information problem is studied for general cases. In this problem, K independent messages are stored at a single server. One user initially has M messages as side information and wants to download N demand messages while not leaking any information about the indices of demand messages to the server. In our previous work, we characterized the minimum number of required download bits and presented an achievability scheme for this problem with the constraint of linear codes. In this paper, we extend the results to general (non-linear) codes and present the closed-form expression for the minimum number of required download bits. Moreover, we show that linear coding schemes are sufficient to achieve the optimal (minimum) download bits. Additionally, we show that the trivial MDS coding scheme with K - M transmissions is optimal if N > M or N 2 +N ≥ K-M. This means if one wishes to privately download more than the square-root of the number of messages in the database, then one must effectively download the full database (minus the side information), irrespective of the amount of side information one has available.

Single-server Multi-message Private Information Retrieval with Side Information

Michael Christoph Gastpar, Su Li

We study the problem of single-server multi-message private information retrieval with side information. One user wants to recover N out of K independent messages which are stored at a single server. The user initially possesses a subset of M messages as side information. The goal of the user is to download the N demand messages while not leaking any information about the indices of these messages to the server. In this paper, we characterize the minimum number of required transmissions for linear codes. Moreover, we present an optimal coding scheme which enables the user to download the demand messages and preserves the privacy of their indices by using linear codes. Additionally, we show that the trivial MDS coding scheme with K - M transmissions is optimal if N > M or N-2 + N >= K - M. This means if one wishes to privately download more than the square-root of the number of files in the database, then one must effectively download the full database (minus the side information), irrespective of the amount of side information one has available.

IEEE2018

Single-server Multi-user Private Information Retrieval with Side Information

Michael Christoph Gastpar, Su Li

In the problem of private information retrieval with side information, a single user wants to recover one of the K independent messages which are stored at one or multiple servers. The user initially has a subset of messages as side information. The goal of the user is to retrieve the demand message by using minimum number of transmissions (R∗) from the server(s) to the user under the condition that the index of the demand message should not be inferred by the server. We introduce the multi-user variant into this problem, where each user wants to retrieve one message and has a subset of messages as side information. In this paper, we study the special cases where all users want to retrieve one common message from a single server, but each user has different side information messages. We show that the optimal coding scheme can be constructed by first optimally partitioning the messages and then generating MDS codes separately in each subset of messages in the partition. We determine the R∗ , propose algorithms to compute R∗ , and construct optimal linear coding schemes with complexity polynomial in K (but exponential in the number of side information messages).

2018

Polarization and Channel Ordering: Characterizations and Topological Structures

Rajai Nasser

Information theory is the field in which we study the fundamental limitations of communication. Shannon proved in 1948 that there exists a maximum rate, called capacity, at which we can reliably communicate information through a given channel. However, Shannon did not provide an explicit construction of a practical coding scheme that achieves the capacity. Polar coding, invented by Arikan, is the first low-complexity coding technique that achieves the capacity of binary-input memoryless symmetric channels. The construction of these codes is based on a phenomenon called polarization. The study of polar codes and their generalization to arbitrary channels is the subject of polarization theory, a subfield of information and coding theories. This thesis consists of two parts. In the first part, we provide solutions to several open problems in polarization theory. The first open problem that we consider is to determine the binary operations that always lead to polarization when they are used in Arikan-style constructions. In order to solve this problem, we develop an ergodic theory for binary operations. This theory is used to provide a necessary and sufficient condition that characterizes the polarizing binary operations, both in the single-user and the multiple-access settings. We prove that the exponent of a polarizing binary operation cannot exceed 1/2. Furthermore, we show that the exponent of an arbitrary quasigroup operation is exactly 1/2. This implies that quasigroup operations are among the best polarizing binary operations. One drawback of polarization in the multiple-access setting is that it sometimes induces a loss in the symmetric capacity region of a given multiple-access channel (MAC). An open problem in MAC polarization theory is to determine all the MACs that do not lose any part of their capacity region by polarization. Using Fourier analysis, we solve this problem by providing a single-letter necessary and sufficient condition that characterizes all these MACs in the general setting where we have an arbitrary number of users, and each user uses an arbitrary Abelian group operation on his input alphabet. We also study the polarization of classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation, and an Arikan-style transformation is applied using this operation. We show that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary classical-quantum multiple-access channels (cq-MAC). In the second part of this thesis, we investigate several problems that are related to three orderings of communication channels: degradedness, input-degradedness, and the Shannon ordering. We provide several characterizations for the input-degradedness and the Shannon ordering. Two channels are said to be equivalent if they are degraded from each other. Input-equivalence and Shannon-equivalence between channels are similarly defined. We construct and study several topologies on the quotients of the spaces of discrete memoryless channels (DMC) by the equivalence, the input-equivalence and the Shannon-equivalence relations. Finally, we prove the continuity of several channel parameters and operations under various DMC topologies.

EPFL2017

Polarization and Channel Ordering: Characterizations and Topological Structures

Rajai Nasser

EPFL2017