Scholarlink

This paper introduces a novel protocol that reduces the cost of querying an encrypted database using homomorphic encryption, improving scalability for a larger number of entries. It leverages fully homomorphic encryption (FHE) and public-key encryption with keyword search (PEKS) to filter the database, selecting a smaller subset of data for further processing with FHE. First, we demonstrate that a construction combining FHE and PEKS is secure against chosen plaintext and chosen keyword attacks. From an experimental point of view, without any parallelism, our protocol is able to match around 5000 database entries per min on a single server core during the PEKS preprocessing phase and around 20 entries per min during an illustrative argmin FHE postprocessing phase, also on a single server core (i.e. assuming the PEKS filters out 99.6% of the database entries, it becomes the limiting scaling factor). This approach achieves a speedup of up to 200 \(\times \) compared with a full FHE solution based on the TFHE scheme and an even greater acceleration when using the BFV scheme (which currently cannot perform an argmin over such large number of entries in a feasible time) at the cost of a leakage/performance tradeoff that we investigate in the paper.

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

Scalable Privacy-Preserving Database Queries with FHE and PEKS

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Nicolas Quero,
  • Renaud Sirdey,
  • Aymen Boudguiga,
  • David Pointcheval,
  • Quentin Sinh,
  • Nadir Karam

摘要

This paper introduces a novel protocol that reduces the cost of querying an encrypted database using homomorphic encryption, improving scalability for a larger number of entries. It leverages fully homomorphic encryption (FHE) and public-key encryption with keyword search (PEKS) to filter the database, selecting a smaller subset of data for further processing with FHE. First, we demonstrate that a construction combining FHE and PEKS is secure against chosen plaintext and chosen keyword attacks. From an experimental point of view, without any parallelism, our protocol is able to match around 5000 database entries per min on a single server core during the PEKS preprocessing phase and around 20 entries per min during an illustrative argmin FHE postprocessing phase, also on a single server core (i.e. assuming the PEKS filters out 99.6% of the database entries, it becomes the limiting scaling factor). This approach achieves a speedup of up to 200 \(\times \) compared with a full FHE solution based on the TFHE scheme and an even greater acceleration when using the BFV scheme (which currently cannot perform an argmin over such large number of entries in a feasible time) at the cost of a leakage/performance tradeoff that we investigate in the paper.