We consider the secure coded caching problem proposed by Ravindrakumaret. alwhere no user can obtain information about files other than the one requested. We first propose three new schemes for 1) the general case with arbitraryNfiles andKusers; 2) cache sizeM= 1,N= 2 files and arbitraryKusers; and 3) worst-case delivery rateR= 1, arbitraryNfiles andKusers, respectively. Then we derive some new converse results for 1) the general case with arbitraryNfiles andKusers; 2) cache sizeM= 1 with arbitraryNfiles andKusers; 3) worst-case delivery rateR= 1 with arbitraryNfiles andKusers; and 4) cache sizeM∈ [1,K/K-1] withN= 2 files and arbitraryKusers. As a result, we obtain 1) the two exact end-points for the optimal memory-rate tradeoff curve for arbitrary number of users and files; 2) a segment of the optimal memory-rate tradeoff curve, whereM∈ [1,K/K-1], for the case ofN= 2 files and arbitrary number of users; and 3) a multiplicative-gap-10 result, i.e., we show that the proposed achievable schemes achieve a ratio less than 10 with respect to the cut-set bound.

We investigate the demand-private coded caching problem, in whichKusers, each equipped with a cache of sizeM, access a library ofNfiles under a privacy constraint. This constraint requires that no user obtain any information about the demands of others. We first present a new virtual-user-based achievable scheme for arbitrary numbers of users and files, which yields tighter order-optimal guarantees whenN≤KandM≤ 1. Next, we further focus on the caseN≤K. On the achievability side, for cache sizeM∈ [0,N/(K+1)(N−1)], we propose a novel demand-private scheme based on the idea that each user’s decoding process should depend only on their own demand. In terms of converse, we derive a new converse bound that is applicable forN≤Kand arbitraryM. Comparing the proposed achievability and converse, we find the optimal memory-rate tradeoff of the demand-private coded caching problem forM∈ [0,N/(K+1)(N−1)] whereN≤K≤ 2N−2, and the optimal memory-rate tradeoff forM∈ [0,1/K+1] whereK> 2N− 2. Moreover, for the case of 2 files and arbitrary number of users, by deriving another new converse bound, the optimal memory-rate tradeoff is characterized forM∈ [0,2/K] ∪ [2(K-1)/K+1,2]. Finally, we provide the optimal memory-rate tradeoff of the demand-private coded caching problem for 2 files and 3 users under arbitrary cache sizeM.

This paper proposes a novel algorithm to verify entropic vectors with probability mass functions parametrized and generated by neural networks. Given a target vector, we minimize the normalized distance by training a neural network, which reveals the entropic nature of the target, with the underlying distribution obtained accordingly. Empirical results demonstrate improved normalized distances and convergence performances compared with prior works. We also conduct optimizations of Ingleton score and Ingleton violation index, where a new lower bound of Ingleton violation index is obtained. An inner bound of the almost entropic region with four random variables is constructed with the proposed method, presenting the current best inner bound measured by the volume ratio.

We study the problem of distributed multi-user secret sharing (DMUSS), involving a main node, N storage nodes, and K users. Every user has access to the contents of a certain subset of storage nodes and wants to decode an independent secret message. With knowledge of K secret messages, the main node strategically places encoded shares in the storage nodes, ensuring two crucial conditions: (i) each user can recover its own secret message from the storage nodes that it has access to; (ii) each user is unable to acquire any information regarding the collection of$K-1$secret messages for all the other users. The rate of each user is defined as the size of its secret message normalized by the size of a storage node. We characterize the capacity region of the DMUSS problem, which is the closure of the set of all achievable rate tuples that satisfy the correctness and perfect secrecy conditions. The converse proof relies on a bound from the traditional single-secret sharing regime. In the achievability proof, we firstly design the linear decoding functions, based on the fact that each secret message needs to be recovered from a single set of storage nodes. It turns out that the perfect secrecy condition holds if K matrices, whose entries are extracted from the decoding functions, are full rank. We prove that the decoding functions can be constructed explicitly if the rate tuple satisfies the converse and the field size is not less than K. At last, the encoding functions are obtained by solving the system of linear decoding functions, where some shares are equal to the randomness and the other shares are linear combinations of the secret messages and the randomness.

