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

• [1] Ágnes Kiss, Masoud Naderpour, Jian Liu, N. Asokan, and Thomas Schneider. SoK: Modular and efficient private decision tree evaluation. Proceedings on Privacy Enhancing Technologies (PoPETs), 2019.
• [2] Anselme Tueno, Florian Kerschbaum, and Stefan Katzenbeisser. Private evaluation of decision trees using sublinear cost (opens in new tab). Proceedings on Privacy Enhancing Technologies (PoPETs), 2019.
• [3] Yifeng Zheng, Huayi Duan, Cong Wang, Ruochen Wang, and Surya Nepal. Securely and Efficiently Outsourcing Decision Tree Inference. IEEE Transactions on Dependable and Secure Computing, 2020.
• [4] Lennart Braun, Daniel Demmler, Thomas Schneider, and Oleksandr Tkachenko. MOTION – A framework for mixed-protocol multI-party computation. Cryptology ePrintArchive, Report 2020/1137, 2020.

Supervisors

• Amos Treiber, M.Sc. ( treiber@encrypto.cs.tu-…)
• Prof. Dr.-Ing. Thomas Schneider ( schneider@encrypto.cs.tu-…)