Secure Query Evaluation: From Theory to Practice

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


PhD Thesis Defence


Title: "Secure Query Evaluation: From Theory to Practice"

By

Mr. Yilei WANG



Abstract

We propose protocols for query evaluation under the secure multi-party 
computation model. Our first result is theoretical, which provides circuit 
constructions for evaluating conjunctive queries under degree constraints, 
with polylogarithmic depth and size matching the polymatroid bound up to 
polylogarithmic factors. These circuits yield protocols against any 
adversary. Our second result is a practical protocol for free-connex 
join-aggregate query evaluation under secure two-party computation model 
against semi-honest adversary. This protocol is instance optimal up to one 
logarithm factor, and greatly outperforms the best previous result in all 
experiments. Our third result is also a practical protocol. It evaluates 
any join-aggregate query on foreign-key acyclic schema under secure 
two-party computation model against semi-honest adversary. The complexity 
of the protocol is linear to the input size, which is also instance 
optimal.


Date:			Tuesday, 3 May 2022

Time:			9:00am - 11:00am

Zoom Meeting: 
https://hkust.zoom.us/j/3549368332?pwd=TzBsSjVQQ3JwUVNySVBpOVdLaXdWQT09

Chairperson:		Prof. Tianling JIN (MATH)

Committee Members:	Prof. Ke YI (Supervisor)
 			Prof. Dimitris PAPADIAS
 			Prof. Dimitris PAPADOPOULOS
 			Prof. Wei ZHANG (ECE)
 			Prof. Dan SUCIU (University of Washington)


**** ALL are Welcome ****