In this paper, we study the problem of the 1-of-2 string oblivious transfer (OT) between Alice and Bob in the presence of a passive eavesdropper Eve. The eavesdropper Eve is not allowed to get any information about the private data of Alice or Bob. When Alice and Bob are honest-but-curious users, we propose a protocol that satisfies 1-private (neither Alice nor Bob colludes with Eve) OT requirements for the binary erasure symmetric broadcast channel, in which the channel provides dependent erasure patterns to Bob and Eve. We find that when the erasure probabilities of the channel are within a certain range, the derived lower and upper bounds on the wiretapped OT capacity meet. Our results generalize and improve upon the results on 1-private wiretapped OT capacity by Mishra et al. Finally, we propose a protocol for a larger class of wiretapped channels and derive a lower bound on the wiretapped OT capacity.

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.

Device-to-device (D2D) coded caching is an effective way to reduce the peak-time delivery rate of both the server and the users. It consists of two phases, the placement phase and the delivery phase. Most prior works on D2D coded caching are based on the assumption that all users will request content at the beginning of the delivery phase. However, in practice, this often times is not true. Motivated by this consideration, this paper formulates a new problem called the request-robust D2D coded caching, where the identity of the users making file requests are known only at the beginning of the delivery phase. For this novel D2D coded caching problem, we propose an achievable scheme based on uncoded cache placement and exploiting common demands and one-shot delivery. We show that the proposed scheme outperforms known D2D coded caching schemes applied to the request-robust scenario.

Entropy region is a set consisting of the entropic vector corresponding to every discrete probability distribution. Both its outer bound consisting of Shannon-type inequalities and inner bound consisting of the rank vectors corresponding to every arrangement of vector subspaces are closed under polymatroid duality. In 2018, Kaced proved that the closure of the entropy region is not closed under polymatroid duality for five or more discrete random variables, and the case of four discrete random variables is left as an open problem. In this paper, we give a definite answer to this open problem by proving via counter example that the closure of the entropy region is not closed under polymatroid duality for four discrete random variables either.

We propose a new D2D centralized coded caching problem, named the 3-user D2D coded caching with two random requesters and one sender (2RR1S), where in the delivery phase, any two of the three users will make file requests, and the user that does not make file request is the designated sender. We find the optimal scheme, denoted as the 2RRIS scheme, for any number of files$N$. To examine the usefulness of the proposed model and scheme, we adapt the 2RR1S scheme to three scenarios. The first one is the 3-user D2D coded caching model proposed by Ji et al. By characterizing the optimal rate-memory tradeoff for the 3-user D2D coded caching when$N=2$, we show that the adapted 2RR1S scheme is in fact optimal when the cache size is medium. The second scenario is request-random D2D coded caching. Adapting the 2RR1S scheme to this scenario, we show the superiority of our adapted scheme for medium to large cache size. The third scenario is K-user D2D coded caching with$K-s$random requesters and$s$senders, for which an achievability result is obtained by generalizing the 2RR1S scheme.

We study the secure distributed matrix multiplication (SDMM) problem under arbitrary collusion pattern. In the one-sided SDMM problem, where only one matrix of the matrix multiplication needs to be kept secure, we propose an achievable scheme that attains the optimal normalized download cost. The optimal scheme distributes a different number of encoded copies to each server, and the servers that collude more with others are given fewer encoded copies. The converse result is proved using Shearer’s lemma. In the two-sided SDMM problem under arbitrary collusion pattern, where the user would want to keep both matrices of the matrix multiplication secure, we provide an achievable scheme whose key parameters, including the method with which the random matrices are appended, the number of random matrices appended, the number of encoded copies generated, the number of encoded copies distributed to each server, are given by the proposed algorithm. We also demonstrate, via numerical results, the performance of the proposed scheme in terms of normalized upload-download cost trade-off, and show that it is much better than the current known scheme devised for the homogeneous collusion pattern.

