PRIORITY CLAIM

[0001] The present application claims priority to U.S. Provisional Application No.

63/380,109, October 19, 2022, the content of which is incorporated herein in its entirety.

FIELD OF THE INVENTION

[0002] The present disclosure relates to a fast secure multiparty comparison approach optimized for common computing architectures.

BACKGROUND

[0003] The comparison of two numbers is a fundamental step in many computations. For example, comparison functions can be used to compute the weights in the network where f(x)=x if x is positive and equals 0 otherwise. In particular, x can be compared to 0. As another example, both in training and evaluation, decision trees use comparisons to determine which features of the data are most relevant (e.g., provide the most information gain), and evaluate which path in the decision tree should be followed for input data.

[0004] The comparison of two numbers becomes more complicated when the numbers are encrypted, or when each of the numbers is “split” across multiple parties so that no single party can see the numbers, but collectively the parties “share” the numbers - e.g., as the sum of their shares of the numbers.

BRIEF SUMMARY

[0005] The following presents a simplified summary relating to one or more aspects disclosed herein. Thus, the following summary should not be considered an extensive overview relating to all contemplated aspects, nor should the following summary be considered to identify key or critical elements relating to all contemplated aspects or to delineate the scope associated with any particular aspect. Accordingly, the following summary has the sole purpose to present certain concepts relating to one or more aspects relating to the mechanisms disclosed herein in a simplified form to precede the detailed description presented below.

[0006] A method of comparing a first number A ^bit with a second number B ^bit , the method comprising: receiving, from a first computing device associated with the first number A ^bit , a share a ₁ ^bit and a share b ₁ ^bit ; receiving, from a second computing device associated with the second number B ^bit , a share a ₂ ^bit and a share b ₂ ^bit , wherein the first number A ^bit = a ₁ ^bit + a ₂ ^bit mod 2 ⁶⁴ and wherein the second number , and wherein the first number and wherein the second number wherein XOR comprises an XOR function that applies addition modulo 2 to corresponding pairs of bits of two strings; and comparing, via a comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate a shared output bit indicating which number is larger.

[0007] A system for comparing a first number A ^bit with a second number B ^bit , the system comprising: one or more processors; and one or more computer-readable memories storing instructions which, when executed by the one or more processors, cause the one or more processors to be configured to: receive, from a second computing device associated with the second number B ^bit , a share a ₂ ^bit and a share b ₂ ^bit , wherein the first number mod 2 ⁶⁴ and wherein the second number mod 2 ⁶⁴ , and wherein the first number and wherein the second number wherein XOR comprises an XOR function that applies addition modulo 2 to corresponding pairs of bits of two strings; and compare, via a comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate a shared output bit indicating which number is larger.

[0008] Other objects and advantages associated with the aspects disclosed herein will be apparent to those skilled in the art based on the accompanying drawings and detailed description. This summary is not intended to identify key or essential features of the claimed subject matter, nor is it intended to be used in isolation to determine the scope of the claimed subject matter. The subject matter should be understood by reference to appropriate portions of the entire specification of this patent, any or all drawings, and each claim.

[0009] The foregoing, together with other features and aspects, will become more apparent upon referring to the following specification, claims, and accompanying drawings.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

[0010] The accompanying drawings are presented to aid in the description of various aspects of the disclosure and are provided solely for illustration of the aspects and not limitation thereof.

[0011] FIG. 1 illustrates the comparison of two numbers;

[0012] FIG. 2 illustrates aa method aspect of this disclosure; and

[0013] FIG. 3 illustrates a computing device in according with some aspects of this disclosure. DETAILED DESCRIPTION

[0014] Certain aspects of this disclosure are provided below for illustration purposes. Alternate aspects may be devised without departing from the scope of the disclosure. Additionally, well-known elements of the disclosure will not be described in detail or will be omitted so as not to obscure the relevant details of the disclosure. Some of the aspects described herein may be applied independently and some of them may be applied in combination as would be apparent to those of skill in the art. In the following description, for the purposes of explanation, specific details are set forth in order to provide a thorough understanding of aspects of the application. However, it will be apparent that various aspects may be practiced without these specific details. The figures and description are not intended to be restrictive.

[0015] The ensuing description provides example aspects only, and is not intended to limit the scope, applicability, or configuration of the disclosure. Rather, the ensuing description of the example aspects will provide those skilled in the art with an enabling description for implementing an example aspect. It should be understood that various changes may be made in the function and arrangement of elements without departing from the scope of the application as set forth in the appended claims.

[0016] As noted above, the comparison of two numbers fundamental to many operations. For example, neural networks often apply the ReLU function (rectified linear unit) to compute the weights in the network where ReLU(x)=x if x is positive and equals 0 otherwise. Decision trees use comparisons to determine which features of the data are most relevant (e.g., provide the most information gain), and evaluate which path in the decision tree should be followed for input data.

[0017] FIG. 1 illustrates a sharing system 100 in which a network 102 such as the Internet is used to enable a first computing device controlled by Alice 104 to have a value A in which A = ai + a2. The value A is to be compared through the network with second computing device 108 owned by Bob and that has a value B such that B = ai+ a2. Alice 104 can generate two shares ai + a2 of the value A and can transmit a2 to Bob 108. Bob 108 shares the value b2 with Alice 104. After the sharing of numbers, Alice 106 (or the first computing device 106) is has ai, bi and Bob 110 (or the second computing device 1106) has a2, b2. Alice 106 does not know the value of B and Bob 110 does not know the value of A. The first computing device 106 is the same as the first computing device 104 only at a later time after which shared values are exchanged. The second computing device 1110 is the same as the second computing device 108 only at a later time after which shared values are exchanged.

