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|·|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 min, 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.
- Open Access
- Article
Efficient Homomorphic String Search via TFHE †
- Shintaro Narisada 1,*,
- Hiroki Okada 1,2,
- Takashi Nishide 3,
- Kazuhide Fukushima 1
Author Information
Received: 09 Jul 2026 | Revised: 13 Aug 2026 | Accepted: 14 Aug 2026 | Published: 21 Aug 2026
Abstract
Keywords
References
- 1.
Akavia, A.; Feldman, D.; Shaul, H. Secure Search on Encrypted Data via Multi-Ring Sketch. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada, 15–19 October 2018; pp. 985–1001.
- 2.
Yasuda, M.; Shimoyama, T.; Kogure, J.; et al. Secure Pattern Matching Using Somewhat Homomorphic Encryption. In Proceedings of the 2013 ACM Cloud Computing Security Workshop (CCSW’13), Berlin, Germany, 4 November 2013; pp. 65–76. https://doi.org/10.1145/2517488.2517497.
- 3.
Hahn, F.; Loza, N.; Kerschbaum, F. Practical and Secure Substring Search. In Proceedings of the SIGMOD/PODS’18: International Conference on Management of Data, Houston, TX, USA, 10–15 June 2018; pp. 163–176. https://doi.org/10.1145/3183713.3183754.
- 4.
Mainardi, N.; Barenghi, A.; Pelosi, G. Privacy Preserving Substring Search Protocol with Polylogarithmic Communication Cost. In Proceedings of the 35th Annual Computer Security Applications Conference, San Juan, Puerto Rico, 9–13 December 2019; pp. 297–312. https://doi.org/10.1145/3359789.3359842.
- 5.
Boldyreva, A.; Chenette, N.; Lee, Y.; et al. Order-Preserving Symmetric Encryption. In Advances in Cryptology—EUROCRYPT 2009, Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, 26–30 April 2009; Springer: Berlin/Heidelberg, Germany, 2009; pp. 224–241. https://doi.org/10.1007/978-3-642-01001-9_13.
- 6.
Pandey, O.; Rouselakis, Y. Property Preserving Symmetric Encryption. In Advances in Cryptology—EUROCRYPT 2012, Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 15–19 April 2012; Springer: Berlin/Heidelberg, Germany, 2012; pp. 375–391. https://doi.org/10.1007/978-3-642-29011-4_23.
- 7.
Desmoulins, N.; Fouque, P.A.; Onete, C.; et al. Pattern Matching on Encrypted Streams. In Advances in Cryptology—ASIACRYPT 2018, Proceedings of the 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, 2–6 December 2018; Springer: Cham, Switzerland, 2018; pp. 121–148. https://doi.org/10.1007/978-3-030-03326-2_5.
- 8.
Bkakria, A.; Cuppens, N.; Cuppens, F. Privacy-Preserving Pattern Matching on Encrypted Data. In Advances in Cryptology—ASIACRYPT 2020, Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, 7–11 December 2020; Springer: Cham, Switzerland, 2020; pp. 191–220. https://doi.org/10.1007/978-3-030-64834-3_7.
- 9.
Bouscatie, E.; Castagnos, G.; Sanders, O. Public Key Encryption with Flexible Pattern Matching. In Advances in Cryptology—ASIACRYPT 2021, Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021; Springer: Cham, Switzerland, 2021; pp. 342–370.
- 10.
Bouscatie, E.; Castagnos, G.; Sanders, O. Pattern Matching in Encrypted Stream from Inner Product Encryption. In
Public-Key Cryptography—PKC 2023, Proceedings of the 26th IACR International Conference on Practice and Theory
of Public-Key Cryptography, Atlanta, GA, USA, 7–10 May 2023; Springer: Cham, Switzerland, 2023; pp. 774–801.
https://doi.org/10.1007/978-3-031-31368-4_27. - 11.
Bonte, C.; Iliashenko, I. Homomorphic String Search with Constant Multiplicative Depth. In Proceedings of the 2020 ACM SIGSAC Conference on Cloud Computing Security Workshop, Online, 9 November 2020; pp. 105–117. https://doi.org/10.1145/3411495.3421361.
- 12.
Choi, S.G.; Dachman-Soled, D.; Gordon, S.D.; et al. Compressed Oblivious Encoding for Homomorphically Encrypted Search. In Proceedings of the CCS’21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Online, 15–19 November 2021; pp. 2277–2291. https://doi.org/10.1145/3460120.3484792.
- 13.
Bkakria, A.; Izabachene, M. Efficient Post-Quantum Pattern Matching on Encrypted Data. IACR Commun. Cryptol. 2024, 1. https://doi.org/10.62056/a09qxrxqi.
- 14.
Kabra, M.; Nadig, R.; Gupta, H.; et al. CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and in-Flash Processing. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, Rotterdam, The Netherlands, 30 March–3 April 2025; pp. 111–130. https://doi.org/10.1145/3676641.3716251.
- 15.
Manber, U.; Myers, G. Suffix Arrays: A New Method for on-Line String Searches. SIAM J. Comput. 1993, 22, 935–948. https://doi.org/10.1137/0222058.
- 16.
Weiner, P. Linear Pattern Matching Algorithms. In Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), Iowa City, IA, USA, 15–17 October 1973; pp. 1–11. https://doi.org/10.1109/swat.1973.13.
- 17.
Chillotti, I.; Gama, N.; Georgieva, M.; et al. Faster Fully Homomorphic Encryption: Bootstrapping in Less than 0.1 Seconds. In Advances in Cryptology—ASIACRYPT 2016, Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4–8 December 2016; Springer: Berlin/Heidelberg, Germany, 2016; pp. 3–33. https://doi.org/10.1007/978-3-662-53887-6_1.
- 18.
Chillotti, I.; Gama, N.; Georgieva, M.; et al. TFHE: Fast Fully Homomorphic Encryption over the Torus. J. Cryptol. 2020, 33, 34–91. https://doi.org/10.1007/s00145-019-09319-x.
- 19.
Larsson, N.J.; Sadakane, K. Faster Suffix Sorting. Theor. Comput. Sci. 2007, 387, 258–272. https://doi.org/10.1016/j.tcs.2007.07.017.
- 20.
Bourse, F.; Sanders, O.; Traor´e, J. Improved Secure Integer Comparison via Homomorphic Encryption. In Proceedings of the Topics in Cryptology—CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, 24–28 February 2020; pp. 391–416.
- 21.
Knuth, D.E.; Morris, J.H., Jr; Pratt, V.R. Fast Pattern Matching in Strings. SIAM J. Comput. 1977, 6, 323–350. https://doi.org/10.1137/0206024.
- 22.
Gama, N.; Izabachene, M.; Nguyen, P.Q.; et al. Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems. In Advances in Cryptology—EUROCRYPT 2016, Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, 8–12 May 2016; Springer: Berlin/Heidelberg, Germany, 2016; pp. 528–558.
- 23.
Chillotti, I.; Ligier, D.; Orfila, J.B.; et al. Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE. In Advances in Cryptology—ASIACRYPT 2021, Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 6–10 December 2021; Springer: Cham, Switzerland, 2021; pp. 670–699.
- 24.
Chen, H.; Dai, W.; Kim, M.; et al. Efficient Homomorphic Conversion between (Ring) LWE Ciphertexts. In Applied Cryptography and Network Security, Proceedings of the 19th International Conference, ACNS 2021, Kamakura, Japan, 21–24 June 2021; Springer: Cham, Switzerland, 2021; pp. 460–479. https://doi.org/10.1007/978-3-030-78372-3_18.
- 25.
Bergerat, L.; Boudi, A.; Bourgerie, Q.; et al. Parameter Optimization and Larger Precision for (T) FHE. J. Cryptol. 2023, 36, 28. https://doi.org/10.1007/s00145-023-09463-5.
- 26.
Wang, R.; Ha, J.; Shen, X.; et al. Refined TFHE Leveled Homomorphic Evaluation and Its Application. In Proceedings of the CCS’25: ACM SIGSAC Conference on Computer and Communications Security, Taipei, Taiwan, 13–17 October 2025; pp. 2309–2323. https://doi.org/10.1145/3719027.3744873.
- 27.
Joye, M. SoK: Fully Homomorphic Encryption over the [Discretized] Torus. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022, 2022, 661–692. https://doi.org/10.46586/tches.v2022.i4.661-692.
- 28.
Joye, M. TFHE Public-Key Encryption Revisited. In Proceedings of the CT-RSA 2024: Cryptographers’ Track at the RSA Conference 2024, San Francisco, CA, USA, 6–9 May 2024; pp. 277–291.
- 29.
Zama TFHE-Rs: A Pure Rust Implementation of the TFHE Scheme for Boolean and Integer Arithmetics over Encrypted Data. Available online: https://github.com/zama-ai/tfhe-rs (accessed on 13 August 2026).
- 30.
Albrecht, M.R.; Curtis, B.R.; Deo, A.; et al. Estimate All the {LWE, NTRU} Schemes! In Proceedings of the International Conference on Security and Cryptography for Networks, Amalfi, Italy, 5–7 September 2018; pp. 351–367. https://doi.org/10.1007/978-3-319-98113-0 19.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Suite 4002 Level 4, 447 Collins Street, Melbourne, Victoria 3000, Australia
General Inquiries: info@sciltp.com