Doctoral defence: Mohammad Anagreh “Privacy-preserving parallel computations for graph problems”

On 29 May at 14:15, Mohammad Anagreh will defend his doctoral thesis “Privacy-preserving parallel computations for graph problems” to obtain the degree of Doctor of Philosophy (in Computer Science).

Supervisors:
Prof. Eero Vainikko, University of Tartu
Visiting Prof. Peeter Laud, University of Tartu and Cybernetica AS

Opponents:
Prof. Shin'ichiro Matsuo, Georgetown University (USA)
Dr. Mustafa A. Mustafa, University of Manchester (United Kingdom)

Summary
Constructing real-world privacy applications based on secure multiparty computation is challenging due to the round complexity of the computation parties of SMC protocol. Due to the novelty of privacy-preserving technologies and the high computational costs associated with these problems, parallel privacy-preserving graph algorithms have not yet been studied. Graph algorithms are the backbone of many applications in computer science, such as navigation systems, community detection, supply chain network, hyperspectral image, and sparse linear solvers. In order to expedite the processing of large private data sets for graphs algorithms and meet high-end computational demands, privacy-preserving parallel algorithms are needed. Therefore, this Thesis presents the state-of-the-art protocols in privacy-preserving parallel computations for different graphs problems, single-source shortest path (SSSP), All-pairs shortest path (APSP), minimum spanning tree (MST) and forest (MSF), and algebraic path computation. These new protocols have been constructed based on combinatorial and algebraic graph algorithms on top of the SMC protocols. Single-instruction-multiple-data (SIMD) operations are also used to build those protocols to reduce the round complexities efficiently. We have implemented the proposed protocols on the Sharemind SMC platform using various graphs and network environments. This Thesis outlines novel parallel protocols with their related algorithms, the results, speed-up, evaluations, and extensive benchmarking. The results of the real implementations of the privacy-preserving single-source shortest paths and minimum spanning tree protocols show an efficient method that reduced the running time hundreds of times compared with previous works. Furthermore, the evaluation and extensive
benchmarking of privacy-preserving All-pairs shortest path protocols are not similar to any previous work. Moreover, the privacy-preserving minimum spanning forest and algebraic path computation protocols have never been addressed before.

Defence can be also followed in Zoom (Meeting ID: 953 0908 5677, Passcode: ati).