Efficient and secure pattern matching with wildcards using lightweight cryptography

Many secure protocols exist for the problem of determining occurrences of a pattern P as a substring of a text string T. That is, when Alice has T, and Bob has P, the protocol computes the answer(s) without revealing to Alice or Bob anything that cannot be deduced from the jointly computed answer. The existing protocols work for various adversarial models (some use the powerful malicious model), but they all have drawbacks that detract from practical deployment. For some, the drawback is their quadratic computation time (proportional to |T||P|), for others, it is their use of expensive cryptographic primitives such as homomorphic encryption; some have both drawbacks. Moreover, some restrict alphabet and input size to be bounded by a polynomial in a security parameter. This paper presents a scheme that overcomes these drawbacks in that it works for arbitrary alphabet and input sizes, has O(|T|log|P|) computational cost, does not use expensive cryptographic primitives, and has information-theoretic security (one-time pad). It can also handle single-character wildcards (symbols that match any alphabet symbol). These improvements come at the cost of using a weaker adversarial model than the malicious one (the semi-honest), and an offline helper (e.g., cloud server) that computes and provides Alice and Bob with randoms that they can subsequently use in protocols. We implemented our scheme, that we call LiLiP (Lightweight, Linearithmic & Private), and it performs very well in practice.