Special Topics on Privacy And Public Auditability — Event 3

A few slides to introduce the STPPA #3 event, including the context of the Privacy-Enhancing Cryptography (PEC) project, and the schedule of this particular event with three invited talks and one panel, which will cover the topics of private information retrieval, encrypted search and fully homomorphic encryption.

Abstract: Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrieval (PIR) schemes achieve polylogarithmic bandwidth per query, but require the server to perform linear computation per query, which is a deal breaker towards deployment. Several recent works showed, however, that by introducing a one-time, per-client, off-line preprocessing phase, an unbounded number of client queries can be subsequently served with sublinear online computation time per query (and the cost of the preprocessing can be amortized over the unboundedly many queries). Existing preprocessing PIR schemes (supporting unbounded queries), unfortunately, make undesirable tradeoffs to achieve sublinear online computation: they are either significantly non-optimal in online time or bandwidth, or require the servers to store a linear amount of state per client or even per query, or require polylogarithmically many non-colluding servers.

We propose a novel 2-server preprocessing PIR scheme that achieves ~sqrt(n) online computation per query and ~sqrt(n) client storage, while preserving the polylogarithmic online bandwidth of classical PIR schemes. Both the online bandwidth and computation are optimal up to a polylogarithmic factor. In our construction, each server stores only the original database and nothing extra, and each online query is served within a single round trip. Our construction relies on the standard LWE assumption. As an important stepping stone, we propose new, more generalized definitions for a cryptographic object called a Privately Puncturable Pseudorandom Set, and give novel constructions that depart significantly from prior approaches.

Joint work with Waqar Aqeel, Balakrishnan Chandrasekaran and Bruce Maggs. A more recent presentation (Youtube link) appears at Crypto 2021.

Abstract: End-to-end encrypted databases store and process data without ever being able to decrypt it. The widespread availability of practical encrypted databases would greatly improve the security and privacy of our data and would enable a wide array of other privacy-enhancing technologies. In this talk, I will describe the state-of-the-art in encrypted databases in both industry and research.

Abstract: As the world adopts Artificial Intelligence, the privacy risks are many. AI can improve our lives, but may leak our private data. Private AI is based on Homomorphic Encryption (HE), a new encryption paradigm which allows the cloud to operate on private data in encrypted form, without ever decrypting it, enabling private training and private prediction. Our 2016 ICML CryptoNets paper showed for the first time that it was possible to evaluate neural nets on homomorphically encrypted data and opened new research directions combining machine learning and cryptography. The security of Homomorphic Encryption is based on hard problems in mathematics involving lattices, a candidate for post-quantum cryptography. This talk will explain Homomorphic Encryption, Private AI, and explain HE in action.

Panel conversation with the speakers of the STPPA#3 event.