The team explored and carefully studied various aspects of private information retrieval primitive, and push forward significantly on the fundamental theory of this security primitive via the proposed holistic view. New information-theoretic limits have been identified, and novel code designs have been proposed. The team obtained significant results on the following three specific areas. Firstly, on the study of the tradeoff between the storage and download cost, the team developed a Shannon-theoretic approach and provided new coding techniques based on this approach. This approach provides a unified view on the classical information-theoretic coding schemes and more modern code designs in the context of private information retrieval, and it is a significant theoretic achievement. The team further utilized the computer-based information-theoretic approach to study this problem, and obtained novel representation of the fundamental limit, as well as new improved bounds on the tradeoff. Secondly, on the tradeoff between privacy leakage and the download cost, sometimes referred to as weakly private information retrieval or leaky private information retrieval, the team quantitatively studied the leakage under different measures, such as the maximal leakage, mutual information, and differential privacy, and obtained efficient optimized code designs under these settings. The settings were further generalized to allow the servers to be heterogeneously trusted, where novel codes were proposed that can utilize such heterogeneity with significant gain. Thirdly, the team studied private information retrieval with multiple level of privacy requirements. The problem formulation by itself is non-trivial, where the levels were carefully quantified by different numbers of colluding servers in such systems. Novel code designs were proposed for this setting, which shows significant improvement over the baseline approach of ignoring these different levels of privacy requirements. The project led to 4 published journal papers and 1 journal submission, and 4 published conference paper and 1 conference paper submission.

Multiple graduate students have been trained in the context of this project. In particularly, two female M.S. students were involved and trained, and one of them is continuing her Ph.D. study in PI's group. These students gained significant experience in rigorous reasoning, optimization, and information theory by participating in this project. 

Last Modified: 01/07/2025
Modified by: Chao Tian