Paper 2014/638

Pattern Matching Encryption

Melissa Chase and Emily Shen

Abstract

In this paper, we consider a setting where a user wants to outsource storage of a large amount of private data, and then perform pattern matching queries on the data; that is, given a data string $s$ and a ``pattern'' string $p$, find all occurrences of $p$ as a substring of $s$. We formalize the security properties desired in this type of setting by defining a type of encryption called \emph{queryable encryption}. In a queryable encryption scheme, a user can encrypt a message $M$ under a secret key, and using the secret key can generate tokens for queries $q$. Applying a token for a query $q$ to an encryption of $M$ gives the answer to the query $q$ on $M$. We consider security against both honest-but-curious and malicious adversaries, and define properties guaranteeing both the correctness of the user's results and the privacy of the user's data. Following the line of work started by \cite{CGKO06}, to allow for efficient constructions, we allow the protocol to leak some information about the user's data, however we ensure that this leakage can be precisely captured in the definition. In addition, we allow the query protocol to involve a small constant number of rounds of interaction. We construct a queryable encryption scheme for pattern matching queries that is correct and secure in the malicious model. Our construction is based on efficient symmetric-key building blocks and scales well with the size of the input: encryption of a data string of length $n$ with security parameter $\lambda$ takes $O(n)$ time and produces a ciphertext of size $O(n\lambda)$, and a query for a pattern string of length $m$ that occurs $k$ times takes $O(m+k)$ time and three rounds of communication.