  Searchable symmetric encryption (SSE) enables a client to perform searches
over its outsourced encrypted files while preserving privacy of the files and
queries. Dynamic schemes, where files can be added or removed, leak more
information than static schemes. For dynamic schemes, forward privacy requires
that a newly added file cannot be linked to previous searches. We present a new
dynamic SSE scheme that achieves forward privacy by replacing the keys revealed
to the server on each search. Our scheme is efficient and parallelizable and
outperforms the best previous schemes providing forward privacy, and achieves
competitive performance with dynamic schemes without forward privacy. We
provide a full security proof in the random oracle model. In our experiments on
the Wikipedia archive of about four million pages, the server takes one second
to perform a search with 100,000 results.
