Match Quest: Fast and Secure Pattern Matching
Authors: Pranav Jangir (New York University), Nishat Koti (Aztec Labs), Varsha Bhat Kukkala (IIT Tirupati), Arpita Patra (Indian Institute of Science), Bhavish Raj Gopal (Indian Institute of Science)
Volume: 2025
Issue: 4
Pages: 308–328
DOI: https://doi.org/10.56553/popets-2025-0132
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: secure computation, secure pattern matching, secure equality
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
