Match Quest: Fast and Secure Pattern Matching
Open Access
- 1 October 2025
- journal article
- Published by Privacy Enhancing Technologies Symposium Advisory Board in Proceedings on Privacy Enhancing Technologies
- Vol. 2025 (4) , 308-328
Abstract
Pattern matching (PM) is the technique of identifying occurrences of a short pattern in a long text, where both, the pattern and text, are a string of characters. Since several applications demand the privacy of the pattern and the text in the process of identifying matches, designing secure solutions for PM is gaining popularity. Moreover, given the variety of applications that consider PM, we design secure solutions for three popular variants of PM---exact, wildcard and approximate. Our solutions are designed using the techniques of secure multiparty computation (MPC) in the two-party semi-honest setting. All of our solutions attain a fast response time, which is the time taken from submission of the input to obtaining the output, and forms a crucial parameter when analysing the performance of any protocol. Moreover, our protocols also provide an improved online communication complexity in comparison to prior works. Since determining if two secret-shared values are equal forms a crucial component in all the PM variants, we design a novel constant-round equality protocol in the two-party semi-honest setting. Our equality protocol outperforms all the prior works in the considered setting and can also be of independent interest. We implement all our protocols on the MPC framework of MOTION2NX to showcase the practicality of the designed solutions. In comparison to prior works that consider DNA matching (over 2-bit characters), our pattern matching protocols see improvements of up to 2 orders of magnitude in response time. Our equality protocol, too, excels over all existing constructions. To analyse the performance of our equality protocol in comparison to prior work, we benchmark it for varying input sizes. We observe that with increasing input sizes, the improvement in response time of our protocol keeps on increasing, with improvements of up to 9.7x for 256-bit inputs.Keywords
This publication has 34 references indexed in Scilit:
- Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation2021
- Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits2020
- Secure Computation with Preprocessing via Function Secret Sharing2019
- A Simple Obfuscation Scheme for Pattern-Matching with Wildcards2018
- Secure and privacy-preserving pattern matching in outsourced computingSecurity and Communication Networks, 2016
- Privacy-Preserving Wildcards Pattern Matching Using Symmetric Somewhat Homomorphic Encryption2014
- Public Key Encryption with Keyword Search Revisited2008
- Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol2007
- Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation2006
- Efficient Multiparty Protocols Using Circuit Randomization2001