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

隐私被广泛认为是一项基本人权。其他社会自由，如结社自由和言论自由，都建立在它的基础上。在大数据、分布式存储和云计算的现代时代，人们对隐私的关注日益增加，本项目主要研究私有信息检索（PIR）问题目标是允许用户从远程存储的数据集中有效地检索所需的记录，而不会向服务器泄露任何有关记录是期望的，即使服务器在计算上是无界的。 PIR的容量是对从所有服务器下载的总数据中每比特可以检索的所需信息的比特数的基本限制。研究PIR很重要，不仅因为隐私很重要，而且因为PIR与理论计算机科学和密码学，编码和信号处理，无线通信和网络信息理论中的许多其他重要开放问题有着深刻的联系。PIR的根本性进展可能会对这些相关问题产生涟漪反应。该项目由七个研究重点组成，围绕PIR的上传限制，数据依赖性，部分隐私，有限计算，数据安全性，编码存储以及允许通过PIR连接的不同问题交换想法的二元性。虽然这些推动力是由对PIR成功至关重要的挑战所推动的，但这些推动力中的每一个的意义都超出了PIR。具有上载约束的PIR的容量是刻画局部可译码码的信息论极限的基础。具有数据依赖性的PIR解决了在来自多个服务器的下载的分布式压缩中联合利用公共信息和干扰对齐的挑战。部分隐私检查对称扰动的对称解决方案的鲁棒性。有限计算的PIR导致局部可解码的代码也是局部可编码的。安全约束将秘密共享引入到图像中，安全性与隐私约束的结合导致新的干扰对齐方案。具有各种编码存储约束的PIR公式揭示了对最佳分布式存储结构的见解，并且对偶允许PIR解决方案应用于其他相关问题，例如不经意传输，实例隐藏，批处理代码，秘密共享，安全计算，本地可解码代码，该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的学术价值和更广泛的影响审查标准。

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.