[0018] Note that the “system” as disclosed herein can include a single computing device as in the computing system 300 shown in FIG. 3, or it may include the first computing device (used by Alice) 106 and the second computing device 110 (used by Bob). In some cases, the different computing devices are owned or operated by different entities and thus it is noted that all the features or operations described herein can be implemented from the standpoint of a single one of the computing devices 106, 110 in the overall system 100.

[0019] The equalities disclosed may hold modulo some number. For example, the equation A= ai + a2, mod 2 ⁶⁴ means that A - (ai+ ai) is a multiple of 2 ⁶⁴ . This disclosure may not always refer to the modulus explicitly, and it is understood that it need not always be 2 ⁶⁴ . The purpose of “sharing” a number across several parties in this way is so that no single party learns the number. In fact, the numbers ai, bi, a2, b2 can be chosen randomly so that, from Alice’s perspective, Alice’s shares ai, bi are numbers that appear completely random and independent (modulo 2 ⁶⁴ for example) from the numbers A and B, and therefore Alice’s shares convey absolutely no information about A and B. Bob’s shares, from his perspective, similarly appear to the random and independent. Of course, someone who views all of the shares ai, bi, a2, b2 can see that they correspond to A and B (by the equations above), but Alice 106 and Bob 110 in isolation each see only half of the shares, which (in isolation) appear completely independent of A and B.

[0020] Despite the fact that each party holds shares that appear - to each party in isolation - to be random and independent, the approach is to enable the parties to compare their shared numbers A and B. The innovation described here is an especially efficient secure multiparty computation (SMPC) method for determining which number is larger without revealing anything at all about these numbers, besides the result of the comparison. Even the final result of the comparison need not be revealed but can be held as a value “split” or “shared” among the parties of the comparison protocol.

[0021] In some aspects, this disclosure addresses the case where A and B are two numbers that fit in 64-bit words. Specifically, each number is mapped modulo 2 ⁶⁴ into the range [- 263 , 2 ⁶³ - 1 ] . The case is addressed where A and B are each shared between Alice and Bob as shown in FIG. 1. Alice 106 holds shares ai, bi and Bob 110 holds shares a2, b2, where ai, bi,a2, b2 are also 64-bit numbers in the range [-2 ⁶³ , 2 ⁶³ - 1 ] satisfying the equations: A=a1+ a2 mod 2 ⁶⁴ and B=b1+ b2 mod 2 ⁶⁴ . [0022] The approach has two main components. The first component is a protocol, called COMPARE-Z. The COMPARE-Z protocol takes as input two 64-bit shares a ₁ ^bit , b ₁ ^bit held by Alice 106 and two 64-bit shares A ^bit =a ₁ ^bit XOR a ₂ ^bit and B ^bit =b ₁ ^bit XOR b ₂ ^bit , where XOR is the XOR function that applies addition modulo 2 to the corresponding pairs of bits of two strings. Notice that it is preferred that the values A ^bit and B ^bit are shared bit-by-bit via XOR instead of modulo 2 ⁶⁴ .

[0023] The protocol COMPARE-Z will output a shared bit indicating the result of the comparison. That is, interpreting the 64-bit strings A ^bit and B ^bit as numbers modulo 2 ⁶⁴ , the shared output bit will indicate which numbers is larger. The innovation here is the extreme efficiency of the disclosed approach, which includes two features: (1) a very simple, natural, and minimally-complex multivariate polynomial is used to represent the comparison function in terms of the individual bits of A ^bit and B ^bit , and (2) the approach evaluates the polynomial using a recursive approach that takes advantage of fast in-built 64-bit processor instructions such as XOR, AND, and shift. Moreover, the recursive approach allows more and more intermediate results of the comparisons to be compressed together into a 64-bit word as the recursive protocol progresses, which reduces the overall complexity of the computation. Note that all of these optimizations work despite the fact that the numbers are shared. The second component of the disclosed approach is an almost cost- free reduction of our initial problem - comparing A and B when Alice 106 and Bob 110 hold shares of them modulo 2 ⁶⁴ - to the problem solved by COMPARE-Z - comparing A ^bit and B ^bit when Alice 106 and Bob 110 hold them as 64 shares modulo 2.

[0024] This component adjusts the result of COMPARE-Z based on the topmost bit of the shares held by Alice 106 and Bob 110.

[0025] Comparing two 64-Bit numbers that are shared bit-wise first using the COMPARE- Z component of the comparison protocol is discussed next. Suppose there are two 64-bit strings A ^bit and B ^bit . The system will determine whether when these 64-bit strings are interpreted as integers in the range [ - 2 ⁶³ , 2 ⁶³ - 1 ] . One can write out the binary representation of these numbers: and B Suppose that these are numbers in the range [0, 2 ⁶⁴ - 1 ] . Note that the system only needs to make slight adjustments for the range [ -2 ⁶³ , 2 ⁶³ - 1], Then, the result is that A ^bit > B ^bit if and only if Ai ^bit > Bi ^bit where i is the index of the most significant bit at which A ^bit and B ^bit differ.

