分野別セミナー

We design a new data structure which supports parallel traversal and localized updates. These two features are useful in building searchable symmetric encryption (SSE) for structured data. Specifically, an untrusted server can perform updates even when the data structure is encrypted, such that the efficiency of later queries are still maintained, with the aim of minimizing the leakage of plaintext information to the server. Previous approaches either require the client to get back the encrypted structure and perform all the relevant updates locally, or resort to some relatively heavyweight cryptographic approaches to perform update in an oblivious manner. Our first SSE scheme leverages the rather simple randomized binary tree to achieve non-interactive queries and updates. Our second scheme utilizes our carefully-designed new data structure called forests of tree, which leaks merely local information for both addition and deletion. With minimal leakages, addition is kept non-interactive while deletion only requires three rounds of communications.