Motivated by advances in multi-core architectures, we present a new method for constructing sub-linear SSE schemes. Our approach is highly parallelizable and dynamic. With roughly a logarithmic number of cores in place, searches for a keyword w in our scheme execute in o(r) parallel time, where r is the number of documents containing keyword w (with more cores, this bound can go down to O(log n), i.e., independent of the result size r). Such time complexity outperforms the optimal \theta(r) sequential search time—a similar bound holds for the updates.
Our scheme also achieves the following important properties: (a) it enjoys a strong notion of security, namely security against adaptive chosen-keyword attacks; (b) compared to existing sub-linear dynamic SSE schemes (e.g., Kamara, Papamanthou, Roeder, CCS ’12), updates in our scheme do not leak any information, apart from information that can be inferred from previous search tokens; (c) it can be implemented efficiently in external memory (with logarithmic I/O overhead). Our technique is simple and uses a red-black tree data structure; its security is proven in the random oracle model.
Category / Keywords: cryptographic protocols / searchable encryption, cloud computing, cloud storage Date: received 30 May 2013 Contact author: senyk at microsoft com Available format(s): PDF | BibTeX Citation Version: 20130603:133214 (All versions of this report) Short URL: ia.cr/2013/335 Discussion forum: Show discussion | Start new discussion