THESIS
2022
1 online resource (12 unnumbered pages, 145 pages) : illustrations (chiefly color)
Abstract
This thesis studies the problem of dynamic symmetric searchable encryption (DSE)
where one or more data owners store their encrypted data on an untrusted remote server,
and wishes to efficiently search on it (or allow other users to access it). This is a heavily
studied problem in literature and the specific focus of this thesis is on dynamic schemes,
i.e., with efficient support for data insertion, deletion, and modification. In particular, it
is crucial to minimize the information revealed to the server as a result of not only search
queries, but also updates. We present schemes that achieve the two strongest privacy
notions for DSE: forward and backward privacy. The first makes it hard for the server to
link an update operation with previous queries, while the second limits what the...[
Read more ]
This thesis studies the problem of dynamic symmetric searchable encryption (DSE)
where one or more data owners store their encrypted data on an untrusted remote server,
and wishes to efficiently search on it (or allow other users to access it). This is a heavily
studied problem in literature and the specific focus of this thesis is on dynamic schemes,
i.e., with efficient support for data insertion, deletion, and modification. In particular, it
is crucial to minimize the information revealed to the server as a result of not only search
queries, but also updates. We present schemes that achieve the two strongest privacy
notions for DSE: forward and backward privacy. The first makes it hard for the server to
link an update operation with previous queries, while the second limits what the server
can learn about entries that were deleted from the database, from queries that happen
after the deletion. Our results improve the state-of-the-art in this area across multiple
aspects, as we describe next.
First, we introduce novel constructions that are extremely lightweight while also achieving
stronger backward privacy notions than existing ones. Our first scheme Mitra achieves
Type-II backward privacy and is, to the best of our knowledge, the fastest and easiest to implement DSE scheme to date. Our second scheme Orion achieves even stronger Type-I
backward privacy and is the only implemented scheme in the literature of its kind. Finally,
our third scheme Horus improves the second one by reducing the number of communication
roundtrips during queries, but reveals slightly more information to the server
(Type-III backward privacy).
Second, we explicitly focus on DSE with efficient (optimal/quasi-optimal) search in the
presence of deletions, i.e., constructions where the search overhead is within a polylogarithmic
multiplicative factor of the theoretical optimal (i.e., the result size of a search). This
property is achieved by our schemes Orion and Horus but we next aim at much more practically
efficient schemes. Towards that end, we first propose OSSE, the first DSE scheme
that can achieve asymptotically optimal search time, improving the previous state-of-the-art
by a multiplicative logarithmic factor. We also propose an alternative scheme LLSE,
that achieves a sublogarithmic search overhead compared to the optimal. While this is
slightly worse than the previous scheme, it still outperforms all prior works, while also
achieving faster deletions and smaller server storage.
Third, we shift our attention to the problem of multi-user dynamic searchable symmetric
encryption (DMUSSE) where some of the users may be colluding with the server
to extract additional information about the dataset, besides what the owner is willing to
server with them. We provide the first formal security and forward/backward privacy
definitions for the dynamic multi-user setting. We then propose μSE, the first provably
secure DMUSSE scheme under our definition and instantiate it in two versions, with different
performance trade-offs. Furthermore, we extend μSE to support verifiability of
results by adopting a blockchain-based approach for the digests’ dissemination.
Finally, we prototype all our schemes and open-source their code. We evaluate their
performance for different datasets and queryloads, experimentally compare them with
prior state-of-the-art DSE schemes, and report the results.
Post a Comment