# US 2021/0083841 A1 · Private Decision Tree Evaluation Using an Arithmetic Circuit

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

- Number: US 2021/0083841 A1
- Document ID: US20210083841A1
- Status: Published application
- Kind: A1
- Application number: 16/573,827
- Filed: 2019-09-17
- Published: 2021-03-18
- Earliest claimed: 2019-09-17
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Anselme Kemgne Tueno; Yordan Boev; Florian Kerschbaum
- Web page: https://patentgrep.com/patent/US20210083841A1

## CPC

- G06N 20/00: Machine learning
- H04L 9/008: {involving homomorphic encryption}
- G06F 40/126: Character encoding
- G06F 40/205: Parsing
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 20/10: using kernel methods, e.g. support vector machines [SVM]
- H04L 9/0618: {Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation}
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A non-interactive protocol is provided for evaluating machine learning models such as decision trees. A client can delegate the evaluation of a machine learning model such as a decision tree to a server by sending an encrypted input and receiving only the encryption of the result. The inputs can be encoded as vector of integers using their binary representation. The server can then evaluate the machine learning model using a homomorphic arithmetic circuit. The homomorphic arithmetic circuit provides an implementation that requires fewer multiplications than a Boolean comparison circuit. Efficient data representations are then combined with different algorithmic optimizations to keep the computational overhead and the communication cost low. Related apparatus, systems, techniques and articles are also described.

## Claims

### Claim 1

A computerized method comprising:
homomorphically encrypting a plaintext data set component-wise;
generating a plurality of random strings;
forming an encrypted input comprising the plurality of random strings and the homomorphically encrypted data set;
transmitting the encrypted input to a server executing a decision tree for evaluation using a homomorphic arithmetic circuit; and
receiving, from the server, data characterizing the evaluation by the server; and
decrypting the evaluation.

### Claim 2

A computerized method comprising:
receiving, by a server from a client, an encrypted input encapsulating a data set;
generating, by the server using a homomorphic arithmetic circuit, a classification of the data set using a decision tree; and
providing, by the server to the client, the generated classification to enable the client to decrypt the classification.

### Claim 3 (depends on 2)

The method of claim 2, wherein the decision tree is a machine learning model that maps an n-dimensional attribute vector to a finite set of classification labels.

### Claim 4 (depends on 3)

The method of claim 3, wherein the decision tree comprises a plurality of internal nodes that each comprise a test condition, and a plurality of leaf nodes that each comprise a classification label.

### Claim 5 (depends on 4)

The method of claim 4, wherein the arithmetic circuit evaluates the decision tree using an efficient integer comparison algorithm requiring fewer multiplications than a Boolean comparison circuit.

### Claim 6 (depends on 4)

The method of claim 4 further comprising:
computing a decision result for each internal node; and
aggregating, for each leaf node, the computed decision results along a corresponding path to such leaf node to determine whether one such leaf node has been reached by a classification algorithm.

### Claim 7 (depends on 5)

The method of claim 5, wherein the provided generated classification comprises the classification labels.

### Claim 8 (depends on 2)

The method of claim 2 further comprising:
receiving, by the server from the client, a public key and an evaluation key.

### Claim 9 (depends on 2)

The method of claim 2 further comprising:
homomorphically encrypting the data set by the client to result in the encrypted input.

### Claim 10 (depends on 8)

The method of claim 8, wherein the data set is plaintext and is encoded as vector of integers and encrypted component-wise.

### Claim 11 (depends on 2)

The method of claim 2 further comprising:
generating a plurality of random integers;
wherein the encrypted input comprises the plurality of random integers and the data set.

### Claim 12 (depends on 2)

The method of claim 2 further comprising: homomorphically evaluating the decision tree.

### Claim 13 (depends on 11)

The method of claim 11, wherein an output of the homomorphic evaluation of the decision tree consists of a ciphertext of a corresponding computation result.

### Claim 14 (depends on 4)

The method of claim 4 further comprising:
encoding a plurality of attribute vectors by the client such that the server can evaluate them together in a single protocol run.

### Claim 15 (depends on 4)

The method of claim 4 further comprising:
encoding a plurality of threshold values by the server and evaluating them together in a single operation

### Claim 16 (depends on 2)

The method of claim 2, wherein the providing comprises transmitting the generated classification to the client over a network;
wherein the method further comprises:
decrypting the generated classification by the client.

### Claim 17

A system comprising:
at least one data processor; and
memory storing instructions which, when executed by the at least one data processor, result in operations comprising:
receiving an encrypted input encapsulating a data set;
generating, using a homomorphic arithmetic circuit, a classification of the data set using a decision tree; and
transmitting the generated classification over a computer network to a remote computing device to enable decryption the classification.

### Claim 18 (depends on 17)

The system of claim 17, wherein:
the decision tree is a machine learning model that maps an n-dimensional attribute vector to a finite set of classification labels;
the decision tree comprises a plurality of internal nodes that each comprise a test condition, and a plurality of leaf nodes that each comprise a classification label.

### Claim 19 (depends on 18)

The system of claim 18, wherein the arithmetic circuit evaluates the decision tree using an efficient integer comparison algorithm requiring fewer multiplications than a Boolean comparison circuit.

### Claim 20 (depends on 19)

The system of claim 19, wherein the operations further comprise:
computing a decision result for each internal node; and
aggregating, for each leaf node, the computed decision results along a corresponding path to such leaf node to determine whether one such leaf node has been reached by a classification algorithm.
