SaTC: CORE: Small: Practical Private Information Retrieval

私有信息检索（PIR）是保护用户在线隐私的最基本的密码学原语之一。它有许多应用程序，包括匿名通信，隐私保护媒体流和安全浏览的私人查找。PIR还与其他重要的隐私保护密码工具密切相关，例如已用于密码监控和有害内容发现的私有集交集。 经过几十年的研究，单服务器PIR方案仍然存在性能限制。主要瓶颈包括高通信成本、繁重的计算和庞大的服务器存储。如果数据库有许多条目，但每个条目都很小，则性能会进一步恶化--这是实际应用程序中的常见情况。不幸的是，这些障碍中有许多是PIR标准制定中的根本性障碍。该项目提出了单服务器PIR的新范例，包括同态加密组合，矢量化批量PIR和有状态PIR。其目标是在通信、计算、存储和支持的数据库参数范围等各个方面实质性地改进单服务器PIR，最终使其适用于广泛的实际应用。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Private information retrieval (PIR) is one of the most fundamental cryptographic primitives to protect user privacy online. It has many applications including anonymous communication, privacy-preserving media streaming, and private look-ups for safe browsing. PIR is also closely related to other important privacy-preserving cryptographic tools, such as private set intersection, which has been used in password monitoring and harmful content discovery. After decades of research, single-server PIR schemes still have performance limitations. The main bottlenecks include high communication costs, heavy computation, and large server storage. The performance further worsens if the database has many entries but each individual entry is small -- a common scenario in real-world applications. Unfortunately, many of these obstacles are fundamental in the standard setting of PIR. This project presents new paradigms for single-server PIR, including homomorphic encryption composition, vectorized batch PIR, and stateful PIR. The goal is to substantially improve single-server PIR in all aspects: communication, computation, storage, and range of supported database parameters, to eventually make it practical for a wide range of real-world applications.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.