SPIRAL: Fast, High-Rate Single-Server PIR via FHE Composition

Abstract

We introduce the SPIRAL family of single-server private information retrieval (PIR) protocols. SPIRAL relies on a composition of two lattice-based homomorphic encryption schemes: the Regev encryption scheme and the GentrySahai-Waters encryption scheme. We introduce new ciphertext translation techniques to convert between these two schemes and in doing so, enable new trade-offs in communication and computation. Across a broad range of database configurations, the basic version of SPIRAL simultaneously achieves at least a 4.5 × reduction in query size, 1.5 × reduction in response size, and 2 × increase in server throughput compared to previous systems. A variant of our scheme, SPIRALSTREAMPACK, is optimized for the streaming setting and achieves a server throughput of 1.9 GB/s for databases with over a million records (compared to 200 MB/s for previous protocols) and a rate of 0.81 (compared to 0.24 for previous protocols). For streaming large records (e.g., a private video stream), we estimate the monetary cost of SPIRALSTREAMPACK to be only 1.9 × greater than that of the no-privacy baseline where the client directly downloads the desired record.