October 14-18, 2024 | Ling Ren, Muhammad Haris Mughees, I Sun
This paper presents simple and practical amortized sublinear stateful private information retrieval (PIR) schemes that avoid the drawbacks of existing approaches, such as large client storage, high communication, and poor practical efficiency. The proposed schemes use a new technique involving dummy subsets to eliminate information leakage and ensure correctness. The schemes work with two non-colluding servers or a single server, achieving practical efficiency. For a database with $2^{28}$ entries of 32-byte, each query of the two-server scheme consumes 34 KB of communication and 2.7 milliseconds of computation, while each query of the single-server scheme consumes amortized 47 KB of communication and 4.5 milliseconds of computation. These results are one or more orders of magnitude better than prior works. The schemes achieve constant online response overhead, take milliseconds of computation, rely only on pseudorandom functions, and have no restrictions on client queries. The paper also provides a detailed analysis of the correctness and privacy of the schemes, as well as an efficiency analysis comparing the two-server and single-server schemes.This paper presents simple and practical amortized sublinear stateful private information retrieval (PIR) schemes that avoid the drawbacks of existing approaches, such as large client storage, high communication, and poor practical efficiency. The proposed schemes use a new technique involving dummy subsets to eliminate information leakage and ensure correctness. The schemes work with two non-colluding servers or a single server, achieving practical efficiency. For a database with $2^{28}$ entries of 32-byte, each query of the two-server scheme consumes 34 KB of communication and 2.7 milliseconds of computation, while each query of the single-server scheme consumes amortized 47 KB of communication and 4.5 milliseconds of computation. These results are one or more orders of magnitude better than prior works. The schemes achieve constant online response overhead, take milliseconds of computation, rely only on pseudorandom functions, and have no restrictions on client queries. The paper also provides a detailed analysis of the correctness and privacy of the schemes, as well as an efficiency analysis comparing the two-server and single-server schemes.