Paper 2026/1959

Information-theoretic two-server PIR requires $(6-o(1))\log n$ bits of communication

Abstract

We prove that every information-theoretic two-server private information retrieval scheme for $n$-bit databases requires $(6-o(1))\log n$ bits of communication. This improves on the $5$ of Wehner and de Wolf (ICALP 2005), who had raised the $4.4$ of Kerenidis and de Wolf (STOC 2003), who in turn had raised Mann's original $4$ (M.Sc.\ thesis, 1998). Our proof follows the quantum route of the earlier bounds: encode the database in a quantum state, recover an entry from enough copies of it, and apply Nayak's bound (FOCS 1999) on quantum random access codes. Previous proofs read that entry as a binary outcome with a small bias toward the correct answer, and pay the inverse square of that bias to amplify it. We instead allow a real-valued outcome whose mean is the correct answer, and pay only its second moment. The same readout strategy improves the other lower bounds of Wehner and de Wolf, for smooth codes and locally decodable codes. In particular, it drops the linearity assumption in the lower bounds of Goldreich, Karloff, Schulman, and Trevisan (CCC 2002) almost for free.