# US 2021/0344478 A1 · Decision tree-based inference on homomorphically-encrypted data without bootstrapping

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0344478 A1
- Document ID: US20210344478A1
- Status: Published application
- Kind: A1
- Application number: 16/863,767
- Filed: 2020-04-30
- Published: 2021-11-04
- Earliest claimed: 2020-04-30
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Kanthi Sarpatwar; Nalini K. Ratha; Karthikeyan Shanmugam; Karthik Nandakumar; Sharathchandra Pankanti; Roman Vaculin
- Web page: https://patentgrep.com/patent/US20210344478A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- G06N 3/0499: Feedforward networks
- G06N 3/08: Learning methods
- G06N 3/09: Supervised learning
- G06N 3/096: Transfer learning
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 5/04: Inference or reasoning models
- G06N 20/20: Ensemble learning
- H04L 9/30: Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- G06N 3/045: Combinations of networks
- G06N 3/088: Non-supervised learning, e.g. competitive learning
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A method, apparatus and computer program product for homomorphic inference on a decision tree (DT) model. In lieu of HE-based inferencing on the decision tree, the inferencing instead is performed on a neural network (NN), which acts as a surrogate. To this end, the neural network is trained to learn DT decision boundaries, preferably without using the original DT model data training points. During training, a random data set is applied to the DT, and expected outputs are recorded. This random data set and the expected outputs are then used to train the neural network such that the outputs of the neural network match the outputs expected from applying the original data set to the DT. Preferably, the neural network has low depth, just a few layers. HE-based inferencing on the decision tree is done using HE inferencing on the shallow neural network. The latter is computationally-efficient and is carried without the need for bootstrapping.

## Claims

### Claim 1

A method for privacy-preserving homomorphic inferencing with respect to a decision tree-based model, comprising:
training a neural network model to learn one or more decision boundaries of the decision tree, the neural network model having low depth and being trained without requiring access to a data set original used to train the decision tree; and
performing homomorphic inferencing on the low depth neural network model in lieu of the decision tree.

### Claim 2 (depends on 1)

The method as described in claim 1 wherein training the neural network model comprises:
applying a random data set to the decision tree, the random data set matching distribution characteristics of the original data set, and obtaining corresponding regression outputs from applying the random data set; and
using the random data set and the regression outputs to train the neural network model;
wherein, following training, outputs from the trained neural network model substantially match outputs expected to be obtained from applying the original data set to the decision tree.

### Claim 3 (depends on 2)

The method as described claim 2 wherein the distribution characteristics comprise training statistics.

### Claim 4 (depends on 3)

The method as described in claim 3 wherein the training statistics are one of:
minimum and maximum values, and feature-wise mean and variance.

### Claim 5 (depends on 1)

The method as described in claim 1 wherein the decision tree-based model is an ensemble of decision trees.

### Claim 6 (depends on 5)

The method as described in claim 5 wherein the ensemble is one of: an adaptive boosting regressor, a random forest regressor, and a gradient boosting regressor.

### Claim 7 (depends on 1)

The method as described in claim 1 wherein the homomorphic inferencing includes:
encrypting the neural network model with a public key of a client;
hosting the encrypted neural network model in a cloud computing environment;
receiving from the client an encrypted inference query;
applying the encrypted neural network model to the encrypted inference query without decrypting the query; and
returning to the client an encrypted result.

### Claim 8

An apparatus, comprising:
a processor;
computer memory holding computer program instructions executed by the processor, the computer program instructions configured to provide privacy-preserving homomorphic inferencing with respect to a decision tree-based model, the computer program instructions configured to:
train a neural network model to learn one or more decision boundaries of the decision tree, the neural network model having low depth and being trained without requiring access to a data set original used to train the decision tree; and
perform homomorphic inferencing on the low depth neural network model in lieu of the decision tree.

### Claim 9 (depends on 8)

The apparatus as described in claim 8 wherein the computer program instructions configured to train the neural network model are further configured to:
apply a random data set to the decision tree, the random data set matching distribution characteristics of the original data set, and to obtain obtaining corresponding regression outputs from applying the random data set; and
use the random data set and the regression outputs to train the neural network model;
wherein, following training, outputs from the trained neural network model substantially match outputs expected to be obtained from applying the original data set to the decision tree.