[0026] One can express this condition as a polynomial as follows: COMPARE-Z Consider why the formula is correct. Notice that, for any i, it is impossible for both yu and xi to be nonzero when . Therefore, at most, one of the monomials in the above polynomial can be nonzero. If, for example X63 X62... x(i+i)yi is nonzero, it indicates that A ^bit and B ^bit have the same most significant bits, until the i-bit where Ai ^bit = 1 and Bi ^bit = 0, in which case A > B. The various monomials in the polynomial above partition the possible positions where Ai ^bit and Bi ^bit begin to differ, and overall the polynomial computes the comparison function correctly. This is in fact the minimally-complex that takes the binary representations of two numbers as input and outputs the result of their comparison.

[0027] Moreover, the polynomial above can be computed very quickly using a recursive approach. Specifically, one can define the following two polynomials: p ( ( ), , ,y( In particular, pn is precisely the comparison function, as explained above, and qn can be simply the product of the bits in x. Observe that . A recursive module or engine for example implemented as a computing device or software programmed to control a processor to perform a recursive approach to computing the data can be implemented.

[0028] That is, one can decompose the computation of pn and q _n in terms of computations of p(n/2) and q(n/2) over the most significant half of the bits and the least significant half. For example, when n = 64, the computation of p64 and q64 decomposes as two computations each of p32 and q32 which are then combined through addition and/or multiplication to obtain the final results. Each computation of p32 and q32, in turn, decomposes into two computations of pi6 and qi6 (and then an aggregation step), and so on, until at the “bottom” of the recursion process one can run 32 instances of p2 and q2 that compute y(2i+i)+x(2i-i)y2i and x(2i+i)-x2i for all i 6 [0,31]. While 32 instances of p2 and q2 may initially sound expensive, one can batch them - that is, compute them simultaneously in a SIMD (single instructions, multiple data) fashion - in a small number of operations on 64-bit words. Computer processors 304 typically use a 64-bit architecture, and come up equipped with fast instructions, such as taking the XOR of two 64-bit words, taking their AND (multiplying each pair of corresponding bits from two 64-bit words and putting the result in another 64-bit word) and shift (which can shift the bits in a word left or right).

[0029] This disclosure exploits these fast instructions to make the above computations in a SIMD fashion wherein the computations are fast and in parallel. Specifically, the processor 304 can compute q2 (x(2i+i),y2i,y(2i+i),y2i ) for all i 6 [0,31] simultaneously by computing x ⁽²⁾ :=x AND shiftright l(x) - that is, the system apply the 64-bit AND operation to x and the string x shifted right by 1 position, so that the bit in the i ^th position of x is in the (i - l) ^th position of shiftright l(x). Now bit positions 2i of x ⁽²⁾ for i G [0,31] hold the value x(2i+i)X2i. Next, to compute q4 (x(2i+3), ... , X2i,y(2i+3),...,y2i)) for all i G [0,15], the system sets x ⁽⁴⁾ := x ⁽²⁾ AND shiftright2(x ⁽²⁾ ). Now bit positions 4i for i G [0,15] hold the value x(4i+3)...X4i. The system can stop this process when it has computed x ⁽³²⁾ . Altogether, the system needs only five fast instructions on 64-bit words to compute all of the outputs of the q polynomials that are needed in the computation. The system computes the outputs of p polynomials similarly. Because the outputs of the p polynomials are always in {0, 1}, it suffices to compute the results modulo 2, and therefore the system can replace the + operations in the p polynomials with XOR operations.

[0030] In the O-th step of the recursion, the system starts with x® = x and y^ = y. In the £-th step in the recursion, the system starts with and where the latter has the various results of p ₂ fc-iin it in positions 2 ^k ~ ¹ i. The system then computes as equation (1):

[0031] For 64-bit words, the system needs to obtain the final result of the comparison as y( ²⁶ ) in position 0. This disclosure has described a very efficient COMPARE-Z method for computing the comparison function, but it has not yet been described how to perform COMPARE-Z when the integers A and B are shared. In particular, one can use the “Beaver triples” technique to convert a circuit of XORs (additions) and ANDs (multiplications) into a secure multiparty computation (SMPC) protocol that evaluates a circuit securely. SIMD techniques can also use here. In some aspects, the protocol for 64-bit words can use a Beaver triple that consists of three 64-bit strings R,S,T such that T = R AND S. That is, R,S,T are equivalent to 64 Beaver triples over the field GF(2). The field GF(2) represents a Galois extension field of order 2 ⁿ which are different to computation modulo 2 ⁿ . Notably, every element has an inverse which is not the case in modulo 2 ⁿ . These triples are XOR shared between the parties and employed in the usual way. The shift operations described above are implemented by performing the same shift operations separately on the separate shares held by the parties.

[0032] In sum, the takes as input sharings and satisfying and (where Alice 106 holds and Bob 110 holds (a ^blt , b ^blt )). The operation outputs a sharing of 1 if ^t and a sharing of 0 otherwise. During the computation, using pre- prepared Beaver triples, Alice 106 and Bob 110 use SMPC operations for each XOR and AND gate of the recursively computed comparison circuit described above.

[0033] Additional optimizations to Compare-Z are discussed next, including a compression concept. Recall that, after k steps of the recursion in COMPARE-Z, only the bits in positions carry “useful” information. The other bit positions hold values that are not used in the comparison computation. This seems wasteful. There is a way that the system can put these unused positions in memory to work.

[0034] Suppose one wishes to do many comparisons of 64-bit numbers, not just a single comparison. For example, suppose the system has two pairs of numbers - one wants to compute both and COMPARE-Z . Separately, one can run the first step of the recursive algorithm to obtain words that hold the relevant values of q ₂ and p ₂ lodged in bit positions . Again, only half of the bits in these words will be used in the rest of the comparison computation. Fortunately, one can merge the words together for better efficiency. For example, suppose MA°) and MA ¹ ) are the words that holds the relevant values of q ₂ associated with the comparisons of ) respectively. These values are lodged in positions 2i for i G [0, 31] respectively. The system can apply a shiftleftl to the word MA ¹ ) and, for bit positions 2i + 1 with for i G [0, 31], one can replace bits with bits. That is, the system now has a packed word w that has values for in positions 2i and 32 q ₂ values for in positions 2i + 1. The system can continue the recursion operation as before. Eventually, the system ends up with the results of the comparisons in bit positions 0 (for the comparison) and 1 (for the comparison).

