Secure and Practical Search over Dynamic Encrypted Datasets

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis 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-theart 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:			Monday, 8 August 2022

Time:			2:00pm - 4:00pm

Zoom Meeting:
https://hkust.zoom.us/j/96824590980?pwd=dUVlenRmMU1oTFQ5cHRGTUpsM2Qydz09

Chairperson:		Prof. Zhiyong FAN (ECE)

Committee Members:	Prof. Dimitris PAPADOPOULOS (Supervisor)
 			Prof. Cunsheng DING
 			Prof. Ke YI
 			Prof. Jack CHENG (CIVL)
 			Prof. Sherman CHOW (CUHK)


**** ALL are Welcome ****