Secure integer comparison using binary trees

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.

TECHNICAL FIELD

Embodiments generally relate to multiparty computation. More specifically, embodiments relate to systems and methods of secure integer comparison using binary trees in a homomorphic encryption system.

RELATED ART

Multiparty computation (MPC) is a cryptographic technique that allows several parties to compute a function on their private inputs without revealing any information other than the function's output. Yao's Millionaires' problem is a classic MPC example which describes two millionaires that are interested in knowing which of them is richer without revealing their actual wealth. More generally, Yao's Millionaires' problem is the issue in which there are two numbers, x and y, and it is desired to determine whether the inequality x≥y is true or false without revealing the actual values of x and y.

Yao's Millionaires' problem can also be viewed as a form of integer comparison, one of the basic arithmetic operations in computer programming and algorithm design. Secure integer comparison is necessary in many privacy-preserving computations. In machine learning, private integers must be compared securely while evaluating classifiers such as decision trees or neural networks. In secure enterprise benchmarking between companies, the companies' key performance indicators must be compared without revealing to the other companies the values of the KPIs. In secure auctions, bids must be compared between bidders without revealing the bid amounts.

Previous methods of secure integer comparison utilize interactive protocols that require client interaction. Other methods rely upon excessive homomorphic encryption operations, leading to a computationally expensive comparison protocol.

Accordingly, a need exists for a more efficient and secure method of integer comparison that makes as few expensive homomorphic operations as possible while providing a non-interactive protocol.

SUMMARY

Disclosed embodiments address the above-mentioned problems by providing systems and methods for secure integer comparison using binary decision trees in a homomorphic encryption scheme. A server may receive a first encrypted input from a client. The server may create a binary tree based on a second input. In some embodiments, the second input is encrypted. The server may evaluate the first encrypted input on the binary tree to determine an encrypted comparison result. The server may send the encrypted comparison result to the client for decryption. The server may then receive the decrypted comparison result indicating whether the first input is greater than or equal to the second input without revealing the value of the first input or the second input. The secure integer comparison may be implemented using homomorphic encryption.

A first embodiment is directed to a 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 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.

A second embodiment is directed to a computer-implemented method for secure integer comparison using binary trees, the computer-implemented method comprising receiving, at a server and from a client, a first encrypted input, creating, at the server, a binary tree, the binary tree based on a second input, evaluating, at the server, the first input on the binary tree to determine an encrypted comparison result, sending, from the server to the client, the encrypted comparison result for decryption by the client, and receiving, at the server and from the client, the decryption of the encrypted comparison result. The first input may be encrypted using a fully homomorphic encryption scheme.

A third embodiment is directed to a system for secure integer comparison using binary trees, the system comprising a processor, a data store, and one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by the processor, perform a method for secure integer comparison using binary trees, the method comprising receiving, at a server and from a client, a first input, creating, at the server, a data structure, the data structure based on a second input, evaluating, at the server, the first input on the data structure to obtain an encrypted comparison result, and sending, from the server to the client, the encrypted comparison result for decryption by the client. The first input may be encrypted using an additively homomorphic encryption scheme.

DETAILED DESCRIPTION

