Toward practical encrypted email that supports private, regular-expression searches
Lei Wei, Michael K. Reiter · International Journal of Information Security · 2014
In this paper, we develop a protocol to enable private regular-expression searches on encrypted data stored at a $$\mathsf {server}$$ . A novelty of the protocol lies in allowing a user to securely delegate an encrypted search query to a $$\mathsf {proxy}$$ , which interacts with the $$\mathsf {server}$$ where the user’s data are stored encrypted to produce the search result for the user. The privacy of the query and the data are both provably protected against an arbitrarily malicious $$\mathsf {server}$$ and an honest-but-curious $$\mathsf {proxy}$$ under rigorous security definitions. We then detail a series of optimizations to our initial design that achieve an order-of-magnitude performance improvement over the original protocol. We demonstrate the practicality of the resulting protocol through measurements of private regular-expression searches on a real-world email dataset.