1. SWiM: Secure Wildcard Pattern Matching From OT Extension 2018 FinancialCryptography OT
    Vladimir Kolesnikov and Mike Rosulek and Ni Trieu
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    @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, Report 2017/1150},
    year = {2017},
    note = {\url{https://eprint.iacr.org/2017/1150}},
    }

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).

  1.