Welcome to the resource topic for 2023/1619
Title:
Encode and Permute that Database! Single-Server Private Information Retrieval with Constant Online Time, Communication, and Client-Side Storage
Authors: Shuaishuai Li, Weiran Liu, Liqiang Peng, Cong Zhang, Xinwei Gao, Aiping Liang, Lei Zhang, Dongdai Lin, Yuan Hong
Abstract:Private Information Retrieval (PIR) facilitates the retrieval of database entries by a client from a remote server without revealing which specific entry is being queried. The preprocessing model has emerged as a significant technique for constructing efficient PIR systems, allowing parties to execute a one-time, query-independent offline phase, and then a fast online retrieval phase. In particular, Corrigan-Gibbs and Kogan (EUROCRYPT 2020) presented a new framework for constructing PIR with sublinear online time. Nevertheless, their protocol is deemed impractical in the single-server setting due to the heavy use of Fully Homomorphic Encryption (FHE). More recently, two state-of-the-art (SOTA) single-server PIR protocols (Zhou et al., S&P 2024 and Mughees-Ren, ePrint 2023) have eliminated FHE, at the price of linear offline communication. However, the client-side storage is still relatively large (\tilde{O}(\sqrt{n})), which poses challenges to practical deployment, especially when the client has limited computation and storage capabilities. To address such limitation, we propose a novel PIR protocol Pai, which only requires constant online time, communication, and client-side storage. The price we pay is only a 1 - 5\times increase in offline communication, which would be acceptable since it is a one-time cost.Building upon our Pai, we also present a Symmetric KPIR (KSPIR) PaiKSPIR and a Chargeable KSPIR (CKSPIR) PaiCKSPIR. These two variants of PIR offer enhanced functionalities while maintaining computational complexities similar to the original Pai.
In addition to providing rigorous theoretical proofs of correctness and privacy for Pai, we have undertaken comprehensive protocol implementations and conducted extensive experiments to validate their high efficiency. Our empirical findings demonstrate that our protocols achieve notably higher online efficiency than SOTA protocols, e.g., Pai exhibits 8.8 - 91.8\times better online communication cost and 2.5 - 8.8\times better online time. Given the superior online time and storage, our protocol is well-suited for practical deployment.
ePrint: https://eprint.iacr.org/2023/1619
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .