Secure and Practical Search over Dynamic Encrypted Datasets

PhD Thesis Proposal Defence


Title: "Secure and Practical Search over Dynamic Encrypted Datasets"

by

Mr. Javad GHAREH CHAMANI


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 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.


Date:			Thursday, 5 May 2022

Time:                  	3:00pm - 5:00pm

Zoom Meeting:		https://hkust.zoom.us/j/4567891320

Committee Members:	Dr. Dimitris Papadopoulos (Supervisor)
 			Dr. Shuai Wang (Chairperson)
 			Prof. Cunsheng Ding
 			Prof. Ke Yi


**** ALL are Welcome ****