Method and system for outsoursing decision-tree inference and obfuscating decision-tree attributes

A second device comprising a second processor, the second processor configured to:

• receive, from a third device, a public key indicative of a second matrix, wherein a first device receives a secret key indicative of a first matrix from the third device;
• receive second shares of the thresholds and attributes associated with corresponding non-leaf nodes of a second share of a permuted decision tree from the third device, wherein the first device computes first shares of thresholds associated with non-leaf nodes of a first share of the permuted decision tree using a seed received from the third device;
• execute, iteratively, a set of steps for traversing the permuted decision tree until a leaf node is encountered, wherein the set of steps comprises:
• receive an encrypted masked query data from the first device, wherein a masked query data is encrypted by the first device to generate the encrypted masked query data,
• wherein the first device generates the masked query data from a permuted query data using a mask variable selected by the first device, wherein the mask variable is a positive integer, wherein the masked query data is generated based on an accumulation of the mask variable with each element of the permuted query data,
• wherein the first device generates the permuted query data from an original query data comprising a sequence of attribute values, and wherein the sequence of attribute values is altered based on a permutation matrix to generate the permuted query data,
• generate a fully permuted query data based on the second matrix and the encrypted masked query data, wherein the fully permuted query data is generated based on computation of a product of the second matrix and the encrypted masked query data,
• receive, from the first device, a masked version of a first share of a threshold associated with a non-leaf node of the first share of the permuted decision tree, wherein the masked version of a first share of a threshold associated with the non-leaf node is generated based on an accumulation of the selected mask variable and the first share of the threshold associated with the corresponding non-leaf node,
• perform a secure comparison operation based on an element of the fully permuted query data, the masked version of the first share of the threshold associated with a non-leaf node of the first share of the permuted decision tree, and a second share of the threshold associated with a corresponding non-leaf node of the second share of the permuted decision tree, wherein the non-leaf node is a root node of the first share of the permuted decision tree and the corresponding non-leaf node is a root node of the second share of the permuted decision tree at a first iteration,
• select a second child node of the corresponding non-leaf node based on the outcome of the secure comparison operation, wherein the second child node is the corresponding non-leaf node of the second share of the permuted decision tree at a subsequent iteration, and wherein the second child node is a corresponding second leaf node of the second share of the permuted decision tree at a final iteration, and
• transmit the outcome of the secure comparison operation to the first device, wherein the first device selects a first child node of the non-leaf node based on the outcome of the secure comparison operation, wherein the first child node is the non-leaf node of the first share of the permuted decision tree at the subsequent iteration, and wherein the first child node is a first leaf node of the first share of the permuted decision tree at the final iteration;
• and
• transmit, to the first device, a second share of the classification result generated based on a label associated with the corresponding second leaf node, wherein the first device generates a first share of a classification result based on a label associated with the first leaf node, and wherein the first device generates a decision tree classification result based on the first share of the classification result and the second share of the classification result.

A method comprising:

• obtaining a permuted query data from an original query data comprising a sequence of attribute values, wherein the sequence of attribute values is altered based on a permutation matrix to obtain the permuted query data;
• receiving a secret key indicative of a first matrix from a third device, wherein the first matrix is an invertible matrix, and wherein a second device receives a public key, indicative of a second matrix, from the third device;
• receiving a seed from the third device that enables computation of first shares of thresholds associated with non-leaf nodes of a first share of a permuted decision tree, wherein second shares of the thresholds and attributes associated with corresponding non-leaf nodes of a second share of the permuted decision tree are received by the second device from the third device;
• executing, iteratively, a set of steps for traversing the permuted decision tree until a leaf node is encountered, wherein the set of steps comprises:
• selecting a mask variable to generate a masked query data from the permuted query data, wherein the mask variable is a positive integer,
• encrypting the masked query data based on computation of a product of the first matrix and the masked query data,
• transmitting the encrypted masked query data to the second device, wherein a fully permuted query data is generated by the second device based on the second matrix and the encrypted masked query data,
• receiving, from the second device, an outcome of a secure comparison operation performed based on an element of the fully permuted query data, a masked version of a first share of a threshold associated with a non-leaf node of the first share of the permuted decision tree, and a second share of the threshold associated with a corresponding non-leaf node of the second share of the permuted decision tree, wherein, at a first iteration, the non-leaf node is a root node of the first share of the permuted decision tree and the corresponding non-leaf node is a root node of the second share of the permuted decision tree, and
• selecting a first child node of the non-leaf node based on the outcome of the secure comparison operation, wherein a second child node of the corresponding non-leaf node is selected based on the outcome of the secure comparison operation, wherein, at a subsequent iteration, the first child node is the non-leaf node of the first share of the permuted decision tree and the second child node is the corresponding non-leaf node of the second share of the permuted decision tree, wherein the first child node is a first leaf node of the first share of the permuted decision tree at a final iteration, and wherein the second child node is a corresponding second leaf node of the second share of the permuted decision tree at the final iteration;
• generating a first share of a classification result based on a label associated with the first leaf node;
• receiving, from the second device, a second share of the classification result generated based on a label associated with the corresponding second leaf node stored in the corresponding second leaf node;
• and
• generating a decision tree classification result based on the first share of the classification result and the second share of the classification result.

A system comprising:

• a first device comprising a first processor;
• a second device comprising a second processor;
• and
• a third device comprising a third processor, the third processor configured to:
• transmit an attribute sequence vector to the first device to enable the first device to generate a permuted query data,
• transmit a secret key indicative of a first matrix to the first device,
• transmit a public key indicative of a second matrix to the second device,
• obtain a permuted decision tree, wherein each non-leaf node of the permuted decision tree includes an attribute and a threshold,
• split the permuted decision tree into a first share of the permuted decision tree and a second share of the permuted decision tree,
• transmit a seed to the first device to enable the first device to compute first shares of thresholds associated with non-leaf nodes of a first share of the permuted decision tree and first shares of labels associated with leaf nodes of the first share of the permuted decision tree, and
• transmit, to the second device, the second share of the permuted decision tree including second shares of the thresholds associated with corresponding non-leaf nodes of the second share of the permuted decision tree, second shares of labels associated with corresponding leaf nodes of the first share of the permuted decision tree, and attributes associated with the corresponding non-leaf nodes of the second share of the permuted decision tree.