Two-Server Sublinear PIR with Symmetric Privacy and Statistical Security

Abstract. We propose a two-server private information retrieval (PIR) scheme that achieves sublinear communication complexity while providing symmetric privacy (the client’s query index is hidden from each server individually) and statistical security (the privacy guarantee holds against computationally unbounded servers). Prior two-server PIR schemes with sublinear communication typically rely on computational assumptions or provide weaker privacy guarantees. Our construction leverages combinatorial techniques and novel query encoding methods to achieve communication cost that grows only polylogarithmically in the database size. We provide formal security proofs and analyze the concrete efficiency of our scheme, demonstrating that it offers a practical alternative for settings where statistical security is required and two non-colluding servers are available.