### Claim 10 (depends on 9)

The apparatus as described claim 9 wherein the distribution characteristics comprise training statistics.

### Claim 11 (depends on 10)

The apparatus as described in claim 10 wherein the training statistics are one of: minimum and maximum feature values, and feature-wise mean and variance.

### Claim 12 (depends on 8)

The apparatus as described in claim 8 wherein the decision tree-based model is an ensemble of decision trees.

### Claim 13 (depends on 12)

The apparatus as described in claim 12 wherein the ensemble is one of: an adaptive boosting regressor, a random forest regressor, and a gradient boosting regressor.

### Claim 14 (depends on 8)

The apparatus as described in claim 8, wherein the processor and the computer memory are located in a cloud computing environment and the computer program instructions configured to perform homomorphic inferencing are further configured to:
encrypt the neural network model with a public key of a client;
receive from the client an encrypted inference query;
apply the encrypted neural network model to the encrypted inference query without decrypting the query; and
return to the client an encrypted result.

### Claim 15

A computer program product in a non-transitory computer readable medium for use in a data processing system to provide privacy-preserving homomorphic inferencing with respect to a decision tree-based model, the computer program product holding computer program instructions that, when executed by the data processing system, are configured to:
train a neural network model to learn one or more decision boundaries of the decision tree, the neural network model having low depth and being trained without requiring access to a data set original used to train the decision tree; and
perform homomorphic inferencing on the low depth neural network model in lieu of the decision tree.

### Claim 16 (depends on 15)

The computer program product as described in claim 15 wherein the computer program instructions configured to train the neural network model are further configured to:
apply a random data set to the decision tree, the random data set matching distribution characteristics of the original data set, and to obtain corresponding regression outputs from applying the random data set; and
use the random data set and the regression outputs to train the neural network model;
wherein, following training, outputs from the trained neural network model substantially match outputs expected to be obtained from applying the original data set to the decision tree.

### Claim 17 (depends on 16)

The computer program product as described claim 16 wherein the distribution characteristics comprise training statistics.

### Claim 18 (depends on 17)

The computer program product as described in claim 17 wherein the training statistics are one of: minimum and maximum feature values, and feature-wise mean.

### Claim 19 (depends on 15)

The computer program product as described in claim 15 wherein the decision tree-based model is an ensemble of decision trees.

### Claim 20 (depends on 19)

The computer program product as described in claim 19 wherein the ensemble is one of: an adaptive boosting regressor, a random forest regressor, and a gradient boosting regressor.

### Claim 21 (depends on 15)

The computer program product as described in claim 15 wherein the data processing system is located in a cloud computing environment and the computer program instructions configured to perform homomorphic inferencing are further configured to:
encrypt the neural network model with a public key of a client;
receive from the client an encrypted inference query;
apply the encrypted neural network model to the encrypted inference query without decrypting the query; and
return to the client an encrypted result.

### Claim 22

A method of machine learning-as-a-service from a cloud computing infrastructure, comprising:
providing a neural network, the neural network constructed as a proxy for a decision tree-based regression model, the neural network having been trained using a data set, together with corresponding predicted outputs generated from applying the data set to the model, the data set bounded by one or more distribution characteristics associated with training data;
encrypting the neural network with a public key of a client;
responsive to receipt of an encrypted inference query, and without decrypting the encrypted inference query, applying the neural network to the encrypted inference query to generate an encrypted response; and
returning the encrypted response to the client.

### Claim 23 (depends on 22)

The method as described in claim 22 wherein the decision tree-based regression model is an ensemble of decision trees.

### Claim 24 (depends on 23)

The method as described in claim 23 wherein the ensemble is one of: an adaptive boosting regressor, a random forest regressor, and a gradient boosting regressor.

### Claim 25 (depends on 25)

The method as described in claim 25 wherein the neural network is a shallow neural network that has an input layer, an output layer, and ≤three (3) hidden layers.