Outsourced Sublinear Private Decision Tree Evaluation

Master Thesis


In privacy-preserving machine learning (PPML) applications, a client wants to use an ML-based service of a service provider without having to provide its private data to the provider and without the provider having to provide its valuable model to the client. For a particular type of model, decision trees (DTs), a range of cryptographic techniques have been proposed [1-3] based on secure multi-party computation (MPC) and homomorphic encryption techniques. In contrast to [1,3], [2] achieves even sublinear costs by incorporating Oblivious RAM (ORAM) into the secure computation process, a notion referred to as RAM-based secure computation (RAM-SC). In a client-server setting as in [1,2], the overhead generated by such techniques can be enormous and is prohibitive especially for mobile clients. Instead, an outsourcing setting such as [3] might be more appropriate for mobile applications. There, two non-colluding servers securely compute the DT inference based on secret shares of the input data – the client data and the model. However, the techniques in [3] have linear costs, which might be prohibitive for very deep DTs, and consequently those techniques have only been evaluated on small instances.


The goal of the thesis is to design a RAM-SC based protocol to privately and efficiently evaluate DTs in an outsourcing setting. It should appropriately combine the techniques of the client-server setting [1,2] to the outsourcing setting of [3] and improve upon [3], possibly with further optimizations. Special emphasis needs to be put on practicality for mobile clients. The implementation shall be included in the state-of-the-art MPC framework MOTION [4] and be compared to a re-implementation of [3] therein. State-of-the-art ORAMs need to be surveyed from the literature and be practically evaluated to find the best fit. All results need to be verified by a comprehensive and comparative empirical evaluation on real DT models and data.