Paper 2026/1480

Doubly-Efficient Secret-Key PIR with Low Storage Overhead

Abstract

In secret-key private information retrieval, a client with a short secret key retrieves a database item while hiding the requested index, and possibly also the database, from the server. The server answers using an encoded version of the database, generated via one-time preprocessing. Secret-key PIR provides an attractive "stateless" alternative to stateful PIR and oblivious RAM, and can be viewed as strengthening the standard notion of searchable symmetric encryption by not allowing any access pattern leakage. We give the first candidate doubly-efficient secret-key PIR schemes that achieve a constant multiplicative storage overhead, asymptotically approaching 1 in natural regimes, together with $k^{o(1)}$ communication and online server work for a database of size $k$. The best previous online server work with constant storage overhead was $k/\textrm{polylog}(k)$. Our constructions follow the permuted-code blueprint for doubly efficient sk-PIR (Boyle-Ishai-Pass-Wootters and Canetti-Holmgren-Richelson, TCC 2017), and are based on similar assumptions. The main novelty is that we instantiate this blueprint using new families of "$t$-smooth" locally decodable codes with improved tradeoffs between rate, locality, and smoothness. This includes a new $t$-smooth local decoder for Reed-Muller codes using concatenated curves, as well as a construction based on curve-lifted codes that has attractive concrete efficiency features. We perform extensive cryptanalysis of the underlying assumptions and benchmark performance under realistic parameters, demonstrating the practicality of our schemes. A representative instantiation encodes a $37$ GB database of $18$-bit records with only $4.2$× storage overhead, while requiring the server to read less than $600$ KB from the encoded database per query.