We consider private information retrieval (PIR) of a single file out of K files from N non-colluding databases with heterogeneous storage constraints m = (m1, ⋯, mN). The aim of this work is to jointly design the content placement phase and the information retrieval phase in order to minimize the download cost in the PIR phase. We characterize the optimal PIR download cost as a linear program. By analyzing the structure of the optimal solution of this linear program, we show that, surprisingly, the optimal download cost in our heterogeneous case matches its homogeneous counterpart where all databases have the same average storage constraint μ = 1/N Σn=1Nmn. N Thus, we show that there is no loss in the PIR capacity due to heterogeneity of storage spaces of the databases. We provide the optimum content placement explicitly for N = 3.

We consider the problem of private information retrieval (PIR) of a single message out of K messages from N replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size S possesses side information in the form of uncoded portions of the messages where the message identities are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint S as D* = 1+ 1/N + 1/N2+· · ·+ 1/NK-1-M+ 1-rM/NK-M+ 1-rM-1/NK-M+1+ · · · + 1-r1/NK-1, where M is the number of side information messages and ri is the portion of the ith side information message that is cached with Σi=1Mri= S. Based on this capacity result, we prove two facts: First, for a fixed memory size S and a fixed number of accessible messages M, uniform caching achieves the lowest normalized download cost, i.e., ri= S/M, for i = 1, . . . , M, is optimum. Second, for a fixed memory size S, among all possible K - ⌈S⌉ + 1 uniform caching schemes, the uniform caching scheme which caches M = K messages achieves the lowest normalized download cost.

We consider private information retrieval (PIR) of a single file out of K files from N non-colluding databases with heterogeneous storage constraints m = (m1, ⋯, mN). The aim of this work is to jointly design the content placement phase and the retrieval phase in order to minimize the download cost in the PIR phase. We characterize the optimal PIR download cost as a linear program. By analyzing the structure of the optimal solution of this linear program, we show that, surprisingly, the optimal download cost in our heterogeneous case matches its homogeneous counterpart where all databases have the same average storage constraint μ = 1/N Σn = 1Nmn. We show the optimum content placement explicitly for N = 3.

We consider the private information retrieval (PIR) problem from decentralized uncoded caching databases. There are two phases in our problem setting, a caching phase, and a retrieval phase. In the caching phase, a data center containing all the K files, where each file is of size L bits, and several databases with storage size constraint μKL bits exist in the system. Each database independently chooses μKL bits out of the total KL bits from the data center to cache through the same probability distribution in a decentralized manner. In the retrieval phase, a user (retriever) accesses N databases in addition to the data center, and wishes to retrieve a desired file privately. We characterize the optimal normalized download cost to be D/L = Σn-1N+1(n-1N)μn-1(1 - μ)N+1-n(1 + 1/n + ⋯ + 1/nK-1). We show that uniform and random caching scheme which is originally proposed for decentralized coded caching by MaddahAli and Niesen, along with Sun and Jafar retrieval scheme which is originally proposed for PIR from replicated databases surprisingly result in the lowest normalized download cost. This is the decentralized counterpart of the recent result of Attia, Kumar and Tandon for the centralized case.

We consider the problem of private information retrieval (PIR) from N non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction r from each of the K stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate D*(r) the optimal download cost normalized with the message size as a function of K, N, and r. For a fixed K and N, we develop an inner bound (converse bound) for the D*(r) curve. The inner bound is a piece-wise linear function in r that consists of K line segments. For the achievability, we develop explicit schemes that exploit the cached bits as side information to achieve K -1 non-degenerate corner points. These corner points differ in the number of cached bits that are used to generate the one-side information equation. We obtain an outer bound (achievability) for any caching ratio by memory sharing between these corner points. Thus, the outer bound is also a piece-wise linear function in r that consists of K line segments. The inner and the outer bounds match in general for the cases of very low-caching ratio and very high-caching ratio. As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r, we show that the largest gap between the achievability and the converse bounds is 1/6. Our results show that the download cost can be reduced beyond memory sharing if the databases are unaware of the cached content.

