Simple and Practical Amortized Sublinear Private Information Retrieval using Dummy Subsets

Recent works in amortized sublinear Private Information Retrieval (PIR) have demonstrated great potential. Despite the inspiring progress, existing schemes in this new paradigm are still faced with various challenges and bottlenecks, including large client storage, high communication, poor practical efficiency, need for non-colluding servers, or restricted client query sequences. We present simple and practical amortized sublinear stateful private information retrieval schemes without these drawbacks using new techniques in hint construction and usage. In particular, we introduce a dummy set to the client's request to eliminate any leakage or correctness failures. Our techniques can work with two non-colluding servers or a single server. The resulting PIR schemes achieve practical efficiency. The online response overhead is only twice that of simply fetching the desired entry without privacy. For a database with 2^28 entries of 32-byte, each query of our two-server scheme consumes 34 KB of communication and 2.7 milliseconds of computation, and each query of our 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.