SaTC: CORE: Small: Batch Techniques for Practical Private Information Retrieval

私有信息检索（PIR）是一种加密原语，它解决了让用户从不受信任的远程数据库服务器获取记录而不让这些服务器了解用户正在获取哪些记录的看似不可能的问题。关于PIR的研究文献是巨大的;二十多年来，密码学，隐私和理论研究社区已经从各种角度深入研究了PIR; PIR的引人注目的应用在由此产生的研究文献中比比皆是。唉，尽管有一系列重大进展，现有的PIR技术仍然是出了名的低效，研究文献中提出的众多基于PIR的应用程序中没有一个被大规模部署，以保护用户的隐私“在野外”。该项目需要一个综合的研究议程，耦合一个强大的理论组成部分，一个雄心勃勃的实践组件围绕开发，分析和实施新的“批处理”IT-PIR技术，这可能会减轻所谓的信息理论私人信息检索（IT-PIR），性能最好，研究最多的PIR协议类别的“高昂的成本”问题。除了提高性能，新的批处理技术还提高了PIR的“表现力”，提供直观的API，应用程序可以通过这些API安全、轻松、高效地与IT-PIR协议进行交互。PIR长期以来在理论上为一系列重要问题提供了令人信服的解决方案，但在实践中很少采用，部分原因是现有技术的效率低下和表现力有限。实际上，传统的PIR构造通过对记录的索引进行编码（即，其相对于数据库中其他记录的物理位置）。这个项目建立在PI的初步结果的基础上，PI扩展了基本功能，不仅让用户获取多个记录（即，“一批”记录），其成本低于单独提取每个记录的成本，而且还允许用户使用指定他们寻找哪些数据的“上下文”查询来提取这样的一批记录，而不是指定那些数据恰好驻留在数据库中的位置的“位置”查询。主要的研究目标是（i）开发理论框架，以更好地理解批量IT-PIR的数学基础，（ii）使用从这些框架中获得的见解来改进和推广已知的结构，以及（iii）使用改进的结构来实现实用的，尊重隐私的替代方案，以选择现有的隐私不可知的产品和服务。新的批量IT-PIR构造将被纳入开源珀西++库，这将使研究生和本科生都深入参与。

Private information retrieval (PIR) is a cryptographic primitive that solves the seemingly impossible problem of letting users fetch records from untrusted and remote database servers without letting those servers learn which records the users are fetching. The research literature on PIR is vast; for over two decades, the cryptography, privacy, and theory research communities have studied PIR intensively and from a variety of perspectives; compelling applications for PIR abound in the resulting research literature. Alas, despite a series of significant advances, existing PIR techniques remain notoriously inefficient and none of the numerous PIR-based applications proposed in the research literature have been deployed at scale to protect the privacy of users "in the wild". This project entails an integrated research agenda that couples a strong theoretical component with an ambitious practical component centered around developing, analyzing, and implementing novel "batch" IT-PIR techniques, which can potentially alleviate the "prohibitive cost" problem for so-called information-theoretic private information retrieval (IT-PIR), the most performant and well-studied category of PIR protocols. Beyond improving performance, the new batch techniques also improve the "expressiveness" of PIR, exposing intuitive APIs through which applications can safely, easily, and efficiently interact with IT-PIR protocols.PIR has long provided compelling solutions in theory to a wide array of important problems, but it has seen little adoption in practice due in part to the inefficiency and limited expressiveness of existing techniques. Indeed, traditional PIR constructions let users fetch just one data record at a time by encoding the record's index (i.e., its physical locations relative to the other records in the database) in a cryptographically protected query. This project builds on preliminary results by the PI, which extend that basic functionality to not only let users fetch several records (i.e., a "batch" of records) for a lower cost than that of fetching each record separately, but also to let users fetch such batches of records using "contextual" queries that specify which data they seek, as opposed to "positional" queries that specify where those data happen to reside in the database. The main research goals are to (i) develop theoretical frameworks to better understand the mathematics underlying batch IT-PIR, to (ii) use insights gained from these frameworks to improve upon and generalize the known constructions, and to (iii) use the improved constructions to implement practical, privacy-respecting alternatives to a selection of existing privacy-agnostic products and services. The new batch IT-PIR constructions will be incorporated into the open-source Percy++ library, an effort which will deeply involve both graduate and undergraduate students.