BitBatSPIR: Efficient Batch Symmetric Private Information Retrieval From PSI
Shuaishuai Li, Liqiang Peng, Weiran Liu, Cong Zhang, Zhen Gu, Dongdai Lin · IEEE Transactions on Dependable and Secure Computing · 2025
Private Information Retrieval (PIR) allows a client to retrieve an entry from a database held by a server without leaking which entry is being requested. Symmetric PIR (SPIR) is a stronger variant of PIR with database privacy so that the client knows nothing about the database other than the retrieved entry. This work studies SPIR in the batch setting (BatchSPIR), where the client wants to retrieve multiple entries. In particular, we focus on the case of bit entries, which has important realworld applications. We set up the connection between bit-entry information retrieval and set operation, and propose a black-box construction of BatchSPIR from Private Set Intersection (PSI). By applying an efficient PSI protocol with asymmetric set sizes, we obtain our BatchSPIR protocol named BitBatSPIR. We also introduce several optimizations for the underlying PSI. These optimizations improve the efficiency of our concrete BatchSPIR construction as well as the PSI protocol. We implement BitBatSPIR and compare the performance with the state-of-the-art PIR protocol in the batch setting. Our experimental results show that BitBatSPIR not only achieves a stronger security guarantee (symmetric privacy) but also has a better performance for large databases, especially in the Wide Area Network (WAN) setting.