Fast Protocols for Secret-Key Private Information Retrieval

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 bx, it suffices to access only polylog(N ) bits of bx per query. This requires |bx| ≥ N · polylog(N ), and even larger server circuit size. In Chapter 2, we consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding bx depends on a client’s short secret key. In this secret-key PIR (sk-PIR) model, we construct a protocol with O(N ε) communication, for any constant ε > 0, under 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 conjectures related to the hardness of learning a hidden linear subspace of F^n_2 with noise, we construct sk-PIR with similar communication and encoding size |bx| = (1 + ε) ·N in which the server is implemented by a Boolean circuit of size (4 + ε) · N . This is the first candidate PIR scheme with such a circuit complexity. In Chapter 3, observing that the fine-grained security setting, where the adversary’s runtime is bounded by a fixed polynomial in the input size, enables meaningful efficiency gains in our context, we design and implement the first practical doubly efficient secret-key PIR scheme based on the protocol proposed by Boyle et al. and Canetti et al. (TCC 2017). In addition, we propose several optimizations that significantly improve the cost of the original approach. Setting for relaxed security, our implementation offers a stateless client, a lightweight online phase, near optimal download rate, and scalability to large databases, outperforming recent works on practical PIR with preprocessing.