Paper 2026/1016 Original: eprint.iacr.org/2026/1016 ↗
Efficient Homomorphic String Search via TFHE
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
- Preprint.
- History
- 2026-08-21: last updated
- 2026-05-21: published
- Short URL
- https://ia.cr/2026/1016
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}