[0035] But one can pack even more data into the process. After the system merges the q ₂ results as described above, and then performs the comparisons, one again is using only half of the bits of each resulting word. So, the system can merge again. Assuming one is trying to evaluate at least four comparisons, the system merges the first and second pairs of comparisons after computing their q ₂ values, and the system merges the merged results into a single word after computing the q ₄ results. Then, again, the system can continue the result of the recursion as before, where the final comparison results would end up in position 0, ... , 3.

[0036] Furthermore, the system can continue to merge. Assuming the system is performing at least 64 comparisons, the system can merge results after each step in the recursion so that eventually the results of all 64 comparisons end up in a single word. This approach reduces both memory and computation as the recursion progresses.

[0037] Next is discussed alternative compression and pipelining concepts. The compression approach above reduces memory usage by half for each step of the recursion. If there is a fixed amount of memory, and one would like to pipe many comparisons through that memory so as to maximize throughput. The following describes another approach to compression.

[0038] The invariant that the system can maintain in this approach is that, at the beginning of a step, a single 64-bit word will hold results associated with six different comparisons, where (roughly speaking) the six comparisons are at six different steps in their recursive computation. One can focus on the first on the word that holds the results of the q polynomials (the x monomials) associated with the six comparisons (the word for the p polynomials is analogous). Specifically, in word w:

1. Positions 32 through 63 will hold the 32 most significant bits of the value of x associated with comparison 1.

2. Positions 16 through 31 will hold the 16 q ₂ results (i.e., the results of the first recursive step applied to the first 32 bits of x) associated with comparison 2.

3. Positions 8 through 15 will hold the 8 q ₈ results (i.e., the results of the second recursive step) associated with comparison 3.

4. Positions 4 through 7 will hold the 4 q ₈ results (i.e., the results of the third recursive step) associated with comparison 4.

5. Positions 2 through 3 will hold the 2 results (i.e., the results of the fourth recursive step) associated with comparison 5.

6. Positions 1 will hold the q ₃₂ result (i.e., the results of the fifth recursive step) associated with comparison 6.

[0039] First, the system saves the result in position 1 elsewhere. Next, the system computes AND shiftrightl(w). Positions 2i of w' now contain the information one would like to keep. Next, the system constructs w"by moving the bit at position 2i to position i, so that this information is in positions [0, 31]. Finally, the system moves the 32 least significant bits associated with a new comparison (comparison 7) into positions [32, 63]. At the end, the system has a new w'" where the invariant has been maintained, except now the results are associated with comparisons 2 through 7 rather than 1 through 6. One can do something similar with the p polynomials. In particular, the system uses the above approach twice, once for the 32 least significant bits of the y values associated with a comparison, and once for the 32 most significant bits. The final results of the comparisons are obtained from the bits that come “off the assembly line” from position 1, and these final computations can be batched as well. The advantage of this approach is that it fully employs a constant amount of memory as comparisons are piped through, and also fully employs the parallel computation capability of the system.

[0040] While Beaver triples are mentioned above, there are variations to using Beaver triples that can be used as well. A modified approach to Beaver triples can be used to reduce the amount of communication, and can even reduce the number of rounds, involved in the comparison protocol.

[0041] Suppose A and B are two 64-bit integers in the range [— 2 ⁶² + 1, 2 ⁶² — 1], Assume further that one has mod-2 ⁶⁴ sharings of these numbers between two parties Alice 106 and Bob 110 - that is, Alice 106 holds a-p b-L 6 [— 2 ⁶³ , 2 ⁶³ — 1] and Bob 110 holds a ₂ , b ₂ 6 [— 2 ⁶³ , 2 ⁶³ — 1] such that A = a _r + a ₂ mod 2 ⁶⁴ and B = b _r + b ₂ mod 2 ⁶⁴ . They now want to run a SMPC protocol to determine whether A > B, using COMPARE-Z as a sub-protocol. Here, one describes such a protocol, COMPARE, that requires only a single invocation of COMPARE-Z.

[0042] In this approach, roughly speaking, the system will compute (sharings of) D =

A —B and check whether D > 0:

