SaTC: CORE: Small: Communication-Efficient, Fault-Tolerant Private Information Retrieval over Erasure Coded Storage

许多隐私保护应用（诸如匿名消息、私有数据库查询、加密搜索和隐私保护广告）需要实现允许客户端读取或写入数据库（由一个或多个服务器托管）而不向服务器揭示数据库中的哪个项目被读取/写入的协议。为了做到这一点，许多应用程序使用了一个重要的加密原语，称为私有信息检索（PIR），它允许客户端从不受信任的数据存储中检索值，这样存储服务器就不会知道正在检索哪个值。当考虑实际使用时，现有方法在通信、存储和计算效率以及容错方面具有若干显著缺点。该项目的创新之处是为多台服务器上托管的数据库的私有读写开发新的PIR协议，并同时实现通信和存储开销的效率，以及对故障停止和拜占庭故障的容错。该项目的更广泛的意义和重要性是通过算法技术改进私人信息检索的重要方面，这些技术可以用于利用PIR的真实的应用程序，并使这些应用程序更有效，可扩展和实用。研究人员计划在两个方面解决研究问题。第一个推力集中在设计容错，通信效率的分布式点功能计划，这将有助于设计查询，可以在以后用于PIR读/写。第二个重点将建立在第一个重点的分布式点功能设计的基础上，以创建端到端PIR协议，用于在擦除编码存储上实现不经意的读取和写入。这个奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many privacy-preserving applications such as anonymous messaging, private database querying, encrypted search, and privacy-preserving advertising require implementing protocols that allow a client to read or write to a database (hosted by one or more servers) without revealing to the servers which item in the database was read/written. To do so, many applications make use of an important cryptographic primitive called private information retrieval (PIR), which allows clients to retrieve values from an untrusted data storage such that the storage servers do not learn anything about which value is being retrieved. When considered for practical usage, existing approaches have several significant drawbacks in terms of communication, storage, and computation efficiency, as well as fault tolerance. This project’s novelties are to develop new PIR protocols for both private reads and writes to a database hosted on multiple servers, and to simultaneously achieve efficiency in communication and storage overheads, as well as being fault-tolerant against fail-stop and Byzantine failures. This project’s broader significance and importance are to improve important aspects of private information retrieval via algorithmic techniques, which can be used in real world applications that leverage PIR, and make these applications more efficient, scalable, and practical.The team of researchers plan to address the research question in two thrusts. The first thrust focuses on designing fault-tolerant, communication-efficient distributed point function schemes, which will help the design of queries that can be later used for PIR reads/writes. The second thrust will build upon the distributed point function designs from the first thrust to create end-to-end PIR protocols for enabling oblivious reads and writes over erasure-coded storage. The team is planning to open source the framework for other researchers and educators.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.