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

许多保护隐私的应用程序，如匿名消息传递、私有数据库查询、加密搜索和保护隐私的广告，都需要实现协议，允许客户端读取或写入数据库（由一个或多个服务器托管），而不会向服务器透露数据库中的哪个条目被读取/写入。为此，许多应用程序使用一种重要的加密原语，称为私有信息检索（PIR），它允许客户机从不受信任的数据存储中检索值，这样存储服务器就不知道正在检索的是哪个值。当考虑到实际应用时，现有的方法在通信、存储、计算效率以及容错性方面存在几个明显的缺点。该项目的新颖之处在于开发新的PIR协议，用于对托管在多个服务器上的数据库进行私有读写，同时实现通信和存储开销的效率，以及对故障停止和拜占庭故障的容错。该项目更广泛的意义和重要性在于通过算法技术改进私有信息检索的重要方面，这些技术可用于利用PIR的现实世界应用程序，并使这些应用程序更高效、可扩展和实用。研究小组计划通过两个重点来解决这个研究问题。第一个重点是设计容错、通信高效的分布式点函数方案，这将有助于设计可用于PIR读/写的查询。第二次推力将建立在第一次推力的分布式点函数设计的基础上，以创建端到端PIR协议，以便在擦除编码存储上实现遗忘读写。该团队计划将该框架开源给其他研究人员和教育工作者。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.