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

点击翻译按钮获取中文摘要

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.