Executive Summary : | In today's digitally connected world, many people rely on cyberspace for various tasks, including downloading data from servers. To protect users from untrusted servers, privacy measures must be built into communication protocols. These protocols, known as Private Information Retrieval (PIR) protocols or schemes, do not reveal the identity of the desired file index to the servers. By designing a careful PIR protocol, we can achieve privacy of the desired file index from each server while allowing the desired file to be downloaded by the client from responses from all servers with as high a PIR rate as possible. The maximum possible PIR rate depends on the linear code used to distribute the file library and is called the PIR capacity for that storage code. This work focuses on three important sub-areas of information-theoretic private information retrieval: new optimal rate or near-optimal rate PIR schemes under special distributed storage models, MDS-PIR capacity, and lossy PIR, weak PIR, and private computation. New PIR schemes are designed based on recently identified star-product PIR schemes, which use new linear codes as storage codes. The second goal is to find the MDS-PIR capacity under collusion and design PIR schemes for storage codes. The third goal is to design privacy-preserving schemes with optimal or near-optimal rates for problems related to PIR problems like Private Intersection, Private Union, or weak-privacy or lossy-privacy. The outcomes of this project will enable novel theoretical insights into the field of Private Information Retrieval, which will play a major role in distributed, multi-terminal communication systems in a society where privacy of end users becomes an increasing concern. |