Secret-Key PIR from Random Linear Codes

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 x, it suffices to access only polylog(N) bits of x per query. This requires |x|≥ N· polylog(N), and even larger server circuit size.