We study the symmetric private information retrieval (SPIR) problem under arbitrary collusion and eavesdropping patterns for replicated databases. We find its capacity, which is the same as the capacity of the original SPIR problem with the number of serversNreplaced by a numberF*. The numberF* is the optimal solution to a linear programming problem, and it is a function of the joint pattern, which is the union of the collusion and eavesdropping pattern. This is the first result that shows how two arbitrary patterns collectively affect the capacity of the SPIR problem. We draw the conclusion that for SPIR problems, the collusion and eavesdropping constraints are interchangeable in terms of capacity, i.e., the two patterns play the same role in the SPIR problem and the capacity remains unchanged if we exchange the colluding and eavesdropping patterns. As corollaries of our result, the capacity of the SPIR problem under arbitrary collusion patterns, and the capacity of the PIR problem where each colluding set is included in some eavesdropping set, are also found. Some extensions with restrictions to finite message lengths are provided, and in this case, upper and lower bounds on the capacity are given. The lower bound is described with a solution to an integer linear programming problem.

We study the private information retrieval (PIR) problem under arbitrary collusion patterns for replicated databases. We find a general characterization of the PIR capacity, which is the same as the capacity of the original PIR problem with the number of databases N replaced by a number S*. S*is the optimal solution to a linear programming problem that is a function of the incidence matrix of the collusion pattern. Hence, the essence of any collusion pattern can be distilled into one number S*. In the proposed achievable scheme, databases are non-uniformly queried according to the optimal solution of a linear programming problem based on the collusion pattern. It can be seen that the databases who collude more with others are queried less. In the converse proof, Shearer's lemma is applied, in place of Han's inequality, to a linear combination of inequalities, where each inequality corresponds to one colluding set in the collusion pattern. The weights of the linear combination come from the optimal solution of another linear programming problem based on the collusion pattern. Finally, by noting the interesting fact that the two seemingly different linear programming problems, one used in the achievability proof and the other used in the converse proof, are in fact dual problems, we characterize the capacity of the PIR problem under arbitrary collusion patterns.

We study the private information retrieval (PIR) problem under arbitrary collusion patterns for replicated databases. We find its capacity, which is the same as the capacity of the original PIR problem with the number of databases N replaced by a number S*. The number S* is the optimal solution to a linear programming problem that is a function of the collusion pattern. Hence, the collusion pattern affects the capacity of the PIR problem only through the number S*.

In this work, we investigate the capacity of private information retrieval (PIR) from N replicated databases, where a subset of the databases are byzantine. We allow for multi-round queries and demonstrate that the identities of the byzantine databases can be determined with a small additional download cost. As a result, the capacity of the multi-round PIR with byzantine databases (BPIR) reaches that of the robust PIR problem when the number of byzantine databases is less than the number of trustworthy databases.

