Welcome to the resource topic for 2025/646
Title:
Secret-Key PIR from Random Linear Codes
Authors: Caicai Chen, Yuval Ishai, Tamer Mour, Alon Rosen
Abstract:Private information retrieval (PIR) allows to privately read a chosen bit from an N-bit database x with o(N) bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing x into an encoded database \hat x, it suffices to access only polylog(N) bits of \hat x per query. This requires |\hat x|\ge N\cdot polylog(N), and prohibitively large server circuit size.
We consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding \hat x depends on a client’s short secret key. In this secret-key PIR (sk-PIR) model we construct a protocol with O(N^\epsilon) communication, for any constant \epsilon>0, 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 \mathbb{F}_2^n with noise, we construct sk-PIR with similar communication and encoding size |\hat x|=(1+\epsilon)\cdot N in which the server is implemented by a Boolean circuit of size (4+\epsilon)\cdot N. This is the first candidate PIR scheme with such a circuit complexity.
ePrint: https://eprint.iacr.org/2025/646
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .