Faster FHE-Based Single-Server Private Information Retrieval

This work introduces KsPIR, a new practically efficient single-server private information retrieval (PIR) system that outperforms the state-of-the-art Spiral (Menon and Wu, S&P 2022) in terms of server response times. We achieve this by proposing novel dimension folding methods, inspired by recent advancements in fully homomorphic encryption. Our methods offer two significant advantages: firstly, they feature simpler designs that eliminate the need for ciphertext expansion steps in Spiral. Secondly, and more importantly, we propose two types of designs that offer distinct advantages - the first type enables preprocessing of the most resource-intensive computation in the offline stage before receiving the query, thereby optimizing online response time; the second type optimizes overall response time without requiring preprocessing in the offline stage, accomplished through a highly optimized baby-step-giant-step matrix-vector homomorphic multiplication.