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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Financial Cryptography and Data Security 2018
Keywords
Pattern MatchingOblivious TransferPRF
Contact author(s)
trieun @ oregonstate edu
History
2019-03-24: revised
2017-11-27: received
See all versions
Short URL
https://ia.cr/2017/1150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1150,
      author = {Vladimir Kolesnikov and Mike Rosulek and Ni Trieu},
      title = {SWiM: Secure Wildcard Pattern Matching From OT Extension},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1150},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1150}},
      url = {https://eprint.iacr.org/2017/1150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.