# US 2025/0158800 A1 · Two-party privacy preserving decision tree evaluation using additively homomorphic encryption

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

- Number: US 2025/0158800 A1
- Document ID: US20250158800A1
- Status: Published application
- Kind: A1
- Application number: 18/421,708
- Filed: 2024-01-24
- Published: 2025-05-15
- Earliest claimed: 2023-11-13
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Anselme TUENO; David BOEHM
- Web page: https://patentgrep.com/patent/US20250158800A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- G06F 18/24323: {Tree-organised classifiers}
- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 20/00: Machine learning
- H04L 9/14: using a plurality of keys or algorithms
- H04W 12/065: Continuous authentication
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- 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)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

Disclosed herein are system, method, and computer program product embodiments for evaluating a decision tree in a privacy preserving manner. In embodiments, s first server receives a first partial share of the decision tree and encrypted input data from a client, wherein the input data comprises a set of attributes. A second server receives a second partial share of the decision tree. Each of the first server and the second server communicate with the other server to compute a classification result over the encrypted input data using the respective partial share of the decision tree received thereby and secure multi-party computation methods, including additive homomorphic encryption and oblivious transfer, such that the classification result is computed without decrypting the encrypted input data, and such that the classification result is ultimately received by the first server. The first server then transmits the classification result to the client.

## Claims

### Claim 1

A computer-implemented method for evaluating a decision tree in a privacy preserving manner, comprising:
receiving, by a first server, a first partial share of the decision tree and encrypted input data from a client, wherein the encrypted input data comprises a set of attributes;
receiving, by a second server, a second partial share of the decision tree;
by each of the first server and the second server: communicating with the other server to compute a classification result over the encrypted input data using the respective partial share of the decision tree received thereby and secure multi-party computation methods, including additive homomorphic encryption and oblivious transfer, such that the classification result is computed without decrypting the encrypted input data, and such that the classification result is ultimately received by the first server; and
transmitting, by the first server, the classification result to the client.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the decision tree comprises a full binary decision tree.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein the decision tree comprises a plurality of decision nodes and a plurality of leaf nodes,
wherein the first partial share of the decision tree comprises a tuple of thresholds respectively associated with decision nodes of the decision tree and a tuple of attribute indices respectively associated with the decision nodes of the decision tree, and
wherein the second partial share of the decision tree comprises a structural description of the decision tree and a tuple of classification labels respectively associated with the leaf nodes of the decision tree.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, wherein the tuple of classification labels is encrypted with a first public key that is paired with a first private key that is accessible to the first server but not the second server, and
wherein the tuple of thresholds is encrypted with a second public key that is paired with a second private key that is accessible to the second server but not the first server.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein the set of attributes is associated with a user, wherein the decision tree comprises a classification model trained on one or more previously-obtained sets of attributes associated with the user, and wherein the classification result indicates whether the user should or should not be authenticated.

### Claim 6 (depends on 5)

The computer-implemented method of claim 5, wherein the set of attributes associated with the user comprise one or more of:
behavioral attributes associated with the user; or
biometric attributes associated with the user.

### Claim 7 (depends on 5)

The computer-implemented method of claim 5, wherein the computer-implemented method is performed as a part of a continuous authentication process used to determine whether the user should have continued access to a system or resource.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, wherein the first server and the second server communicate with each other directly or indirectly via one or more intermediaries.

### Claim 9

A system for evaluating a decision tree in a privacy preserving manner, comprising:
a first server that is configured to receive a first partial share of the decision tree and encrypted input data from a client, wherein the encrypted input data comprises a set of attributes; and
a second server that is configured to receive a second partial share of the decision tree;
wherein each of the first server and the second server is further configured to communicate with the other server to compute a classification result over the encrypted input data using the respective partial share of the decision tree received thereby and secure multi-party computation methods, including additive homomorphic encryption and oblivious transfer, such that the classification result is computed without decrypting the encrypted input data, and such that the classification result is ultimately received by the first server, and
wherein the first server is further configured to transmit the classification result to the client.

### Claim 10 (depends on 9)

The system of claim 9, wherein the decision tree comprises a full binary decision tree.

### Claim 11 (depends on 9)

The system of claim 9, wherein the decision tree comprises a plurality of decision nodes and a plurality of leaf nodes,
wherein the first partial share of the decision tree comprises a tuple of thresholds respectively associated with decision nodes of the decision tree and a tuple of attribute indices respectively associated with the decision nodes of the decision tree, and
wherein the second partial share of the decision tree comprises a structural description of the decision tree and a tuple of classification labels respectively associated with the leaf nodes of the decision tree.

### Claim 12 (depends on 11)

The system of claim 11, wherein the tuple of classification labels is encrypted with a first public key that is paired with a first private key that is accessible to the first server but not the second server, and
wherein the tuple of thresholds is encrypted with a second public key that is paired with a second private key that is accessible to the second server but not the first server.

### Claim 13 (depends on 9)

The system of claim 9, wherein the set of attributes is associated with a user, wherein the decision tree comprises a classification model trained on one or more previously-obtained sets of attributes associated with the user, and wherein the classification result indicates whether the user should or should not be authenticated.

### Claim 14 (depends on 13)

The system of claim 13, wherein the set of attributes associated with the user comprise one or more of:
behavioral attributes associated with the user; or
biometric attributes associated with the user.

### Claim 15 (depends on 9)

The system of claim 9, wherein the first server and the second server are configured to communicate with each other directly or indirectly via one or more intermediaries.

### Claim 16

A non-transitory computer-readable device having instructions stored thereon that, when executed by a first server, cause the first server to perform operations for evaluating a decision tree in a privacy preserving manner, the operations comprising:
receiving a first partial share of the decision tree and encrypted input data from a client, wherein the encrypted input data comprises a set of attributes;
communicating with a second server that has received a second partial share of the decision tree to compute a classification result over the encrypted input data, wherein the first server and the second server are each configured to compute the classification result over the encrypted input data using the respective partial share of the decision tree received thereby and secure multi-party computation methods, including additive homomorphic encryption and oblivious transfer, such that the classification result is determine without decrypting the encrypted input data, and such that the classification result is ultimately received by the first server; and
transmitting the classification result to the client.

### Claim 17 (depends on 16)

The non-transitory computer-readable device of claim 16, wherein the decision tree comprises a full binary decision tree.

### Claim 18 (depends on 16)

The non-transitory computer-readable device of claim 16, wherein the decision tree comprises a plurality of decision nodes and a plurality of leaf nodes,
wherein the first partial share of the decision tree comprises a tuple of thresholds respectively associated with decision nodes of the decision tree and a tuple of attribute indices respectively associated with the decision nodes of the decision tree, and
wherein the second partial share of the decision tree comprises a structural description of the decision tree and a tuple of classification labels respectively associated with the leaf nodes of the decision tree.

### Claim 19 (depends on 18)

The non-transitory computer-readable device of claim 18, wherein the tuple of classification labels is encrypted with a first public key that is paired with a first private key that is accessible to the first server but not the second server, and
wherein the tuple of thresholds is encrypted with a second public key that is paired with a second private key that is accessible to the second server but not the first server.

### Claim 20 (depends on 16)

The non-transitory computer-readable device of claim 16, wherein the set of attributes is associated with a user, wherein the decision tree comprises a classification model trained on one or more previously-obtained sets of attributes associated with the user, and wherein the classification result indicates whether the user should or should not be authenticated.
