October 14–18, 2024 | Ling Ren, Muhammad Haris Mughees, I Sun
This paper presents a simple and practical amortized sublinear stateful private information retrieval (PIR) scheme that overcomes the limitations of existing schemes, such as large client storage, high communication costs, and poor practical efficiency. The authors introduce a dummy subset to eliminate leakage and correctness failures in client requests. The proposed techniques can be applied to both two non-colluding servers and a single server, achieving constant online response overhead and sublinear client storage and computation. The scheme is evaluated using an implementation in C++, demonstrating significant improvements over prior works in terms of client storage, communication, and computation efficiency. For a database with 2^38 entries of 32 bytes, the two-server scheme consumes 34 KB of communication and 2.7 milliseconds of computation per query, while the single-server scheme consumes 47 KB of communication and 4.5 milliseconds of computation per query. These results are one or more orders of magnitude better than those of prior works.This paper presents a simple and practical amortized sublinear stateful private information retrieval (PIR) scheme that overcomes the limitations of existing schemes, such as large client storage, high communication costs, and poor practical efficiency. The authors introduce a dummy subset to eliminate leakage and correctness failures in client requests. The proposed techniques can be applied to both two non-colluding servers and a single server, achieving constant online response overhead and sublinear client storage and computation. The scheme is evaluated using an implementation in C++, demonstrating significant improvements over prior works in terms of client storage, communication, and computation efficiency. For a database with 2^38 entries of 32 bytes, the two-server scheme consumes 34 KB of communication and 2.7 milliseconds of computation per query, while the single-server scheme consumes 47 KB of communication and 4.5 milliseconds of computation per query. These results are one or more orders of magnitude better than those of prior works.