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

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.