US 2023/0155815 A1 · SECURE INTEGER COMPARISON USING BINARY TREES

Abstract

Systems, methods, and computer-readable media are disclosed for secure integer comparison using binary trees. A server may receive a first encrypted input and a public encryption key from a client. The server may create a binary tree representing a second encrypted input. The server may evaluate the first encrypted input on the binary tree. The evaluation may comprise computing decision bits along a plurality of paths of the binary tree. The decision bits may then be aggregated along each path of the binary tree and the aggregation stored at a leaf node of each path. The leaf node of each path may be evaluated to obtain a comparison result. The comparison result may be encrypted with the public encryption key. The server may send the comparison result to the client for decryption. The comparison result may indicate whether the first input was larger than the second input.

Claims20

Dependent claims

One or more non-transitory computer-readable media storing computer-executable instructions that, when executed by a processor, perform a method for secure integer comparison using binary decision trees, the method comprising:

receiving, at a server and from a client, a public encryption key and a first encrypted input, the first encrypted input encrypted with the public encryption key;
creating, at the server, a binary tree, the binary tree based on a second encrypted input;
evaluating, at the server, the first encrypted input on the binary tree, the evaluation comprising:
computing decision bits along a plurality of paths of the binary tree;
aggregating the decision bits along each path of the binary tree, the aggregated decision bits stored at a leaf node of each path;
and
evaluating the leaf node of each path to obtain an encrypted comparison result;
and
sending, from the server to the client, the encrypted comparison result for decryption by the client, the encrypted comparison result encrypted using the public encryption key.

6 more elements

Dependencies are inferred from the claim text.

Secure integer comparison using binary trees

Life of this patent

Secure integer comparison using binary trees

Life of this patent

Abstract

Claims20