Paper 2026/1051

Streamlined Symmetric Private Information Retrieval via Rényi Divergence

Abstract

Private Information Retrieval (PIR) protocols allow a client to recover items from a server-held database without revealing the locations of requested items. In Symmetric PIR (SPIR), the client also learns nothing about the database beyond the requested items. Such schemes are critical for maintaining security in applications such as compromised credential checking, where database elements are considered as sensitive as queries. Existing approaches to building SPIR schemes require running multiple cryptographic primitives in parallel. Moreover, they do not naturally translate to the post-quantum setting, even though practical PIR schemes are typically post-quantum due to their reliance on learning with errors (LWE). This work explores the possibility of deriving SPIR from PIR directly, utilising noise flooding to maintain the privacy of the database. While the common analysis based on the statistical distance leads to impractical parameters, we instead utilise arguments based on the Rényi divergence to obtain significantly improved parameters. We obtain simple single-server SPIR from state-of-the-art LWE-based PIR schemes with polynomial noise dimension and ciphertext modulus (concretely of 64 bits in size). Along the way, we note that practical schemes that utilise preprocessing via client-downloaded offline hints require extra protections for the database. Overall, via an implementation of our approach, we show that post-quantum, round-optimal SPIR schemes can be constructed requiring online communication of 8 MB and server computation costs of 302 ms for a database of 1 million 1 kB elements.