Systems and methods for secure integer comparison are described herein. Secure integer comparison may be utilized to compare inputs from parties, wherein each party has a private integer. A branching program implemented as a binary tree may be used for the evaluation. A party having input x is considered to be the client, and a party having input y is considered to be the server. The server may construct a binary tree representing y. The client may encrypt x according to a homomorphic encryption scheme and send the encrypted x (denoted asx) to the server. The server may evaluatexon the binary tree to obtain an encrypted comparison result. The server may send the encrypted comparison result to the client for decryption. The goal of the computation is to compare the integers securely and reveal to the parties which integer is larger without revealing the values of the integers themselves. The secure integer comparison may be performed non-interactively to reduce the communication overhand and/or the computational overhead (e.g., the client's computational overhead). Further, the secure integer comparison may be output expressive, such that the comparison may be embedded into a larger protocol and further applications may be applied to the output of the comparison. In some embodiments, the server input is encrypted. In some embodiments, the client input and the server input are sent to a third-party server for evaluation.

The subject matter of the present disclosure is described in detail below to meet statutory requirements; however, the description itself is not intended to limit the scope of claims. Rather, the claimed subject matter might be embodied in other ways to include different steps or combinations of steps similar to the ones described in this document, in conjunction with other present or future technologies. Minor variations from the description below will be understood by one skilled in the art and are intended to be captured within the scope of the present claims. Terms should not be interpreted as implying any particular ordering of various steps described unless the order of individual steps is explicitly described.

The following detailed description of embodiments references the accompanying drawings that illustrate specific embodiments in which the present teachings can be practiced. The described embodiments are intended to illustrate aspects of the disclosure in sufficient detail to enable those skilled in the art to practice the present teachings. Other embodiments can be utilized, and changes can be made without departing from the claimed scope. The following detailed description is, therefore, not to be taken in a limiting sense. The scope of embodiments is defined only by the appended claims, along with the full scope of equivalents to which such claims are entitled.

Embodiments described herein utilize various homomorphic encryption (HE) schemes for performing computations on ciphertexts and for generating an encrypted result such that the decryption of the encrypted result is equivalent to the result of a function on the corresponding plaintexts. As will be discussed in further detail below, the implementation details of the secure integer comparison protocol using binary trees may vary based on the HE scheme selected. An HE scheme as used in embodiments herein may comprise the following algorithms:

PK, SK, EK←KGen(λ): A probabilistic algorithm that takes a security parameter, λ, and outputs public (PK), private (SK), and evaluation (EK) keys.

c←Enc(PK, m): The probabilistic encryption algorithm that encrypts a message, m, using PK and outputs a ciphertext, c. As used herein,mrepresents Enc(PK, m).

m′←Dec(SK, c): This deterministic algorithm takes SK and a ciphertext, c, and outputs a message m′.

In practice, an HE scheme defines two basic operations for addition and multiplication that may then be used to compute larger functionalities. An HE scheme in which both addition and multiplication operations are supported is referred to as a fully homomorphic scheme (FHE). For FHE, as used herein, the following operations and short hands may be utilized for all plaintexts m1, m2:
Addition: Add(m1,m2)=m1m2=m1+m2,
Constant Addition: AddCons(m1,m2)=m1m2=m1+m2,
Multiplication: Mul(m1,m2)=m1m2=m1·m2, and
Constant Multiplication: MulCons(m1,m2)=m1,m2=m1m2=m1·m2.

FHE schemes may further be classified into somewhat homomorphic encryption (SHE) and leveled homomorphic encryption. HE schemes that support both addition and multiplication, but only for a limited number of times, are considered to be SHEs. In leveled FHE, computations are only evaluated up to a certain circuit depth that is fixed by the encryption keys. Implementing FHE may require bootstrapping, a computationally expensive method. As such, leveled FHE may be employed to increase computational efficiency.

If the HE scheme supports only addition, the scheme is referred to as additively homomorphic (AHE). Example AHE schemes include Pallier and Elliptic Curve ElGamal. For AHE, as used herein, the following properties may be utilized for all integer plaintexts m1, m2and bit plaintexts a, b∈{0,1}:
Addition: Add(m1,m2)=m1m2=m1+m2,
Constant Multiplication: MulCons(m1,m2)=m1m2=m1·m2, and
Xor: XOR(a,b)=Add(b,MulCons(a,(−1)b))=a⊕b.

FIG.1illustrates protocol100for secure integer comparison using binary trees for some embodiments. Protocol100may be implemented using AHE, FHE, or variations thereof. The variable β is used herein to denote whether the homomorphic encryption scheme is AHE or FHE. If the scheme AHE, β=0, and if the scheme is FHE, β=1. As shown, protocol100may comprise a client102holding client input104(also referred to as x) and a server106holding server input108(also referred to as y). In some embodiments, client input104and server input108are both integers with a bitlength μ. In some embodiments, μ is public. In some embodiments, protocol100may be implemented with integers having bitlengths up to 128 bits. The goal of protocol100is to compare client input104with server input108and return an output110indicative of whether client input104is larger than or equal to server input108. In some embodiments, output110comprises a bit b indicative of whether x≥y is true. If the equality is true, output110may be one; if the equality is false, output110may be zero.

Protocol100may begin with the generation of the one-time key (PK, SK, EK) described above. In some embodiments, client102generates the one-time key and sends PK, EK to server106. In some embodiments, client102and server106share the one-time key and send PK, EK to a third-party server for evaluation. In some such embodiments, server106functions as a second client. In some embodiments, client102sends two inputs to server106or a third-party server for evaluation.

Client102may encrypt client input104bitwise (using PK) to obtain encrypted client input112(denotedx=x[1], . . . , x[μ]). In some embodiments, x[μ] represents the most significant bit of client input104. Client102may send encrypted client input112to server106for evaluation. Once received, server106may create a binary tree114representative of server input108. In some embodiments, server106creates binary tree114prior to receiving encrypted client input112. In some embodiments, binary tree114is encrypted homomorphically using PK. In some embodiments, binary tree114represents all bit strings of bit length μ. Binary tree114may comprise inner nodes and terminal nodes. Each inner node may comprise two child nodes. Each terminal node may comprise zero child nodes. A node with no parent node may be referred to as the root node.

Server106then evaluates encrypted client input112on binary tree114. The evaluation may comprise comparing decision bits, aggregating decision bits, and evaluating leaves, as discussed in further detail below. Once evaluated, server106may send result116to client102. Result116may comprise the encrypted form of output110. In some embodiments, result116is encrypted with PK. As such, once received, client102may decrypt result116(using SK) to obtain output110. In some embodiments, protocol100is a non-interactive protocol such that all calculations are performed without requiring interaction by client102.

In some embodiments, shares of output110bit b are returned to server106and client102, thus preventing server106and/or client102from learning any intermediate results. In some embodiments, server106computes a bit bsand a bit bc, wherein b=bc⊕bs. Server106may store bsand send bcto client102.

At step204, server106may construct binary tree114. As discussed further below, binary tree114may comprise one of a binary comparison tree, a normal comparison binary tree, or an inverse normal comparison binary tree. In some embodiments, binary tree114represents the server input108. As discussed below, binary tree114may be pruned (half-pruned or fully-pruned) to increase efficiency of protocol100. The construction of binary tree114is discussed in further detail below with respect toFIGS.3A,3B, and4A.

At step206, when client102wishes to compare client input104against a server input108, client102may encrypt client input104using PK and send encrypted client input112to server106for evaluation. In some embodiments, client input104is encrypted bitwise, such that client102computes the bit presentationx=x[1], . . . , x[μ] and sends the corresponding ciphertextx=x[1], . . . ,x[μto server106. In some embodiments, the ordering of steps204and206are interchangeable, and binary tree114may be constructed in response to receiving client input104.

Next, at step208, server106may evaluate encrypted client input112on binary tree114. In some embodiments, the evaluation comprises comparison of decision bits, aggregation of decision bits, and evaluation of leaves to obtain result116. Evaluation of binary tree114is described in further detail below with respect toFIG.5. Evaluation of binary tree114may return result116, which may be encrypted by server106using PK.

At step210, server106may send result116back to client102. In some embodiments, if method200is implemented using FHE, result116comprises a single encrypted bit. In some embodiments, if method200is implemented using AHE, result116comprises μ ciphertexts among which at most one of the μ ciphertexts encrypts 0 and the remaining ciphertexts encrypt random plaintext. Decryption of result116is discussed in further detail below with respect toFIGS.6A and6B.

FIG.3Aillustrates a first method300of creating binary tree114for some embodiments. At step302, binary tree114may be initialized. In some embodiments, binary tree114is created to represent all bit strings of length μ. As such, initialization of binary tree114may comprise creating a binary tree114with all edges labeled with one or zero. At step304, once binary tree114is initialized, the path in binary tree114that represents server input108may be identified. The path representing server input108may comprise the path with edge labels corresponding to the binary representation of server input108starting from the most significant bit of server input108at the root node. The path on binary tree114representing server input108is referred to hereinafter as path p. Next, at step306, the leaf of path p and the leaves of all paths to the right of path p on binary tree114may be labeled with one. At step308, leaves to the left of path p on binary tree114may be labeled with zero. At this point, binary tree114may be fully complete, with all leaf nodes labeled with ones or zeroes. As such, traversing binary tree114with bits of encrypted client input112may lead to a leaf node labeled with zero if client input104is less than server input108, and may lead to a leaf node labeled with one if client input104is greater than or equal to server input108.

At optional step310, subtrees of binary tree114may be pruned. Pruning binary tree114may result in a simpler binary tree114and a more efficient protocol100because pruned subtrees may not have to be evaluated by server106. In some embodiments, all subtrees that are labeled with the same bit are pruned. That is, if an inner node of binary tree114comprises two child nodes labeled with the same bit b, the child nodes of the inner node may be removed from the tree. Thereafter, the inner node may be transformed into a leaf node. In some embodiments, the inner node is transformed into a leaf node and labeled with the bit b.

Constructing a binary comparison tree according to method300may result in a binary tree114that is unnecessarily large. In some embodiments, binary tree114may be pruned to simplify binary tree114without losing the meaning provided by the full binary tree114generated according to the method300. Binary tree114may be pruned to be full-pruned or half-pruned. A full-pruned binary tree114comprises a binary tree in which no inner node has child nodes comprising leaves with the same label. A half-pruned binary tree114comprises a binary tree having a depth of bitlength equivalent to server input108and, for each non-deepest inner node, exactly one child node is a leaf node. For a binary tree114, the tree depth is equivalent to the number of edges on the longest path. The depth of a node is equivalent to the number of edges between the node and the root node. A deepest inner node comprises a node whose child nodes are both leaf nodes with a node depth equivalent to the depth of binary tree114.

Looking now atFIG.3B, a second method350of creating binary tree114is illustrated for some embodiments. Method350outlines a method of creating a pruned binary tree114without creating a full binary tree and then pruning subtrees. In some embodiments, creating the full binary tree114(representing all bit strings of length μ) and then pruning the full binary tree114as described above may be avoided by traversing binary tree114a single time with the bits of server input108and replacing non-traversed subtrees with a leaf node. Method350may begin at step352where the root node of binary tree114may be initialized and an index, i, is set to μ, (i.e., the most significant bit of server input108). At this point, binary tree114may comprise only the root node and no other nodes.

At step354, it may be determined whether the bit (i.e., y[i]) of server input108, at index i is equivalent to one. If the bit is equivalent to one, processing may proceed to step356. If the bit is not equivalent to one (i.e., the bit is zero), processing may proceed to step362.

At step356, where y[i]=1 is true, a leaf node may be inserted on the left of the node and labeled with zero. In some embodiments, step356is optional and only performed in the FHE scheme. In some embodiments, in the AHE scheme, when y[i]=1 is true, a leaf node on the left is not inserted, and processing proceeds to step358. At step358, a new node may be inserted on the right of the leaf node. At step360, binary tree114may be traversed to the right of the leaf node to the new node and i is decremented. Next, at step368, it may be determined if i=0 is true or false. If true, processing may proceed to optional step370whereby the new node inserted at step358is labeled with β. In some embodiments, step370is only implemented in the FHE scheme.

At step362, where y[i]=0, a leaf node may be inserted on the right of the node and labelled with one. Thereafter, at step364, a new node may then be inserted to the left of the leaf node. At step366, binary tree114may be traversed to the left of the leaf node, to the new node, and i is decremented. Next, at step368, it may be determined if i=0 is true or false. If true, processing may proceed to optional step370whereby the new node inserted at step364is labeled with β. In some embodiments, step370is only implemented in the FHE scheme.

As described above, when binary tree114is implemented in a AHE scheme, no leaf node is inserted on the left of the traversed path when y[i]=1. As such, in some embodiments, binary tree114may comprise only paths which can be evaluated to zero. That is, binary tree114may comprise paths labeled with integers that are larger than or equal to server input108.

As previously mentioned, protocol100may be ran with server input108encrypted or unencrypted. Leaving server input108unencrypted may be permissible when server106is performing the homomorphic operations on server input108and client input104. However, when client102and server106send client input104and server input108to a separate server, server input108may be encrypted to protect the privacy of server input108. For example, in a secure auction setting, client102and server106(server106functioning as a second client102) may be two bidders who send their input to an auction-hosting server for secure integer comparison to determine the highest bidder. Encrypting server input108may therefore be advisable for enhanced privacy. Encrypting server input108may still be advisable when server106implements protocol100to increase security against malicious parties. When both client input104and server input108are encrypted, server106may perform comparison of client input104and server input108with the help of client102or another server having the decryption key. In some embodiments, server106only requires the aid of client102or another server in the AHE scheme.

To handle encrypted inputs in the FHE scheme, server106may construct a binary tree114as described above. As previously described, binary tree114may comprise a binary tree in which edges and leaves of binary tree114are labeled with zero or one. As such, for every integer of client input104, traversing binary tree114along a path labeled with the bits of client input104reaches a leaf labeled with one if client input104is greater than or equal to server input108and reaches a leaf labeled with zero otherwise. In some embodiments, traversal of binary tree114begins at the root node with the most significant bit of client input104. It should be noted that for secure comparison in which client input104and server input108are both encrypted, the binary tree114may be evaluated on encrypted client input112. As such, for secure comparison, in which server input108and client input104are encrypted, traversal of binary tree114is such that there is at most one path wherein client input104evaluates to one if the scheme is FHE and evaluates to zero if the scheme is AHE. For all other paths of binary tree114, client input104evaluates to zero if the scheme is FHE, and to a random plaintext that is not zero if the scheme is AHE.

In some embodiments, a normal comparison binary tree450(seeFIG.4B) is created for the case in which client input104and server input108are both encrypted. Both client input104and server input108may be encrypted using PK from the one-time key as described above. In some embodiments, client102and server106hold the one-time key and send client input104and server input108(along with PK, EK) to a third-party server for evaluation. As such, the client102and server106may know PK, SK, EK while the third-party server may only know PK.

A normal comparison binary tree450may be built based on the input size of client input104and server input108but independent of the actual values of client input104and server input108. In some embodiments, normal comparison binary tree450can be built when bits of server input108are homomorphically encrypted. For a normal comparison binary tree450, there may be a leftmost path of length μ labeled with the bits of server input108. Normal comparison binary tree450may also comprise a deepest inner node of the leftmost path comprising a left leaf node labeled with β (i.e., 1 if FHE or 0 if AHE). Further, each inner node of the leftmost path may have a right child leaf node. Additionally, each inner node may be labeled with b on the left edge, 1−b on the right edge, and Fβ(b) on the right child node of the inner node. In some embodiments, Fβ(b) depends upon whether the protocol100is implemented with an FHE scheme or an AHE scheme. For an FHE scheme, Fβ=1−bwith arithmetic encoding or Fβ=1+bfor binary encoding, as the addition is modulo two. For an AHE scheme, Fβ=b.

In some embodiments, a normal comparison binary tree450of server input108is equivalent to a half-pruned binary tree114of server input108. In some embodiments, a normal comparison binary tree comprises μ+1 leaves, with at most μ leaves labeled with one in the FHE case. In some embodiments, in the AHE case, at most μ leaves are labeled with zero. In the AHE case, the paths corresponding to the leaves labeled with zero may be created and evaluated and sent back to client102. That is, if n represents the number of leaves labeled with zero in the AHE case, exactly the paths corresponding to the n leaves are created, evaluated and sent back with additional μ−n random ciphertexts to client102.

FIG.4Aillustrates a method400for creating normal comparison binary tree450for server input108for some embodiments. In some embodiments, normal comparison binary tree450may be created by computing Not-operations as¬b=1−b=ADD(1, MULCONS(b, −1)). Method400may begin after receiving server input108from server106. In some embodiments, creation of normal comparison binary tree450is performed by server106or a third-party server. At step402, server input108may be parsed and an index i may be initialized to be equivalent to the bitlength μ. As described above, server input108may be encrypted bitwise using the public encryption key. As such, parsing server input108may result in the encrypted bits of server input108(i.e.,yis parsed toy[1], . . . ,y[μ]).

Creation of normal comparison binary tree450may begin at the root node of the tree as described above. At step404, the right edge of the node may be labeled with NOTy[i]. As such, if y[i]=0, the right edge may be labeled with one, and if y[i]=1, the right edge may be labeled with zero. Next, at step406, a leaf node may be created as a right child node of the current node, and the leaf node may be labeled with Fβ(y[i]).

At step408, the left edge of the current node may be labeled withy[i]. Thereafter, at step410, a child node may be created on the left and the normal comparison binary tree450traversed thereto.

At step412, the index i may be decremented by one. At step414, a check may be performed to determine whether or not i=0. If i=0 is true, processing may proceed to step416. If i=0 is false, processing may proceed back to step404.

At step416, where i=0 is true, the child node created at step410may be labeled with β. As such, normal comparison binary tree450may comprise the leftmost path labeled with the bits of server input108.

FIG.4Billustrates an example normal comparison binary tree450created according to method400with server input108=3, μ=3, and implemented with FHE for some embodiments. As shown normal comparison binary tree450comprises a root node452, edge labels454, leaf nodes456, and inner nodes458. As described above, creation of normal comparison binary tree450may begin at root node452. As such, for the edge label454on the right of root node452, the value is NOT0=1. Similarly, for the edge label454on the right of root node452, the value is0. Additionally, for the right leaf node456, the value is Fβ=1−b=1. A left child node may then be created and the above-described process repeated for the rest of normal comparison binary tree450.

In some embodiments, server106can choose between evaluating the greater-than or the less-than case. The greater-than case may be with binary tree114or normal comparison binary tree450. To evaluate the less-than case, an inverse normal comparison binary tree may be created. The inverse normal comparison binary tree may comprise a rightmost path of length μ labeled with the bits of server input108. Additionally, there may be a deepest inner node of the rightmost path having a left leaf node labeled with β. Each inner node of the inverse normal comparison binary tree may comprise a left child leaf node.

An inverse normal comparison binary tree may be created according to method400outlined above with the following differences. All leaf nodes, except for the leftmost leaf node, may be labeled with 1−Fβ(b). Each inner node may comprise a left edge label454labeled with b and a right edge label454labeled with 1−b.

FIG.5illustrates a method500for evaluating client input104on binary tree114for some embodiments (binary tree114is used hereinafter as representative of normal comparison binary tree450and its inverse). As described above, evaluation of binary tree114may comprise the computation of decision bits, (outlined in steps502and504), aggregation of comparison bits (outlined in steps506and508), and evaluation of leaves (outlined in steps510-520).

At step502, decision bits may be computed. As described above, client102may encrypt client input104to obtain encrypted client input112which may be sent to server106. Server106may then evaluate encrypted client input112by computing decision bits. In some embodiments, server106computes decision bits by comparing each ciphertext bit of encrypted client input112(i.e.,x[i]) against edge labels454of a node of binary tree114. The comparison may comprise a bit equality test.

At step504, the comparison results are returned. If the two bits are equal, the bit equality test may return encrypted one (i.e.,1). If the two bits are unequal, the bit equality test may return encrypted zero (i.e.,0). In some embodiments, if protocol100utilizes an FHE scheme, an FHE XNORgate is utilized for comparing decision bits. In some embodiments, if protocol100utilizes an AHE scheme, the inequality is implemented using an AHE XORgate. In some embodiments, edge labels454of binary tree114are not encrypted in an AHE scheme. For the AHE case in which client input104and server input108are both encrypted, comparison of decision bits may comprise applying XOR-operations on the bits of encrypted client input112along paths of normal comparison binary tree450. In some embodiments, an XOR-operation on two encrypted bitsaandbis computed asa⊕b=a−b.

Next, at step506, the comparison bits determined above may be aggregated. In some embodiments, comparison bits are aggregated along the path from root node452to each leaf node456in binary tree114. If the scheme is FHE, the comparison bits may be aggregated using homomorphic multiplication of the comparison bits. If the scheme is AHE, the comparison bits may be aggregated using homomorphic addition of the comparison bits.

When comparing and aggregating comparison bits in an AHE scheme, if XOR-results of a path comprise1and−1(i.e., the XOR-operation of two encrypted bitsaandbis computed asa⊕b=a−b), the aggregation of such a path may also evaluate to zero. Thus, to alleviate this issue (since this path should not result to zero), the XOR-result may be multiplied at level i (i.e., edges starting at a node with depth i) by 2iprior to aggregating the results along the paths. Because 2iis a constant number, the multiplication can be applied on an AHE ciphertext. As such, after multiplying by 2i, the aggregation of the path may no longer evaluate to zero.

At step508, the aggregation result may be stored at the leaf node456of the corresponding path upon which the comparison bits were aggregated. In some embodiments, aggregation is implemented using a queue and traversing binary tree114in BFS (Breadth-first search) order. Alternatively, or additionally, binary tree114may be traversed using depth-first search, iterative deepening search, or any other tree searching algorithm. In some embodiments, the aggregation computation may be improved by using path prefixes for binary tree114. In some embodiments, for two or more paths having the same prefix, the prefix is evaluated a single time. After comparison and aggregation of the bits, processing may proceed to step510if the HE scheme is fully homomorphic, or to step516if the HE scheme is additively homomorphic.

At step510, for FHE encryption, a cost attribute at each leaf node456of binary tree114may be aggregated. After the aggregation outlined in step506is complete, each leaf node456may store a cost value. In some embodiments, each leaf node456of binary tree114stores a cost value of encrypted zero (0) or a cost value of encrypted one (1). In some embodiments, there is a unique leaf node456in binary tree114storing a cost of1, with all other leaf nodes storing a cost of0. Server106may then aggregate the cost value for each leaf node456by computing, the product of the cost of the leaf node456with the value of the label of leaf node456. At step512, the result of the computation may then be summed across all leaf nodes456in binary tree114to obtain result116. At step520, result116may be sent to client102.

For AHE, after aggregation of the comparison bits, each leaf node456in binary tree114may store a cost value of0or a cost value of an encrypted random plaintext (r). In some embodiments, binary tree114comprises at most one leaf node456with a cost of0, and all other leaf nodes456in binary tree114comprise a cost ofr. As such, at step514, server106may randomize all ciphertexts. At step516, additional random ciphertexts may be generated by server106and added into the list of already-present ciphertexts. Next, at step518, server106may permute all ciphertexts. Lastly, processing may proceed to step520whereby server106sends result116(in the form of p permuted ciphertexts) to client102, thus preserving the privacy of server106. Randomization and permutation of the ciphertexts may also aid in preventing leakage of the structure of binary tree114. Leakage of tree structure may allow for malicious actors to obtain information about server input108.

In the AHE scheme with both inputs encrypted, if client input104is greater than or equal to server input108, exactly one path of binary tree114may have XOR-results equal to zero, such that the sum along the paths is zero. The remaining paths of the normal comparison tree may have at least one XOR-result that is not zero, thus resulting in an aggregation of comparison bits that is not zero. Consequently, a path result is the aggregation of comparison bits along it and the final comparison result116may be determined by checking if there is a path result that is zero.

FIG.6Aillustrates a method600for decrypting result116in a FHE scheme for some embodiments. As described in step520above, server106may send result116back to client102for decryption to learn the output110. For a FHE scheme, result116may be sent to client102as a single encrypted bit. Once received, at step602, client102may parse result116to obtain an encrypted bitb. At step604, the encrypted bit may be decrypted using SK. Thereafter, at step606, output110may be obtained comprising the comparison result between client input104and server input108. In some embodiments, client102may then share the comparison result with server106.

FIG.6Billustrates a method650for decrypting result116in an AHE scheme. As described above, for an AHE scheme, result116may comprise μ ciphertexts with at most one ciphertext encrypting 0 and the remaining ciphertexts encrypting a random plaintext. At step652, client102may parse result116to obtain a list of μ ciphertexts. At step654, client102may iteratively decrypt the list of ciphertexts. Decryption may be performed using the private key SK from the one-time key generation. Each ciphertext, when decrypted, may return zero or a random value. At step656, output110may be obtained. If any of the decrypted bits returned zero, client102may learn that client input104was greater than or equal to server input108. Otherwise, if none of the decrypted ciphertexts returned zero, client102may learn that client input104was not greater than or equal to server input108.

Protocol100and the above-described methods may be modified for certain use cases. For example, as described above, in an AHE scheme, creating binary tree114according to method300and/or method350may result in a binary tree114comprising only paths that can evaluate to zero (i.e., paths that are labeled with integers larger than or equal to server input108). Recall that for the AHE case, server106may send μ ciphertexts (i.e., one ciphertext for each path in binary tree114) to client102as result116. If server input108is zero, because all paths may be larger than or equal to zero, the resulting binary tree114may comprise μ+1 leaves, thus result116may comprise μ+1 ciphertexts. If μ+1 ciphertexts are sent back to client102, client102may be able to learn more information than just the desired output110. As such to handle the AHE case wherein server input108is zero, when creating binary tree114, server106may replace the first encrypted bit of client input104(i.e.,x[μ]) with a ciphertext of 0 (0) and omit the rightmost path of binary tree114during evaluation of binary tree114.

Another use case which may require modifications to protocol100occurs when output110is shared between client102and server106. In two-party comparison protocols, such as the Damgard-Geisler-Kroigaard (DGK) comparison protocol and variations thereof, it is common for client102and server106to share output110in the form of a comparison bit b. In such an embodiment, output110may be split into bs, held by server106, and bc, sent from server106to client102, such that b=bc⊕bs. In some embodiments, server106may choose between computing greater-than (i.e., client input104≥server input108) or less-than (i.e., client input104≤server input108) functionality when implementing protocol100as described above. In some embodiments, server106flips a random coin, bs, to determine whether to compute greater than functionality or less than functionality. If the random coin flip returns zero, the greater than functionality may be computed, otherwise the less than functionality may computed by creation of the inverse normal comparison binary tree.

FIG.7Aillustrates a binary tree array702corresponding to the example normal comparison binary tree450illustrated inFIG.4Bfor some embodiments. In some embodiments, a simpler data structure than binary tree114may be utilized for the secure integer comparison and evaluation to improve computational efficiency. As illustrated inFIG.7A, binary tree array702may be constructed and used to evaluate the inequality between client input104and server input108. Evaluating binary tree array702instead of binary tree114may result in increased computational efficiency. In some embodiments, binary tree array702comprises a two-dimensional array a[(1, . . . , μ), (1,2,3)] comprising μ+1 rows and three columns. In some embodiments, binary tree array702is initialized with normal comparison binary tree450based on server input108.

In the first column, binary tree array702may store the edge labels454from the leftmost path of normal comparison binary tree450(i.e., the binary representation of server input108). The second column may store the right-oriented paths, starting from the first row of binary tree array702to the last row of binary tree array702. As such, the bottom row and the rightmost row of binary tree array702may store the labels of leaf nodes456of normal comparison binary tree450. In some embodiments, in the bottom row of binary tree array702, only the first cell is filled. The first cell in the bottom row may be one if FHE and zero if AHE. Binary tree array702may be evaluated against a client input104as illustrated in evaluation array704and according to method750outlined inFIG.7B. In evaluation array704, the arrows illustrate path evaluations, wherein a→b means that a and b are aggregated and the result stored in b.

FIG.7Billustrates an exemplary method750for evaluating binary tree array702with a client input104. The evaluation of binary tree array702is illustrated in evaluation array704, corresponding to an example case wherein client input104equals one. As described above, client102and server106may encrypt their inputs and send them to a third-party server for evaluation. At step752, the encrypted client input112and encrypted server input108may be parsed into encrypted bits, and binary tree array702is initialized. Next, at step754, the equality of the current bits is stored in the first cell of each row. That is, xi⊕yimay be computed for each encrypted bit of client input104and server input108.

At step756, the negation of the equality of the current bits of client input104and server input108may be stored in the second cell for each row. In some embodiments, xi⊕yimay be computed for each encrypted bit of client input104and server input108. At step758, Fβ(y[i]) may be stored in the third cell. Step754, step756, and step758substantially correspond to the computation of decision bits, aggregation of decision bits, and storing the aggregation at leaf nodes456as outlined above with respect to steps502-508.

At step760, the first row of evaluation array704may be evaluated. In some embodiments, the first row of evaluation array704is evaluated differently from the rest of the rows in evaluation array704. For the first row, the second and third cell may be multiplied together, and the result may be stored in the third cell. The multiplication operation is indicated by the arrow from the second cell to the third cell. As such, for the example shown inFIG.7A, 0 is multiplied by 1 and the result 0 is stored (not shown) in the third cell. As such, Fβ(y[i]), calculated at step758and stored in the third cell, may be overwritten, and replaced with the multiplication result at step760.

Next, at step762, the remaining rows of the binary tree array702may be evaluated. For the remaining rows, a[i,1] and a[i−1,1] may be multiplied together and stored in a[i, 1], corresponding to the aggregation of the leftmost path of binary tree array702. Additionally, a[i−1, 1], a[i, 2], and a[i, 3] may be multiplied together, and the result is stored in a[i, 3], corresponding to the evaluations of the paths having right child nodes. After these multiplications, the first cell of the last row (which was initially 1 if FHE or 0 if AHE, now holds the aggregation of comparison bits on the leftmost path) may then be copied over to the last cell of the last row, as indicated with the dashed arrow in evaluation array704.

Processing may then proceed to step764if the scheme is FHE or step766if the scheme is AHE. At step764, the third column of binary tree array702is summed. This corresponds to evaluation of leaf nodes456as described above. Once summed, at step768, result116may be sent to client102for decryption. If the scheme is AHE, at step766, the third column may be permuted. At step768, the permutation is sent back to client102with ciphertexts randomized for decryption.

In some embodiments, for the constant case (i.e., the server input y is unencrypted), the implementation may be further optimized by having client102sendx[i]⊕1to server106instead ofx[i]. As such, server106may only need to computex[i]⊕0=¬(x[i]⊕1, thereby reducing the number of additions by the bitlength μ of client input104and server input108without any increase in the communication cost. The computation of client102as x[i]⊕1 may be done in plaintext before being encrypted.

For the FHE scheme, the multiplicative depth of the procedure may be relevant if the FHE scheme is a leveled FHE scheme, wherein multiplication operations are only supported until a certain depth without bootstrapping as described above. In some embodiments, a leveled FHE scheme has a fixed parameter L such that circuits with depth at most L can be evaluated without bootstrapping. In some embodiments, the inner nodes of binary tree114are evaluated as described above using XORoperations, while multiplication uses a direct acyclic graph. In some embodiments, the direct acyclic graph comprises a graph with directed edges in which there are no cycles. This evaluation is illustrated inFIG.8.

To evaluate the direct acyclic graph, a dependency list table804may be computed for each element of binary tree array702. Left table802corresponds to binary tree array702wherein the cells have been renumbered 1 to 10 for clarity of illustration. In some embodiments, the dependency list is a stack, represented as [), with bottom [ and top ), that comprises the cells' numbers along a multiplication path, whereby the multiplication path is the set of cells that must be multiplied together. For left table802, the multiplication paths are (1, 4, 7, 10), (1, 4, 8, 9), (1, 5, 6), and (2, 3) in the illustrated example. Each multiplication path is evaluated by first identifying a list of nodes. To identify the nodes, elements are grouped into pairs. The first element in a pair is added to the dependency list of the second element in the pair. The node list may then be reduced by all elements that occur in any dependency list. These steps may then be repeated until there is only a single element left. For example, if a multiplication path comprises nodes a, b, c, d, in this order, then the dependency lists are as follows: [), [a), [), [b, c). Notably, the computation of dependency list table804does not depend on server input108but rather on the structure of the binary tree. As such, advantageously, the dependency list table804may be computed a single time and given as an input to protocol100.

Evaluation table806illustrates the evaluation of dependency list table804. The arrows shown in evaluation table806are computed according to the dependency list. That is, if cell b has a in its dependency list, then there is an arrow a→b. The solid arrows have a multiplicative depth of one, and the dashed arrows have a multiplicative depth of two. As described above, the multiplication stage of protocol100may be done using dependency list table804. For the multiplication, evaluation table806may be traversed from top to bottom and from left to right, with the aggregated result of each cell computed using its dependency list. For example, using the dependency lists [), [a), [), [b, c), there is nothing to do for nodes a and c because their dependency lists are empty. For node b, b←a·b may be computed. For node d, d←c·d may first be computed, followed by d←b·d. Following this procedure, the use of the dependency list table804may reduce the multiplication depth on a binary tree114having a path of length k from k to log(k).

As mentioned above, embodiments herein may have applications in various fields such as machine learning, secure auctions, benchmarking, and the like. Protocol100may be output expressive and integrated as part of a larger application. Output110may have further operations applied thereto once determined decrypted by client102. In some embodiments, server106may send result116for further applications.

While embodiments have been described herein with respect to comparing integers between a client-server pair, it should be noted that protocol100may be ran with multiple clients. For example, in a secure auction setting, protocol100may be ran with all auction participants. A first pair of participants may be selected to send their bids to an auction host. One participant in the pair may function as client102, and the second participant in the pair may function as server106. Both participants may send their inputs encrypted to the auction host. Once the highest bidder is determined with protocol100, the auction host may pair the highest bidder with another auction participant. This process may then repeat until the overall highest bidder is determined. As such, the auction participants may have their bids securely compared without any of the other participants or the auction host learning the actual value of their bids.

Turning now toFIG.9, in which an exemplary hardware platform for certain embodiments is depicted. Computer902can be a desktop computer, a laptop computer, a server computer, a mobile device such as a smartphone or tablet, or any other form factor of general- or special-purpose computing device containing at least one processor. Depicted with computer902are several components, for illustrative purposes. In some embodiments, certain components may be arranged differently or absent. Additional components may also be present. Included in computer902is system bus904, via which other components of computer902can communicate with each other. In certain embodiments, there may be multiple busses or components may communicate with each other directly. Connected to system bus904is central processing unit (CPU)906. Also attached to system bus904are one or more random-access memory (RAM) modules908. Also attached to system bus904is graphics card910. In some embodiments, graphics card910may not be a physically separate card, but rather may be integrated into the motherboard or the CPU906. In some embodiments, graphics card910has a separate graphics-processing unit (GPU)912, which can be used for graphics processing or for general purpose computing (GPGPU). Also, on graphics card910is GPU memory914. Connected (directly or indirectly) to graphics card910is display916for user interaction. In some embodiments no display is present, while in others it is integrated into computer902. Similarly, peripherals such as keyboard918and mouse920are connected to system bus904. Like display916, these peripherals may be integrated into computer902or absent. Also connected to system bus904is local storage922, which may be any form of computer-readable media, such as non-transitory computer readable media, and may be internally installed in computer902or externally and removably attached.

Finally, network interface card (NIC)924is also attached to system bus904and allows computer902to communicate over a network such as network926. NIC924can be any form of network interface known in the art, such as Ethernet, ATM, fiber, Bluetooth, or Wi-Fi (i.e., the Institute of Electrical and Electronics Engineers (IEEE) 802.11 family of standards). NIC924connects computer902to local network926, which may also include one or more other computers, such as computer928, and network storage, such as data store930. Generally, a data store such as data store930may be any repository from which information can be stored and retrieved as needed. Examples of data stores include relational or object-oriented databases, spreadsheets, file systems, flat files, directory services such as LDAP and Active Directory, or email storage systems. A data store may be accessible via a complex API (such as, for example, Structured Query Language), a simple API providing only read, write, and seek operations, or any level of complexity in between. Some data stores may additionally provide management functions for data sets stored therein such as backup or versioning. Data stores can be local to a single computer such as computer928, accessible on a local network such as local network926, or remotely accessible over public Internet932. Local network926is in turn connected to public Internet932, which connects many networks such as local network926, remote network934or directly attached computers such as computer936. In some embodiments, computer902can itself be directly connected to public Internet932.

Many different arrangements of the various components depicted, as well as components not shown, are possible without departing from the scope of the claims below. Embodiments have been described with the intent to be illustrative rather than restrictive. Alternative embodiments will become apparent to readers of this disclosure after and because of reading it. Alternative means of implementing the aforementioned can be completed without departing from the scope of the claims below. Certain features and subcombinations are of utility and may be employed without reference to other features and subcombinations and are contemplated within the scope of the claims. Although the present teachings have been described with reference to the embodiments illustrated in the attached drawing figures, it is noted that equivalents may be employed, and substitutions made herein without departing from the scope of the present teachings as recited in the claims.