We consider the problem of private information retrieval (PIR) of a single message out of$K$messages from$N$replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size$M$possesses side information in the form of full messages that are partially known to the databases. In this model, the user and the databases engage in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user downloads desired information. In the prefetching phase, the user receives$m_{n}$full messages from the$n$th database, under the cache memory size constraint$\sum _{n=1}^{N} m_{n} \leq M$. In the retrieval phase, the user wishes to retrieve a message (which is not present in its memory) such that no individual database learns anything about the identity of the desired message. In addition, the identities of the side information messages that the user did not prefetch from a database must remain private against that database. Since the side information provided by each database in the prefetching phase is known by the providing database and the side information must be kept private against the remaining databases, we coin this model aspartially known private side information. We characterize the capacity of the PIR with partially known private side information to be$C=\left ({1+\frac {1}{N}+\cdots +\frac {1}{N^{K-M-1}}}\right)^{-1}=\frac {1-\frac {1}{N}}{1-\left({\frac {1}{N}}\right)^{K-M}}$. Interestingly, this result is the same if none of the databases knows any of the prefetched side information, i.e., when the side information is obtained externally, a problem posed by Kadhe et al. and settled by Chen-Wang-Jafar recently. Thus, our result implies that there is no loss in using the same databases for both prefetching and retrieval phases.

We consider the problem of private information retrieval (PIR) from N non-colluding and replicated databases, when the user is equipped with a cache that holds an uncoded fraction r from each of the K stored messages in the databases. This model operates in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user privately downloads the desired message. In the prefetching phase, the user receivesrN uncoded fraction of each message from the nth database. This side information is known only to the nth database and unknown to the remaining databases, i.e., the user possesses partially known side information. We investigate the optimal normalized download cost D*(r) as a function of K, N, r. For a fixed K, N, we develop an inner bound (converse) and an outer bound (achievability) for the D*(r) curve. The bounds match in general for the cases of very low caching ratio (r ≤ 1/NK-1) and very high caching ratio (r ≥ K-2/N2-3N+KN). As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r, we show that the largest gap between the achievability and the converse bounds is 5/32.

We consider the problem of private information retrieval (PIR) from N non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction r from each of the K stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate D*(r) the optimal download cost normalized with the message size as a function of K, N, r. We develop inner and outer bounds for the optimal download cost. Both inner and outer bounds are piece-wise linear functions in r (for fixed N, K) that consist of K line segments. The inner and the outer bounds match in general for the cases of very low caching ratios and very high caching ratios. As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r, we show that the largest additive gap between the achievability and the converse bounds is [1/6].

We consider the problem of private information retrieval (PIR) of a single message out of K messages from N replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size S possesses side information in the form of uncoded portions of the messages that are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint S as D* =1+1/N+ 1/N2+ · · · + 1/NK-1-M+ 1 - rM/NK-M+ 1 - rM1/NK-M+1 + · · · + 1-r1/ NK-1, where riis the portion of the ith side information message that is cached with Σi=1Mri= S. Based on this capacity result, we prove two facts: First, for a fixed memory size S and a fixed number of accessible messages M, uniform caching achieves the lowest normalized download cost, i.e., ri= S/M, for i = 1,· · ·, M, is optimum. Second, for a fixed memory size S, among all possible K - 〈S〉 +1 uniform caching schemes, the uniform caching scheme which caches M = K messages achieves the lowest normalized download cost.

We consider the problem of private information retrieval from N non-colluding and replicated databases, when the user is equipped with a cache that holds an uncoded fraction r of the symbols from each of the K stored messages in the databases. This model operates in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user privately downloads the desired message. In the prefetching phase, the user receives r/N uncoded fraction of each message from the nth database. This side information is known only to the nth database and unknown to the remaining databases, i.e., the user possesses partially known side information. We investigate the optimal normalized download cost D*(r) in the retrieval phase as a function of K, N, and r. We develop lower and upper bounds for the optimal download cost. The bounds match in general for the cases of very low caching ratio and very high caching ratio. We fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r values, we show that the largest additive gap between the achievability and the converse bounds is 5/32.

