Welcome to the resource topic for 2025/756
Title:
PIRCOR: Communication-Optimal Hintless Single-Server PIR via Homomorphic Rotation
Authors: Xue Yang, Ruida Wang, Depan Peng, Kun Liu, Xianhui Lu, Xiaohu Tang
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 \alpha$ primary codewords into \beta 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 \mathcal{O}\left(N^{\frac{\delta-1}{\delta}}\right) compared to PIRANA, while also avoiding the \mathcal{O}(N +\frac{|\mathrm{DB}|}{N}) linear scaling inherent in YPIR (N, \delta and |\mathrm{DB}| are the (R)LWE secret dimension, the number of codewords with a Hamming weight of 1 and the number of database elements). Based on PIRCOR, we further present PIRCOR$^{} by additionally introducing the Rotation-self-Multiplication operation, which achieves a \mathbf{50%} reduction in rotation operations and a smaller query size when \delta = 2$.
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 \mathbf{10.7\times} query size reduction compared to PIRANA. When benchmarked against YPIR, the improvements are even more striking: PIRCOR reduces the query size by \mathbf{26.8\times} and accelerates query generation by a staggering \mathbf{6,080\times}. Notably, the enhanced PIRCOR$^{*} achieves a \mathbf{53.6\times} reduction in query size compared to YPIR, while improving query generation time by an impressive \mathbf{12,160\times}$.
ePrint: https://eprint.iacr.org/2025/756
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .