Paper 2026/2804

Actively Secure PIR from Verifiable Linear Relations over Rings

Abstract

Privately retrieving data from a database without revealing which element is being retrieved is a fundamental problem in cryptography with many diverse applications. State-of-the-art solutions to this problem are generally based on homomorphic encryption, which offers security only against passive adversaries. In this work, we contribute to the recently introduced notion of Verifiable Private Information Retrieval (vPIR), which leverages verifiable computation to achieve security against active adversaries. We present a new sum-check based interactive oracle proof for linear relations over power-of-two cyclotomic rings, and show how to instantiate it into a vPIR protocol using Ring-LWE. Our solution is concretely efficient, offers the best possible security guarantees and is plausibly post-quantum secure. We additionally provide an open-source Rust implementation. Our server time improves on prior work's IOP by more than an order of magnitude, leading to a factor two end-to-end performance improvement. Compared to vPIR prior work, on a 4 GiB database, our offline communication and client storage are of 128 MiB, against 3.29 GiB. Preprocessing is run once per database and amortized over an unbounded number of queries.