1. First, the parties compute shares of D = A -B. That is, Alice 106 computes di = — b _t mod 2 ⁶⁴ and Bob 110 computes d ₂ = a ₂ — b ₂ mod 2 ⁶⁴ where again reduction is into the range [-2 ⁶³ , 2 ⁶³ - 1], It is important that A, B G [-2 ⁶² + 1, 2 ⁶² - 1] to guarantee D is in [— 2 ⁶³ + 2, 2 ⁶³ — 2],

2. They (Alice and Bob) set

3. Each party creates two shares of its own over Z ₂ and sends one share to the other party.

4. Alice and Bob separately compute: k _t = Sj(2 ⁶³ - 1) + di

5. Each party creates binary shares of k^and sends it to the other party. That is, Alice 106 generates a random XOR sharing of k _r (that is, the binary representation of k _t ) and keeps one share to herself and gives the other to Bob 110. Bob 110 does analogous operations for k ₂ . The parties use SMPC to compute:

[r] = COMPARE - ZQkJ, [k ₂ ])

6. The parties (Alice 106 and Bob 110) compute [result] = [r] + [s _t ] + [s ₂ ] mod 2. [0043] The correctness of the reduction is discussed next. Recall some facts from above that can be used to prove correctness:

1. A,B and D = A -B.

2. such that

[0044] To prove correctness, one can consider the various cases of d _± and d ₂ being negative or positive.

Case 1: d _± and d ₂ have the same sign Suppose d _± and d ₂ are both > 0 or both < 0. In this case, d _± — d ₂ is already in the range [— 2 ⁶³ , 2 ⁶³ — 1] without any reduction modulo 2 ⁶⁴ . That is, D = di — d ₂ over Z. So: )

If and , one can have and result =

COMPARE — ZC/q, k ₂ ) = COMPARE — Z(di, d ₂ ), , which is correct.

If and , one can have , and result which is correct.

[0045] Notice that some of these equalities underlying correctness rely on the numbers not overflowing the interval [— 2 ⁶³ , 2 ⁶³ — 1], For example, in the second case above, one can establish that d _± < 0 and d ₂ < 0 and both are in [— 2 ⁶³ , 2 ⁶³ — 1], In that case k _± = d _± + 2 ⁶³ — 1, k ₂ = d ₂ + 2 ⁶³ — 1 1 are also both in [— 2 ⁶³ , 2 ⁶³ — 1], If one had added 2 ⁶³ — 1 to d _r and d ₂ and the result of one addition overflowed (was bigger than 2 ⁶³ - 1, necessitating subtracting 2 ⁶⁴ to get it back in the proper range) while the other addition did not overflow, then comparing the two resulting numbers over the integers Z would give a different result than comparing the original numbers d _lt d ₂ , - leading to incorrectness.

[0046] Case 2: d ₁ > 0 and d ₂ < 0

One can have , and result

If , then result = 1 as computed above. This is correct, since in this case without any wrapping modulo 2 ^M and therefore D is positive, meaning that indeed A > B. If — d ₂ > 2 ⁶³ — 1, then result = 0 as computed above. This is correct, since in this case the system must have D = d ₁ — d ₂ — 2 ⁶⁴ , which must be negative, meaning that it is false that A > B.

[0047] Case 3: di < 0 and d ₂ > 0

One can have and result =

If di — d ₂ > 2 ⁶³ + 1, then result = 0 as computed above. This is correct, since in this case D = di — d ₂ without any wrapping modulo 2 ^s4 and therefore D is negative, meaning that it is false that .A > B.

If d-t — d ₂ < — 2 ⁶³ + 1, then result = 1 as computed above. This is correct, since in the fact that A,B G [— 2 ⁶² + 1, 2 ⁶² — 1] implies that D > — 2 ⁶³ + 2 . Therefore, it must hold that D = di — d ₂ + 2 ⁶⁴ , and therefore D is positive, meaning that indeed A > B.

[0048] The use of a multiparty protocol is described next. Above is described in detail how COMPARE works when two parties, called Alice and Bob, hold shares of the numbers to be compared. Here, this disclosure explains how to extend COMPARE to parties for arbitrary n.

[0049] Let mod 2 ⁶⁴ and mod 2 ⁶⁴ +where party Pt holds shares (a _t , bf). Let D = A B, as before. The approach consists of two parts:

Step 1: From the mod-2 ⁶⁴ sharings, the parties obtain bit-sharings of two numbers d ₁₅ d ₂ such that

Step 2: Given the shares d ₁₅ d ₂ , we proceed basically as before. From d ₁₅ d ₂ , compute s ₁₅ s ₂ , fci, fusing SMPC, then compute COMPARE-Z (k _lt k ₂ ) and finally the result of the comparison.

[0050] Step 1 includes several features. If each party P _t simply secret-shared its shares a _t , b _t - that is, it XOR-shared a _t and bjamong the n parties - then the n parties would have bit-wise sharings of 2n numbers - namely, a^, ... , a _n , —b ₁ , ... , —b _n - whose sum is D modulo 2 ⁶⁴ . The problem now is to reduce the number of numbers in the sum from 2n to 2.

