Paper 2017/1150

SWiM: Secure Wildcard Pattern Matching From OT Extension

Vladimir Kolesnikov, Mike Rosulek, and Ni Trieu

Abstract

Suppose a server holds a long text string and a receiver holds a short pattern string. Secure pattern matching allows the receiver to learn the locations in the long text where the pattern appears, while leaking nothing else to either party besides the length of their inputs. In this work we consider secure wildcard pattern matching WPM, where the receiver's pattern is allowed to contain wildcards that match to any character. We present SWiM, a simple and fast protocol for WPM that is heavily based on oblivious transfer (OT) extension. As such, the protocol requires only a small constant number of public-key operations and otherwise uses only very fast symmetric-key primitives. SWiM is secure against semi-honest adversaries. We implemented a prototype of our protocol to demonstrate its practicality. We can perform WPM on a DNA text (4-character alphabet) of length $10^5$ and pattern of length $10^3$ in just over 2 seconds, which is over two orders of magnitude faster than the state-of-the-art scheme of Baron et al. (SCN 2012).

Note: We updated our writeup to be clear that the previous work also considers secure pattern matching in the malicious setting. However, our paper only focuses on the semi-honest one.