Paper 2026/1016

Efficient Homomorphic String Search via TFHE

Hiroki Okada, KDDI Research (Japan), The University of Tokyo

Takashi Nishide, University of Tsukuba

Kazuhide Fukushima, KDDI Research (Japan)

Abstract

We present a method for secure pattern matching over encrypted texts using TFHE. Our approach realizes a fully secure binary search algorithm by leveraging two operational modes of integer-input TFHE. While the BGV-based method of Bonte and Iliashenko (CCSW '20) requires $O(|P| \cdot |T|)$ secure character comparisons to find a pattern $P$ in a text $T$, our method reduces this to $O(|P|\log |T|)$ comparisons, achieving improved scalability for large texts. As a result, our method can find a pattern of length 100 in an encrypted text containing genomic data of one million characters in less than 5 minutes, where prior work would require approximately 5 days for the same task. These results highlight the practicality of TFHE and its potential for large-scale secure string search.

@misc{cryptoeprint:2026/1016,
      author = {Shintaro Narisada and Hiroki Okada and Takashi Nishide and Kazuhide Fukushima},
      title = {Efficient Homomorphic String Search via {TFHE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1016},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1016}
}