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

CIF：小：从私人信息检索的角度看隐私、安全、结构和一致性的基本限制

• 批准号: 1907053
• 负责人: Syed Jafar
• 金额: $ 50万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1907053&HistoricalAwards=false
• 关键词: CIF; Small; Fundamental; Limits; Privacy

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.

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

项目成果

On the Asymptotic Capacity of X -Secure T -Private Information Retrieval With Graph-Based Replicated Storage

基于图的复制存储的X-Secure T-Private信息检索的渐进能力

• DOI: 10.1109/tit.2020.3011053
• 发表时间: 2020-10
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Jia, Zhuqing;Jafar, Syed Ali
• 通讯作者: Jafar, Syed Ali

X -Secure T -Private Federated Submodel Learning With Elastic Dropout Resilience

具有弹性辍学弹性的 X -Secure T -Private 联合子模型学习

• DOI: 10.1109/tit.2022.3165400
• 发表时间: 2022-08
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Jia, Zhuqing;Jafar, Syed Ali
• 通讯作者: Jafar, Syed Ali

The Capacity of T -Private Information Retrieval With Private Side Information

T-私有信息检索的能力

• DOI: 10.1109/tit.2020.2977919
• 发表时间: 2020-08
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Chen, Zhen;Wang, Zhiying;Jafar, Syed Ali
• 通讯作者: Jafar, Syed Ali

Cross Subspace Alignment Codes for Coded Distributed Batch Computation

用于编码分布式批量计算的跨子空间对齐代码

• DOI: 10.1109/tit.2021.3064827
• 发表时间: 2019-09-30
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Zhuqing Jia;S. Jafar
• 通讯作者: S. Jafar

GCSA Codes With Noise Alignment for Secure Coded Multi-Party Batch Matrix Multiplication

用于安全编码多方批量矩阵乘法的具有噪声对齐的 GCSA 代码

• DOI: 10.1109/jsait.2021.3052934
• 发表时间: 2021-03-01
• 期刊: IEEE Journal on Selected Areas in Information Theory
• 作者: Zhen Chen;Zhuqing Jia;Zhiying Wang;S. Jafar
• 通讯作者: S. Jafar