Secure Multi-party Query Processing

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


PhD Thesis Defence


Title: "Secure Multi-party Query Processing"

By

Mr. Qiyao LUO


Abstract:

Secure Multi-Party Computation (MPC) has gained significant attention due to 
its ability to provide robust privacy protection for joint data analysis among 
multiple organizations. However, current MPC protocols suffer from huge 
computational overhead, rendering them impractical for real-world deployments. 
In this thesis, we tackle efficient MPC protocols from different perspectives.

We first improve the join operator, which is the key relational operator in 
query processing. Our improvement processes all free-connex queries with linear 
complexity under the three-server honest-majority model. It matches the 
plaintext result for the query processing problem, as free-connex queries are 
the largest class of queries known to be solvable in linear time on plaintext.

Second, we consider sublinear complexity for aggregation queries. We describe 
circuit constructions for batch sampling problems, and further implement the 
first approximate query processing solution that achieves amortized cost 
related to the sample size. By adopting the two-stage approach and moving heavy 
computation tasks into the offline stage, we significantly reduce the online 
response time and communication costs of aggregation queries.

Finally, we address the challenge of performing aggregations on a large number 
of participants with anonymous channels, a scenario referred to as the shuffle 
model. We combine differential privacy techniques with the shuffle model, 
resulting in the optimal error frequency estimation protocol with almost a 
single message. This approach has a simple implementation and practical results 
- providing strong privacy protection while maintaining the optimal error.


Date:                   Monday, 24 June 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Dr. Ivan Chi Ho IP (MATH)

Committee Members:      Prof. Ke YI (Supervisor)
                        Prof. Kai CHEN
                        Dr. Dimitris PAPADOPOULOS
                        Dr. Shenghui SONG (ISD)
                        Prof. Guoliang LI (Tsinghua Univ.)