IACR News item: 20 August 2014
Melissa Chase, Emily Shen
ePrint Report``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.
Additional news items may be found on the IACR news page.