HET-PIR: practical Keyword PIR via a Novel homomorphic equality test Algorithm

Abstract Fully homomorphic encryption (FHE) enables arbitrary computations on encrypted data while preserving strong privacy guarantees. However, the high computational cost of homomorphic operations, particularly multiplication and comparisons, remains a significant bottleneck in practical applications. In this paper, we propose a novel algorithm that efficiently evaluates univariate polynomial functions under FHE, leveraging specific optimization techniques to minimize the number of required homomorphic operations. We rigorously analyze its theoretical performance and extend it to implement an optimized equality test. Our experimental results show that comparing two 32-bit values takes only 3.9 milliseconds, and for batch comparisons between 32,768 16-bit values and a single 16-bit value, the amortized overhead is reduced to 0.01 milliseconds per comparison. Furthermore, we apply this equality test to build a practical single-round keyword private information retrieval (PIR) protocol for the single-server setting. Compared to the Constant-Weight PIR (USENIX 2022), our method achieves a 4–6× reduction in computational overhead during the server’s response phase, making it a more practical solution for real-world deployments.