SPIRIT: Batch Hintless Single-Server PIR via Stateful Ciphertext Conversion

Zhou Zhang, Ran Mao, Zian Zhao, Haowen Pan, Yunhao Fu, Yizhong Liu, and Dawei Li, School of Cyber Science and Technology, Beihang University; Yi Chen, Bo Zhang, Changrui Ren, and Jin Dong, Beijing Academy of Blockchain and Edge Computing; Zhenyu Guan and Song Bian, School of Cyber Science and Technology, Beihang University

This work proposes a single-server private information retrieval (PIR) protocol for the efficient evaluation of batched queries without offline hints. It has recently been shown that hintless PIR can be established through the cross-scheme ciphertext conversion technique. However, we point out that such a conversion introduces a considerable amount of computational and communication overheads in the batch PIR setting. To tackle the performance challenge, we propose SPIRIT, a batch, hintless, and single-server PIR protocol that leverages stateful ciphertext conversion to simultaneously achieve high-throughput query execution and low communication cost. To enhance computational efficiency, we develop a novel stateful key expansion procedure that amortizes the conversion cost across multiple queries, significantly accelerating the query evaluation speed. To reduce the communication overhead, we derive a new response compression strategy based on a shared intermediate representation, such that a batch of PIR responses can be packed into a single ciphertext efficiently. In experiments, we show that SPIRIT can achieve up to by 3.1×−5.1× speedup in query execution and reduce the communication bandwidth by 2.3×−3.6× compared to state-of-the-art batch PIR protocols.

USENIX Security '26 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {320859,
author = {Zhou Zhang and Ran Mao and Zian Zhao and Haowen Pan and Yunhao Fu and Yizhong Liu and Dawei Li and Yi Chen and Bo Zhang and Changrui Ren and Jin Dong and Zhenyu Guan and Song Bian},
title = {{SPIRIT}: Batch Hintless {Single-Server} {PIR} via Stateful Ciphertext Conversion},
booktitle = {35th USENIX Security Symposium (USENIX Security 26)},
year = {2026},
isbn = {978-1-939133-58-8},
address = {Baltimore, MD},
pages = {4523--4542},
url = {https://www.usenix.org/conference/usenixsecurity26/presentation/zhang-zhou},
publisher = {USENIX Association},
month = aug
}