Verifiable and Forward Secure Dynamic Searchable Symmetric Encryption with Storage Efficiency

摘要

Searchable symmetric encryption (SSE) provides private searching over an encrypted database against an untrusted server. Though various SSE schemes have been studied, recently, it is shown that most of existing schemes are vulnerable to file injection attacks. At ACM CCS 2016, Bost proposed a forward secure SSE scheme to resist such attacks, called Σoøoc. Besides the basic scheme (Σoøoc) secure against semi-honest servers, a verifiable scheme (Σoøoc-є) secure against malicious servers is also introduced. In Σoøoc-є, each client keeps hash values of indexes of documents corresponding to each keyword. Thus, the client storage cost is higher than for Σoøoc, and the hash table must be reconstructed when a new document is added. Also, since any security definition and proof of security against malicious servers are not provided, what Σoøoc-є guarantees against malicious server is unclear. In this paper, we propose a new verifiable and forward secure SSE scheme against malicious servers. An advantage of our scheme to Σoøoc-є is the client storage cost; that is, our scheme only needs the same storage cost as Σoøoc-є. Our key idea is to bind each index and keyword with a tag generated by an algebraic pseudo-random function, and to store the tag to the server as well as the encrypted index on an update phase. The client can efficiently check validity of answers to search queries by verifying the combined tag thanks to closed form efficiency of the algebraic pseudorandom function; and thus, the client does not need to keep the hash table. Also, we formally prove security against malicious servers. Specifically, we show that our scheme satisfies the strong reliability definition.