Paper 2025/646

Secret-Key PIR from Random Linear Codes

Abstract

Private information retrieval (PIR) allows to privately read a chosen bit from an $$-bit database $$ with $$ bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing $$ into an encoded database $$, it suffices to access only $$ bits of $$ per query. This requires $$, and prohibitively large server circuit size. We consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding $$ depends on a client's short secret key. In this secret-key PIR (sk-PIR) model we construct a protocol with $$ communication, for any constant $$, from the Learning Parity with Noise assumption in a parameter regime not known to imply public-key encryption. This is evidence against public-key encryption being necessary for sk-PIR. Under a new conjecture related to the hardness of learning a hidden linear subspace of $$ with noise, we construct sk-PIR with similar communication and encoding size $$ in which the server is implemented by a Boolean circuit of size $$. This is the first candidate PIR scheme with such a circuit complexity.