Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月7日

查看全文
  • Peizhe Song,
  • Mingsheng Wang

摘要

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.