More about HKUST
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.)