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 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 servers $N$ replaced by a number $F^{*}$ . The number $F^{*}$ 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 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.

The paradigm-shifting developments of cryptography and information theory have focused on the privacy of data-sharing systems, such as epidemiological studies, where agencies are collecting far more personal data than they need, causing intrusions on patients’ privacy. To study the capability of the data collection while protecting privacy from an information theory perspective, we formulate a new distributed multiparty computation problem called privacy-preserving epidemiological data collection. In our setting, a data collector requires a linear combination of K users’ data through a storage system consisting of N servers. Privacy needs to be protected when the users, servers, and data collector do not trust each other. For the users, any data are required to be protected from up to E colluding servers; for the servers, any more information than the desired linear combination cannot be leaked to the data collector; and for the data collector, any single server can not know anything about the coefficients of the linear combination. Our goal is to find the optimal collection rate, which is defined as the ratio of the size of the user’s message to the total size of downloads from N servers to the data collector. For achievability, we propose an asymptotic capacity-achieving scheme when $E<N-1$, by applying the cross-subspace alignment method to our construction; for the converse, we proved an upper bound of the asymptotic rate for all achievable schemes when $E<N-1$. Additionally, we show that a positive asymptotic capacity is not possible when $E\ge N-1$. The results of the achievability and converse meet when the number of users goes to infinity, yielding the asymptotic capacity. Our work broadens current researches on data privacy in information theory and gives the best achievable asymptotic performance that any epidemiological data collector can obtain.

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.

D2D coded caching, originally introduced by Ji, Caire, and Molisch, significantly improves communication efficiency by applying the multi-cast technology proposed by Maddah-Ali and Niesen to the D2D network. 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 is often not the case. Motivated by this consideration, this paper formulates a new problem called request-robust D2D coded caching. The considered problem includes K users and a content server with access to N files. Only r users, known as requesters, request a file each at the beginning of the delivery phase. The objective is to minimize the average and worst-case delivery rate, i.e., the average and worst-case number of broadcast bits from all users among all possible demands. For this novel D2D coded caching problem, we propose a scheme based on uncoded cache placement and exploiting common demands and one-shot delivery. We also propose information-theoretic converse results under the assumption of uncoded cache placement. Furthermore, we adapt the scheme proposed by Yapar et al. for uncoded cache placement and one-shot delivery to the request-robust D2D coded caching problem and prove that the performance of the adapted scheme is order optimal within a factor of two under uncoded cache placement and within a factor of four in general. Finally, through numerical evaluations, we show that the proposed scheme outperforms known D2D coded caching schemes applied to the request-robust scenario for most cache size ranges.