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解决方案应用于其他相关问题，例如遗忘传输、实例隐藏、批处理代码、秘密共享、安全计算、本地可解码代码和盲干扰对齐。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.