CIF: Small: Fundamental Limits of Privacy, Security, Structure and Alignment through the Lens of Private Information Retrieval

University Of California-Irvine, Irvine CA

Investigators

Abstract

Privacy is widely recognized as a fundamental human right. Other societal freedoms such as the freedom of association and freedom of speech are built upon it. Motivated by increasing privacy concerns in the modern era of big data, distributed storage and cloud computing, this project focuses on the problem of Private Information Retrieval (PIR) where the goal is to allow users to efficiently retrieve desired records from remotely stored datasets without revealing any information to the servers about which records are desired, even if the servers are computationally unbounded. The capacity of PIR is the fundamental limit on the number of bits of desired information that can be retrieved per bit of total download from all servers. It is important to study PIR not only because privacy is important, but also because PIR has deep connections to a number of other important open problems in theoretical computer science and cryptography, coding and signal processing, and wireless communications and network information theory. Fundamental advances in PIR are likely to have a ripple effect on these related problems. The project is comprised of seven research thrusts centered around the capacity of PIR with upload constraints, data dependencies, partial privacy, limited computation, data security, coded storage, and the dualities that allow exchange of ideas across different problems that are connected through PIR. While the thrusts are motivated by challenges that are critical to the success of PIR, the significance of each of these thrusts extends beyond PIR. Capacity of PIR with upload constraints is a stepping stone for characterizing the information theoretic limits of locally decodable codes. PIR with data dependencies addresses the challenge of jointly exploiting both common information and interference alignment in distributed compression of downloads from multiple servers. Partial privacy examines the robustness of symmetric solutions to perturbations in symmetry. PIR with limited computation leads to locally decodable codes that are also locally encodable. Security constraints bring secret sharing into the picture and the combination of security with privacy constraints leads to new interference alignment schemes. PIR formulations with various coded storage constraints reveal insights into optimal distributed storage structures, and dualities allow PIR solutions to be applied to other related problems, such as oblivious transfer, instance hiding, batch codes, secret sharing, secure computation, locally decodable codes, and blind interference alignment. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.