Toward practical encrypted email that supports private, regular-expression searches

In this paper, we develop a protocol to enable private regular-expression searches on encrypted data stored at a $$\mathsf {server}$$server. A novelty of the protocol lies in allowing a user to securely delegate an encrypted search query to a $$\mathsf {proxy}$$proxy, which interacts with the $$\mathsf {server}$$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}$$server and an honest-but-curious $$\mathsf {proxy}$$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.

Duke Scholars

Author Michael Reiter Computer Science