Paper 2025/756

PIRCOR: Communication-Optimal Hintless Single-Server PIR via Homomorphic Rotation

Abstract

This work addresses the hintless single-server Private Information Retrieval (PIR) from the perspective of high-level protocol design and introduces PIRCOR and PIRCOR$$ that outperform the state-of-the-art PIRANA (Liu et. al., IEEE S&P 2024) and YPIR (Menon and Wu, USENIX Security 2024) in terms of the query size and the query generation time. In PIRCOR, we construct an efficient Rotation-based Expanded Binary Code (REBC) to expand $$ primary codewords into $$ expanded codewords by the Rotation-Mutual-Multiplication operation. By leveraging the innovative REBC, PIRCOR reduces the query size for single-query PIR by a factor of $$ compared to PIRANA, while also avoiding the $$ linear scaling inherent in YPIR ($$, $$ and $$ are the (R)LWE secret dimension, the number of codewords with a Hamming weight of $$ and the number of database elements). Based on PIRCOR, we further present PIRCOR$$ by additionally introducing the Rotation-self-Multiplication operation, which achieves a $$ reduction in rotation operations and a smaller query size when $$. Building upon PIRCOR and PIRCOR$$, we further propose their optimized variants, PIRCOR-op and PIRCOR$$-op, to further reduce the online response time. Similar to YPIR that leverage pre-processing, PIRCOR-op and PIRCOR$$-op allow all rotations and part of multiplications to be carried out in an offline stage before receiving the query. Additionally, we also design FHE-operator acceleration with leveled optimization and implementation optimization of ciphertext rotation. For 8 KB element retrieval in an 8 GB database, PIRCOR achieves a $$ query size reduction compared to PIRANA. When benchmarked against YPIR, the improvements are even more striking: PIRCOR reduces the query size by $$ and accelerates query generation by a staggering $$. Notably, the enhanced PIRCOR$$ achieves a $$ reduction in query size compared to YPIR, while improving query generation time by an impressive $$.