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.