Paper 2026/1016
Efficient Homomorphic String Search via TFHE
, KDDI Research (Japan), KDDI Research (Japan), The University of Tokyo, University of Tsukuba, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. Minor revision. Pragmatic Cybersecurity (presented in ACISP 2026)
- Keywords
- TFHESecure SearchSecure Pattern Matching
- Contact author(s)
-
sh-narisada @ kddi com
ir-okada @ kddi com
nishide @ risk tsukuba ac jp
ka-fukushima @ kddi com - History
- 2026-05-21: approved
- 2026-05-21: received
- See all versions
- Short URL
- https://ia.cr/2026/1016
- License
-
CC BY
BibTeX
@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}
}