We propose a new decentralized coded caching scheme for a two-phase caching network, where the data placed in user caches in the prefetching phase are random portions of a maximal distance separable (MDS) coded version of the original files. The proposed scheme achieves a better rate memory trade-off by utilizing the reconstruction property of MDS codes which reduces the number of transmissions that are useful only for a small subset of users in the delivery phase. Unlike the previously available coded prefetching schemes, the proposed scheme does not require to have more users than files. The proposed scheme can be viewed as a generalization of the original uncoded prefetching based decentralized coded caching scheme, and likewise, is applicable to various network topologies.

Information-theoretic work for wiretap channels is mostly based on random coding schemes. Designing practical coding schemes to achieve information-theoretic secrecy is an important problem. By applying two recently developed techniques for polar codes, namely, universal polar coding and polar coding for asymmetric channels, we propose a polar coding scheme to achieve the secrecy capacity of the general wiretap channel. We then apply this coding scheme to achieve the best-known inner bounds for the multiple access wiretap channel (MAC-WTC), and the broadcast and interference channels with confidential messages (BC-CM and IC-CM).

This paper considers noisy Wyner-Ziv coding (WZC), in which a remote noisy source is compressed with side information at the decoder only. The decoder side information is not limited to being Gaussian, thus this noisy WZC problem cannot be transformed into the conventional one tailored for noiseless sources. A new coding structure, named the residual-quantization (RQ) based noisy WZC, is proposed to solve the problem. This scheme explicitly constructs the theoretical auxiliary random variable to facilitate optimal reconstruction of the noisy source. In this two-stage encoder, the noisy source is quantized twice and the quantization error (residue) of the first stage is the input of the second stage. By sending only the quantization index of the second stage to the decoder, the corresponding code rate can theoretically approach the noisy WZC bound. Moreover, the RQ-based noisy WZC is implemented using graph-based codes. The main challenge is that it is necessary to design a codebook that is simultaneously good for source and channel coding for the first stage quantization, since this quantization code also acts as a channel code at the decoder. This problem is solved by constructing a low-density parity check (LDPC) code with edge degrees optimized for channel coding, and enhancing its performance for source coding by using a modified reinforced belief-propagation quantization algorithm. Simulation results show that the noisy Wyner-Ziv bounds can be practically approached by our implementation. In addition, the proposed implementation offers more flexibility in the code rates compared with the existing practical designs, making it more suitable for emerging applications such as fronthaul compression.

Information-theoretic work for wiretap channels is mostly based on random coding schemes. Designing practical coding schemes to achieve information-theoretic security is an important problem. By applying two recently developed techniques for polar codes, namely, universal polar coding and polar coding for asymmetric channels, we propose a polar coding scheme to achieve the secrecy capacity of the general wiretap channel.

Wyner-Ziv coding (WZC) is a compression technique using decoder side information, which is unknown at the encoder, to help the reconstruction. In this paper, we propose and implement a new WZC structure, called residual WZC, for the quadratic-Gaussian Wyner-Ziv problem where side information can be arbitrarily distributed. In our two-stage residual WZC, the source is quantized twice and the input of the second stage is the quantization error (residue) of the first stage. The codebook of the first stage quantizer must be simultaneously good for source and channel coding, since it also acts as a channel code at the decoder. Stemming from the non-ideal quantization at the encoder, a problem of channel decoding beyond capacity is identified and solved when we design the practical decoder. Moreover, by using the modified reinforced belief-propagation quantization algorithm, the low-density parity check code (LDPC), whose edge degree is optimized for channel coding, also performs well as a source code. We then implement the residual WZC by an LDPC and a low-density generator matrix code (LDGM). The simulation results show that our practical construction approaches the Wyner-Ziv bound. Compared with previous works, our construction can offer more design flexibility in terms of distribution of side information and practical code rate selection.