The centralized coded caching problem is studied for the two-user scenario, considering heterogeneous cache capacities at the users and private channels from the server to the users, in addition to a shared channel. Optimal caching and delivery strategies that minimize the worst-case delivery latency are presented for an arbitrary number of files. The converse proof follows from the sufficiency of file-index-symmetric caching and delivery codes, while the achievability is obtained through memory-sharing among a number of special memory-capacity pairs. The optimal scheme is shown to exploit the private link capacities by transmitting part of the corresponding user`s request in an uncoded fashion. When there are no private links, the results presented here improve upon the two known results in the literature, namely: 1) equal cache capacities and arbitrary number of files and 2) unequal cache capacities and two files. The results are then extended to the caching problem with heterogeneous distortion requirements.

In this paper, we study outer bounds on the capacity region of the downlink multicell processing model with finite backhaul capacity for the simple case of two base stations and two mobile users. It is modeled as a two-user multiple access diamond channel. It consists of a first hop from the central processor to the base stations via orthogonal links of finite capacity and the second hop from the base stations to the mobile users via a Gaussian interference channel. The outer bound is derived using the converse tools of the multiple access diamond channel and that of the Gaussian MIMO broadcast channel. Through numerical results, it is shown that our outer bound improves upon the existing outer bounds greatly in the medium backhaul capacity range, and as a result, the gap between the outer bounds and the rate of the time-sharing of the known achievable schemes is significantly reduced.

The centralized coded caching problem is studied under heterogeneous cache sizes and channel qualities from the server to the users, focusing on the two-user case. A server holding N files is considered to be serving two users with arbitrary cache capacities of M1and M2, and it is assumed that in addition to a shared common link, each user also has a private link from the server available during the delivery phase. Optimal caching and delivery strategies that minimize the worst-case delivery latency are presented for an arbitrary N. The converse proof benefits from Tian's observation that it suffices to consider file-index symmetric caching schemes, while the achievability is obtained through memory-sharing among certain special (M1, M2) pairs. The optimal scheme is shown to exploit the private link capacities by transmitting part of the corresponding user's request in an uncoded fashion. When there are no private links, the results presented here improve upon the two known results in the literature, namely, i) equal cache capacities and arbitrary number of files; and ii) unequal cache capacities and N = 2 files.

In this paper, we study the error exponent in the problem of lossless source coding with a helper. We use the inherently typical subset lemma to remove the Markov chain constraint in the proof of the converse and obtain an upper bound on the error exponent, which is very close to the existing lower bound. The proposed upper bound and the existing lower bound meet when the rate pair is close to the boundary of the optimal rate region.

In this paper, we study upper bounds on the sum capacity of the downlink multicell processing model with finite backhaul capacity for the simple case of 2 base stations and 2 mobile users. It is modeled as a two-user multiple access diamond channel. It consists of a first hop from the central processor to the base stations via orthogonal links of finite capacity, and the second hop from the base stations to the mobile users via a Gaussian interference channel. The upper bound is derived using the converse tools of the multiple access diamond channel and that of the Gaussian MIMO broadcast channel. Through numerical results, it is shown that our upper bound improves upon the existing upper bound greatly in the medium backhaul capacity range, and as a result, the gap between the upper bounds and the sum rate of the time-sharing of the known achievable schemes is significantly reduced.

We study the Ahslwede-Han problem of a pointto-point communication with partial state information available at the destination. For a class of channels, by establishing a tight converse, we show that the Wyner-Ziv compression of the channel state treating the destination's channel output as side information is optimal. This result is more general than the modulo-sum channel studied by Aleksic et al. and the symmetric binary erasure channel with two states studied by Tandon and Ulukus. Thus, for this more general class of channels, we prove the Ahlswede-Han conjecture.

In a system that performs both encryption and lossy compression, the conventional way is to compress first and then encrypt the compressed data. This separation approach has been proved to be optimal. In certain applications where sensitive information should be protected as early as possible, it is preferable to perform the encryption first and then compress the encrypted data, which leads to the concept of the reversed system. Johnson et al. proposed an achievable scheme for the reversed system, where a modulo-sum encryption is followed by a compression using the Wyner-Ziv distributed source coding with side information. However, in general, this reversed system performs worse than the conventional system in the sense that it requires more compression rate and secrecy key rate. In this paper, we propose a new achievable scheme for the reversed system, where the encryption is conducted by a permutation cipher, and then, the encrypted data is compressed using the optimal rate-distortion code. The proposed scheme can achieve the optimal compression rate and secret key rate. As a result, we show that reversing the order of the encryption and compression does not necessarily compromise the performance of an encryption-compression system. We show that the proposed system attains strong secrecy, and the information leakage vanishes exponentially.

In this paper, we study the problem of message authentication with two correlated sources observed by the legitimate transmitter and receiver as secret information. We consider an active adversary capable of the impersonation attack and the substitution attack. We are interested in minimizing the maximum probability of successful deception under the two attacks, where the minimization is over all authentication schemes by the legitimate transmitter and receiver and the maximization is over all attack strategies by the adversary. We propose a random coding based authentication scheme and obtain upper bound on the solutions of the above min-max problem for both attacks. We also show that the proposed random coding based scheme outperforms the separation-based scheme, i.e., private-key generation first using the correlated sources and then authentication with the private key. Finally, for the impersonation attack, we obtain a lower bound, which meet the upper bound. Therefore, we solve the min-max problem and characterize the optimal performance of the authentication system under impersonation attacks.

In this paper, we propose a permutation-based code for the wiretap channel. We begin with an arbitrary channel code from Alice to Bob and then perform a series of permutations to enlarge the code to achieve secrecy to Eve. We show that the proposed code achieves the same performance as the traditional random code, in the sense that it achieves the random coding bound for the probability of decoding error at Bob and an exponentially vanishing information leakage at Eve. Thus, the permutation-based code we propose offers an alternative method of code construction for the wiretap channel.

In this paper, we study the multiple access diamond channel, where each relay has cached a part of the message intended for the destination node. It is assumed that the cached information at the two relays are independent. We propose an achievability scheme and show that the scheme of sending correlated codewords through the multiple access channel with the superposition structure proposed for the multiple access diamond channel can be easily adapted to the case where there are cached information at the relays. We further show the optimality of our proposed scheme when the channel satisfies certain conditions. Under these conditions, it is suboptimal for the source node to inform each relay the cached message of the other relay to form common data, rather it is optimal to have no common data and use the cached message at each relay to form the correlated codewords.

In this paper, we study the probability of successful deception of an uncompressed biometric authentication system with side information at the adversary. It represents the scenario where the adversary may have correlated side information, e.g., a partial finger print or a DNA sequence of a relative of the legitimate user. We find the optimal exponent of the deception probability by proving both the achievability and the converse. Our proofs are based on a connection between the problem of deception with side information and the rate distortion problem with side information at both the encoder and the decoder.

In this paper, we study the capacity of the diamond channel. We focus on the special case where the channel between the source node and the two relay nodes are two separate links with finite capacities and the link from the two relay nodes to the destination node is a Gaussian multiple access channel. We call this model the Gaussian multiple access diamond channel. We first propose an upper bound on the capacity. This upper bound is a single-letterization of an $n$-letter upper bound proposed by Traskov and Kramer, and is tighter than the cut-set bound. As for the lower bound, we propose an achievability scheme based on sending correlated codes through the multiple access channel with superposition structure. We then specialize this achievable rate to the Gaussian multiple access diamond channel. Noting the similarity between the upper and lower bounds, we provide sufficient and necessary conditions that a Gaussian multiple access diamond channel has to satisfy such that the proposed upper and lower bounds meet. Thus, for a Gaussian multiple access diamond channel that satisfies these conditions, we have found its capacity.

In this paper, we study the probability of successful deception of an uncompressed biometric authentication system with side information at the adversary. It represents the scenario where the adversary may have correlated side information, e.g., a partial finger print or a DNA sequence of a relative of the legitimate user. We find the optimal exponent of the deception probability by proving both the achievability and the converse. Our proofs are based on the connection between the problem of deception with side information and the rate distortion problem with side information at both the encoder and decoder.

In the scenario of downlink multicell processing, for the case of two base stations and two mobile users, by viewing the problem as a multiple access diamond channel with two destinations, we propose an achievability scheme that combines both the achievability of correlated codewords into the multiple access channel and Marton's achievability for the general broadcast channel. Compared with previously known schemes, our scheme focuses more on exploiting the gain of correlation between the transmitted signals of the base stations. We demonstrate through examples that our proposed scheme outperforms known achievability schemes when the capacities of the backhaul links are in the medium range.

We study a two-transmitter two-receiver network where Receiver 1 can only hear the transmitted signal of Transmitter 1. Transmitter 1 has two messages, one of which is intended for Receiver 1 while both are intended for Receiver 2. Transmitter 2 has one message which is intended for Receiver 2. We call this channel model the Z channel with degraded message sets. For networks with the element of distributed encoding, it has been shown that when the multiple access link between the two encoders and the decoder satisfies the conditions proposed by Liu and Goldsmith, capacity results can be obtained for a variety of problems. In this paper, we generalize these conditions and show that for a larger class of multiple access links, the capacity region of the Z channel with degraded message sets can be characterized despite the presence of distributed encoding.

We study the Ahlswede-Han problem of single-user communication with partial state information available at the destination. For a class of channels, we show that the Wyner-Ziv compression of the channel state treating the receiver's channel output as side information is optimal. This result is more general than the modulo-sum channel studied by Aleksic et. al in 2009. Thus, for this more general class of channels, we prove the Ahlswede-Han conjecture.

Following the work of Liu and Goldsmith in 2009, we study a class of Z-interference channels that satisfy the shift-invariant condition but not the maximum entropy condition. We provide a new capacity region outer bound for this class of Z-interference channels. We show the tightness of the proposed outer bound by finding the capacity region of certain Z-interference channels which were not previously known.

In this paper, we study the capacity of the diamond channel. We focus on the special case where the channel between the source node and the two relay nodes are two separate links of finite capacity and the link from the two relay nodes to the destination node is a Gaussian multiple access channel. We call this model the Gaussian multiple access diamond channel. We first propose an upper bound on the capacity. This upper bound is a single-letterization of the n-letter upper bound proposed by Traskov and Kramer, which is tighter than the cut-set bound. Next, we provide a lower bound based on sending correlated codes through the multiple access channel. Since the upper and lower bounds take on similar forms, it is expected that they coincide for certain channel parameters. To show this, we further focus on the symmetric case where the separate links to the relays are of the same capacity and the power constraints of the two relays are the same. For the symmetric case, we give necessary and sufficient conditions that the upper and lower bounds meet. Thus, for a Gaussian multiple access diamond channel that satisfies these conditions, we have found its capacity.

We study the problem of secure communications over the multiple access channel where there is one eavesdropper in the system and the eavesdropper can only overhear the transmitted signal of one of the transmitters. This channel model can be seen as a special case of both scenarios currently studied in the literature for multiple access channels with secrecy constraints. In this simplified model, we obtain the secrecy capacity region if the multiple access channel satisfies certain conditions. We also compare the capacity regions of this special class of multiple access channels with and without secrecy constraints to illustrate the price paid for secrecy.

In the distributed coding of correlated sources, the problem of characterizing the joint probability distribution of a pair of random variables satisfying an n-letter Markov chain arises. The exact solution of this problem is intractable. In this paper, we seek a single-letter necessary condition for this n-letter Markov chain. To this end, we propose a new data processing inequality on a new measure of correlation through a spectral method. Based on this new data processing inequality, we provide a single-letter necessary condition for the required joint probability distribution. We apply our results to two specific examples involving the distributed coding of correlated sources: multiple-access channel with correlated sources and multiterminal rate-distortion region, and propose new necessary conditions for these two problems.

We study a special class of diamond channels which was introduced by Schein in 2001. In this special class, each diamond channel consists of a transmitter, a noisy relay, a noiseless relay and a receiver. We prove the capacity of this class of diamond channels by providing an achievability scheme and a converse. The capacity we show is strictly smaller than the cut-set bound. We note that there exists a duality between this diamond channel coding problem and the Kaspi-Berger source coding problem.

This paper studies the problem of secure communication over a wiretap channel where the transmitter and the legitimate receiver share a secret key, which is concealed from the eavesdropper. We find the secrecy capacity under this scenario. This result generalizes that of Yamamoto, which is applicable only to less noisy wiretap channels, to the general wiretap channel when no distortion is allowed at the legitimate receiver.

In this paper, we study secure communications over a two-user semi-deterministic broadcast channel, i.e., one of the receivers is connected to the transmitter through a deterministic channel. We consider the case where the deterministic receiver is also the eavesdropper for the other receiver's message. We derive the secrecy capacity region by showing that superposition encoding plus Gel'fand-Pinsker encoding is optimal. We find that due to the deterministic component of the channel, Gel'fand-Pinsker binning alone is enough to achieve perfect secrecy. We also compare our scheme with the capacity-achieving scheme of Marton for the semi-deterministic broadcast channel where there is no secrecy constraint.

The multi-terminal rate-distortion problem has been studied extensively. Notably, among these, Tung and House-wright have provided the best known inner and outer bounds for the rate region under certain distortion constraints. In this paper, we first propose an outer bound for the rate region, and show that it is tighter than the outer bound of Tung and Housewright. Our outer bound involves some n-letter Markov chain constraints, which cause computational difficulties. We utilize a necessary condition for the Markov chain constraints to obtain another outer bound, which is represented in terms of some single-letter mutual information expressions evaluated over probability distributions that satisfy some single-letter conditions