[0051] To solve this problem, the system can use the so-called 3-for-2 trick. The 3-for-2 trick takes 3 numbers in binary representations - for example, r = (r _k , ... , r ₀ ), s = (s _k , ... , s ₀ ), t = (t _k , ... , to). - and outputs 2 numbers in binary representation that have the same sum as the original three numbers. Specifically, the first number is simply the XOR of the three numbers: u = r XOR s XOR t. The second number holds all of the “carry” bits from the addition of the three numbers: v = shiftleftl (v') where v' =

(r AND s) XOR (r AND t) XOR (s AND t). It can be verified that the numbers represented by u, v have the same sum as the numbers represented by r, s, t. Each application of the 3-for-2 trick reduces the number of numbers by 1, so 2n - 2 applications of the trick are needed to reduce the number of numbers from 2n to 2.

[0052] Observe that many triples can be reduced to doubles in parallel. Also, observe that one can reduce communication significantly by not first n-wise sharing the initial values. Rather, for example, small sub-groups of parties can share within the sub-group and each subgroup separately can work to reduce the number of numbers that they are sharing. Once the small subgroups have reduced their number of numbers, they can cross-share with another group (or groups). This merging temporarily increases the number of numbers that are being shared in the group. But they work again to reduce the number of numbers. And so on, until the entire group is sharing only two numbers.

[0053] FIG. 2 illustrates a method 200 related to comparing a first number A ^bit with a second number B ^bit . The method can be performed by a “system” which can include one or more computing devices 300 such as is shown in FIG. 3 and/or FIG. 1. The method 200 can include receiving, from a first computing device associated with the first number A ^bit , a share a ₁ ^bit and a share b ₁ ^bit (202) and receiving, from a second computing device associated with the second number B ^bit , a share a ₂ ^bit and a share b ₂ ^bit , wherein the first number A ^bit = a ₁ ^bit + a ₂ ^bit mod 2 ⁶⁴ and wherein the second number B ^bit = b ₁ ^bit + b ₂ ^bit mod 2 ⁶⁴ , and wherein the first number A ^bit = a ₁ ^bit XOR a ₂ ^bit and wherein the second number B ^bit = b ₁ ^bit XOR b ₂ ^bit , wherein XOR comprises an XOR function that applies addition modulo 2 to corresponding pairs of bits of two strings (204). The method 200 can further include comparing, via a comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate a shared output bit indicating which number is larger (206).

[0054] In some aspects, the first number A ^bit can include a first 64-bit word and the second number B ^bit comprises a second 64-bit word. The share a ₁ ^bit is in a 64-bit format and the share b ₁ ^bit is in the 64-bit format.

[0055] The XOR function can compare a ₁ ^bit with a ₂ ^bit and b ₁ ^bit with b ₂ ^bit on a bit-by -bit basis and not under modulo 2 ⁶⁴ . In another aspect, the comparison function can be represented as a multivariate polynomial in terms of individual bits of A ^bit and B ^bit . The comparison function in such a case applies a recursive approach to evaluate the multivariate polynomial.

[0056] In some aspects, the comparing, via the comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate the shared output bit indicating which number is larger occurs on each of the first computing device and the second computing device (e.g., the first computing device 106 and the second computing device 110).

[0057] In some aspects, the comparison function can apply a Beaver triples technique that converts a circuit of additions and multiplications into a secure multi-party computation protocol that evaluates the circuit securely. The Beaver triples technique in one example uses three 64-bit strings R, S, T such that T - R AND S. The triples R, S and T can be equivalent to 64 Beaver triples over a field GF(2).

[0058] In other aspects, the comparing can be performed using pre-prepared Beaver triples and the first computing device and the second computing device use secure multi-party computation operations for each XOR and AND gate of the comparison function. The comparison function can be implemented as a recursively computed comparison circuit.

[0059] In some aspects, a system (e.g., the computing device 300 and/or a combination of the first computing device 106 and the second computing device 110) for comparing a first number A ^bit with a second number B ^bit . The system includes one or more processors and one or more computer-readable memories storing instructions. When the instructions are executed by the one or more processors, the instructions cause the one or more processors to be configured to: receive, from a first computing device associated with the first number A ^bit , a share a ₁ ^bit and a share b ₁ ^bit ; receive, from a second computing device associated with the second number B ^bit , a share a ₂ ^bit and a share b ₂ ^bit , wherein the first number A ^bit = a ₁ ^bit + a ₂ ^bit mod 2 ⁶⁴ and wherein the second number B ^bit = b ₁ ^bit + b ₂ ^bit mod 2 ⁶⁴ , and wherein the first number A ^bit = a ₁ ^bit XOR a ₂ ^bit and wherein the second number B ^bit = b ₁ ^bit XOR b ₂ ^bit , wherein XOR comprises an XOR function that applies addition modulo 2 to corresponding pairs of bits of two strings; and compare, via a comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate a shared output bit indicating which number is larger.

[0060] In some aspects, the first number A ^bit can include a first 64-bit word and the second number B ^bit comprises a second 64-bit word. The share a ₁ ^bit is in a 64-bit format and the share b ₁ ^bit is in the 64-bit format.

[0061] The XOR function can compare a ₁ ^bit with a ₂ ^bit and b ₁ ^bit with b ₂ ^bit on a bit-by -bit basis and not under modulo 2 ⁶⁴ . In another aspect, the comparison function can be represented as a multivariate polynomial in terms of individual bits of A ^bit and B ^bit . The comparison function in such a case applies a recursive approach to evaluate the multivariate polynomial. [0062] In some aspects, the comparing, via the comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate the shared output bit indicating which number is larger occurs on each of the first computing device and the second computing device (e.g., the first computing device 106 and the second computing device 110).

[0063] In some aspects, the comparison function can apply a Beaver triples technique that converts a circuit of additions and multiplications into a secure multi-party computation protocol that evaluates the circuit securely. The Beaver triples technique in one example uses three 64-bit strings R, S, T such that T - R AND S. The triples R, S and T can be equivalent to 64 Beaver triples over a field GF(2).

[0064] In other aspects, the comparing can be performed using pre-prepared Beaver triples and the first computing device and the second computing device use secure multi-party computation operations for each XOR and AND gate of the comparison function. The comparison function can be implemented as a recursively computed comparison circuit.

[0065] FIG. 3 shows an example of computing system 300, which can be for example any computing device used to compare two number, or any component thereof including components of the system that are in communication with each other using connection 302. Connection 302 can be a physical connection via a bus, or a direct connection into processor 304, such as in a chipset architecture. Connection 302 can also be a virtual connection, networked connection, or logical connection.

[0066] In some embodiments, computing system 300 is a distributed system in which the functions described in this disclosure can be distributed within a datacenter, multiple data centers, a peer network, etc. In some embodiments, one or more of the described system components represents many such components each performing some or all of the function for which the component is described. In some embodiments, the components can be physical or virtual devices.

[0067] Example computing system 300 includes at least one processing unit (CPU or processor) 304 and connection 302 that couples various system components including system memory 308, such as read-only memory (ROM) 310 and random access memory (RAM) 312 to processor 304. Computing system 300 can include a cache of high-speed memory 306 connected directly with, in close proximity to, or integrated as part of processor 304.

[0068] Processor 304 can include any general purpose processor and a hardware service or software service, such as services 316, 318, and 320 stored in storage device 314, configured to control processor 304 as well as a special-purpose processor where software instructions are incorporated into the actual processor design. Processor 304 may essentially be a completely self-contained computing system, containing multiple cores or processors, a bus, memory controller, cache, etc. A multi-core processor may be symmetric or asymmetric.

[0069] To enable user interaction, computing system 300 includes an input device 326, which can represent any number of input mechanisms, such as a microphone for speech, a touch-sensitive screen for gesture or graphical input, keyboard, mouse, motion input, speech, etc. Computing system 300 can also include output device 322, which can be one or more of a number of output mechanisms known to those of skill in the art. In some instances, multimodal systems can enable a user to provide multiple types of input/output to communicate with computing system 300. Computing system 300 can include communication interface 324, which can generally govern and manage the user input and system output. There is no restriction on operating on any particular hardware arrangement, and therefore the basic features here may easily be substituted for improved hardware or firmware arrangements as they are developed.

[0070] Storage device 314 can be a non-volatile memory device and can be a hard disk or other types of computer readable media which can store data that are accessible by a computer, such as magnetic cassettes, flash memory cards, solid state memory devices, digital versatile disks, cartridges, random access memories (RAMs), read-only memory (ROM), and/or some combination of these devices.

[0071] The storage device 314 can include software services, servers, services, etc., that when the code that defines such software is executed by the processor 304, it causes the system to perform a function. In some embodiments, a hardware service that performs a particular function can include the software component stored in a computer-readable medium in connection with the necessary hardware components, such as processor 304, connection 302, output device 322, etc., to carry out the function.

[0072] For clarity of explanation, in some instances, the present technology may be presented as including individual functional blocks including functional blocks comprising devices, device components, steps or routines in a method embodied in software, or combinations of hardware and software.

[0073] Any of the steps, operations, functions, or processes described herein may be performed or implemented by a combination of hardware and software services or services, alone or in combination with other devices. In some embodiments, a service is a program or a collection of programs that carry out a specific function. In some embodiments, a service can be considered a server. The memory can be a non-transitory computer-readable medium.

[0074] In some embodiments, the computer-readable storage devices, mediums, and memories can include a cable or wireless signal containing a bit stream and the like. However, when mentioned, non-transitory computer-readable storage media expressly exclude media such as energy, carrier signals, electromagnetic waves, and signals per se. [0075] Methods according to the above-described examples can be implemented using computer-executable instructions that are stored or otherwise available from computer- readable media. Such instructions can comprise, for example, instructions and data which cause or otherwise configure a general purpose computer, special purpose computer, or special purpose processing device to perform a certain function or group of functions. Portions of computer resources used can be accessible over a network. The executable computer instructions may be, for example, binaries, intermediate format instructions such as assembly language, firmware, or source code. Examples of computer-readable media that may be used to store instructions, information used, and/or information created during methods according to described examples include magnetic or optical disks, solid-state memory devices, flash memory, USB devices provided with non-volatile memory, networked storage devices, and so on.

[0076] Devices implementing methods according to these disclosures can comprise hardware, firmware and/or software, and can take any of a variety of form factors. Typical examples of such form factors include servers, laptops, smartphones, small form factor personal computers, personal digital assistants, and so on. The functionality described herein also can be embodied in peripherals or add-in cards. Such functionality can also be implemented on a circuit board among different chips or different processes executing in a single device, by way of further example.

[0077] The instructions, media for conveying such instructions, computing resources for executing them, and other structures for supporting such computing resources are means for providing the functions described in these disclosures.

[0078] Clauses associated with this description include:

[0079] Clause 1. A method of comparing a first number A ^bit with a second number B ^bit , the method comprising: receiving, from a first computing device associated with the first number A ^bit , a share a ₁ ^bit and a share b ₁ ^bit ; receiving, from a second computing device associated with the second number B ^bit , a share a ₂ ^bit and a share b ₂ ^bit , wherein the first number A ^bit = a ₁ ^bit + a ₂ ^bit mod 2 ⁶⁴ and wherein the second number B ^bit = b ₁ ^bit + b ₂ ^bit mod 2 ⁶⁴ , and wherein the first number A ^bit = a ₁ ^bit XOR a ₂ ^bit and wherein the second number B ^bit = b ₁ ^bit XOR b ₂ ^bit , wherein XOR comprises an XOR function that applies addition modulo 2 to corresponding pairs of bits of two strings; and comparing, via a comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate a shared output bit indicating which number is larger.

[0080] Clause 2. The method of clause 1, wherein the first number A ^bit comprises a first 64-bit word and the second number B ^bit comprises a second 64-bit word.

[0081] Clause 3. The method of any previous clause, wherein the share a ₁ ^bit is in a 64-bit format and the share b ₁ ^bit is in the 64-bit format.

[0082] Clause 4. The method of any previous clause, wherein the XOR function compares a ₁ ^bit with a ₂ ^bit and b ₁ ^bit with b ₂ ^bit on a bit-by -bit basis and not under modulo 2 ⁶⁴ .

[0083] Clause 5. The method of any previous clause, wherein the comparison function is represented as a multivariate polynomial in terms of individual bits of A ^bit and B ^bit .

[0084] Clause 6. The method of any previous clause, wherein the comparison function applies a recursive approach to evaluate the multivariate polynomial.

[0085] Clause 7. The method of any previous clause, wherein the comparing, via comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate the shared output bit indicating which number is larger occurs on each of the first computing device and the second computing device.

[0086] Clause 8. The method of any previous clause, wherein the comparison function applies a Beaver triples technique that converts a circuit of additions and multiplications into a secure multi-party computation protocol that evaluates the circuit securely.

[0087] Clause 9. The method of any previous clause, wherein the Beaver triples technique uses three 64-bit strings R, S, T such that T - R AND S.

[0088] Clause 10. The method of any previous clause, wherein R, S and T are equivalent to 64 Beaver triples over a field GF(2).

[0089] Clause 11. The method of any previous clause, wherein the comparing is performed using pre-prepared Beaver triples and the first computing device and the second computing device use secure multi-party computation operations for each XOR and AND gate of the comparison function.

[0090] Clause 12. The method of any previous clause, wherein the comparison function is implemented as a recursively computed comparison circuit. [0091] Clause 13. A system for comparing a first number A ^bit with a second number B ^bit , the system comprising: one or more processors; and one or more computer-readable memories storing instructions which, when executed by the one or more processors, cause the one or more processors to be configured to: receive, from a second computing device associated with the second number B ^bit , a share a ₂ ^bit and a share b ₂ ^bit , wherein the first number A ^bit = a ₁ ^bit + a ₂ ^bit mod 2 ⁶⁴ and wherein the second number B ^bit = b ₁ ^bit + b ₂ ^bit mod 2 ⁶⁴ , and wherein the first number A ^bit = a ₁ ^bit XOR a ₂ ^bit and wherein the second number B ^bit = b ₁ ^bit XOR b ₂ ^bit , wherein XOR comprises an XOR function that applies addition modulo 2 to corresponding pairs of bits of two strings; and compare, via a comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate a shared output bit indicating which number is larger.

[0092] Clause 14. The system of clause 13, wherein the first number A ^bit comprises a first 64-bit word and the second number B ^bit comprises a second 64-bit word.

[0093] Clause 15. The system of any of clauses 13-14, wherein the share a ₁ ^bit is in a 64-bit format and the share b ₁ ^bit is in the 64-bit format.

[0094] Clause 16. The system of any of clauses 13-15, wherein the XOR function compares a ₁ ^bit with a ₂ ^bit and b ₁ ^bit with b ₂ ^bit on a bit-by -bit basis and not under modulo 2 ⁶⁴ .

[0095] Clause 17. The system of any of clauses 13-16, wherein the comparison function is represented as a multivariate polynomial in terms of individual bits of A ^bit and B ^bit .

[0096] Clause 18. The system of any of clauses 13-17, wherein the comparison function applies a recursive approach to evaluate the multivariate polynomial.

[0097] Clause 19. The system of any of clauses 13-18, wherein the comparing, via comparison function that compares numbers as modulo 2 ⁶⁴ , the first number A ^bit and the second number B ^bit to generate the shared output bit indicating which number is larger occurs on each of the first computing device and the second computing device.

[0098] Clause 20. The system of any of clauses 13-19, wherein the comparison function applies a Beaver triples technique that converts a circuit of additions and multiplications into a secure multi-party computation protocol that evaluates the circuit securely.

[0099] Clause 21. The system of any of clauses 13-20, wherein the Beaver triples technique uses three 64-bit strings R, S, T such that T - R AND S.

[0100] Clause 22. The system of any of clauses 13-21, wherein R, S and T are equivalent to 64 Beaver triples over a field GF(2).

[0101] Clause 23. The system any of clauses 13-22, wherein the comparing is performed using pre-prepared Beaver triples and the first computing device and the second computing device use secure multi-party computation operations for each XOR and AND gate of the comparison function.

[0102] Clause 24. The system of any of clauses 13-23, wherein the comparison function is implemented as a recursively computed comparison circuit.