Cryptology ePrint Archive: Report 2017/1150

SWiM: Secure Wildcard Pattern Matching From OT Extension

Vladimir Kolesnikov and 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).

Category / Keywords: Pattern Matching, Oblivious Transfer, PRF

Original Publication (with minor differences): Financial Cryptography and Data Security 2018

Date: received 21 Nov 2017, last revised 24 Mar 2019

Contact author: trieun at oregonstate edu

Available format(s): PDF | BibTeX Citation

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.

Version: 20190324:185236 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]