back to list

Outsourced Sublinear Private Decision Tree Evaluation

Master Thesis

Motivation

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.

Goal

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.

References

Supervisors