SECURE MULTI-PARTY EQUALITY TESTING

Abstract

The present disclosure involves methods, apparatus, and systems for processing equality testing in secure multi-party computation (MPC). In one aspect, a method includes, generating, by a first party of the secure MPC, a difference between a secret share of a first value and a secret share of a second value. During a first iteration, the difference is partitioned into N sections each including M bits. For each section, a random bit is generated, a group of 2.sup.M bits are generated based on the random bit, and a selected bit from the group of 2.sup.M bits is sent to a second party of the secure MPC based on oblivious transfer (OT) protocol. The random bits of the N sections are concatenated as an input of a second iteration. The method further includes determining whether the first value equals the second value based on performing a plurality of iterations.

Claims

1. A computer-implemented method, comprising: generating, by a first party of a secure multi-party computation (MPC), a first difference between a first secret share of a first value and a first secret share of a second value; during a first iteration of the secure MPC: partitioning the first difference into N sections each comprising M bits, where N and M are positive integers; for each section of the N sections: generating a first random bit; generating, based on the first random bit, a first group of 2.sup.M bits; and sending, to a second party of the secure MPC based on oblivious transfer (OT) protocol, a first selected bit from the first group of 2.sup.M bits; and concatenating first random bits of the N sections as a first input of a second iteration of the secure MPC; and determining whether the first value equals the second value based on performing a plurality of iterations of the secure MPC comprising at least the first iteration and the second iteration.

2. The computer-implemented method of claim 1, comprising: concatenating, by the second party, first selected bits of the N sections as a second input of the second iteration.

3. The computer-implemented method of claim 1, comprising: during the second iteration: partitioning the first input into R sections each comprising M bits, where R is a positive integer; for each section of the R sections: generating a second random bit; generating, based on the second random bit, a second group of 2.sup.M bits; and sending, to the second party based on the OT protocol, a second selected bit from the second group of 2.sup.M bits.

4. The computer-implemented method of claim 1, wherein generating the first group of 2.sup.M bits comprises: generating a k.sup.th bit, (k=0, 1, 2, . . . , 2.sup.M1), of the first group of 2.sup.M bits by performing an exclusive OR (XOR) operation on the first random bit and an indicator bit, wherein the indicator bit is 0 when the a value of the corresponding section equals k, and the indicator bit is 1 when the value of the corresponding section is not equal to k.

5. The computer-implemented method of claim 4, wherein the first selected bit is the Q.sup.th bit of the first group of 2.sup.M bits, wherein Q equals a value of a section of a second difference corresponding to the section of the first difference, wherein the second difference is between a second secret share of the second value and a second secret share of the first value.

6. The computer-implemented method of claim 5, wherein: a result of an XOR operation on the first random bit and the first selected bit is 0 when the value of the section of the first difference and the value of the corresponding section of the second difference are equal; and the result of the XOR operation on the first random bit and the first selected bit is 1 when the value of the section of the first difference and the value of the corresponding section of the second difference are not equal.

7. The computer-implemented method of claim 1, comprising: during a last iteration of the plurality of iterations: generating a last random bit for a first input of the last iteration; generating, based on the last random bit, a last group of 2.sup.M bits; and sending, to the second party based on the OT protocol, a last selected bit from the last group of 2.sup.M bits, wherein determining whether the first value and the second value are equal comprises: performing an XOR operation on the last random bit and the last selected bit.

8. The computer-implemented method of claim 1, wherein determining whether the first value and the second value are equal comprises: performing one or more AND operations on a first input and a second input of a last iteration of the plurality of iterations.

9. The computer-implemented method of claim 5, wherein the first secret share of the first value and the second secret share of the first value are arithmetic shares of the first value, and wherein the first secret share of the second value and the second secret share of the second value are arithmetic shares of the second value.

10. The computer-implemented method of claim 1, wherein the secure MPC is a secure two-party computation.

11. One or more computer-readable storage media storing one or more instructions that, when executable by one or more computers, cause the one or more computers to perform operations comprising: generating, by a first party of a secure multi-party computation (MPC), a first difference between a first secret share of a first value and a first secret share of a second value; during a first iteration of the secure MPC: partitioning the first difference into N sections each comprising M bits, where N and M are positive integers; for each section of the N sections: generating a first random bit; generating, based on the first random bit, a first group of 2.sup.M bits; and sending, to a second party of the secure MPC based on oblivious transfer (OT) protocol, a first selected bit from the first group of 2.sup.M bits; and concatenating first random bits of the N sections as a first input of a second iteration of the secure MPC; and determining whether the first value equals the second value based on performing a plurality of iterations of the secure MPC comprising at least the first iteration and the second iteration.

12. The one or more computer-readable storage media of claim 11, wherein the operations further comprise: concatenating, by the second party, first selected bits of the N sections as a second input of the second iteration.

13. The one or more computer-readable storage media of claim 11, wherein the operations further comprise: during the second iteration: partitioning the first input into R sections each comprising M bits, where R is a positive integer; for each section of the R sections: generating a second random bit; generating, based on the second random bit, a second group of 2.sup.M bits; and sending, to the second party based on the OT protocol, a second selected bit from the second group of 2.sup.M bits.

14. The one or more computer-readable storage media of claim 11, wherein generating the first group of 2.sup.M bits comprises: generating a k.sup.th bit, (k=, 1, 2, . . . , 2.sup.M1), of the first group of 2.sup.M bits by performing an exclusive OR (XOR) operation on the first random bit and an indicator bit, wherein the indicator bit is 0 when a value of the corresponding section equals k, and the indicator bit is 1 when the value of the corresponding section is not equal to k.

15. The one or more computer-readable storage media of claim 14, wherein the first selected bit is the Q.sup.th bit of the first group of 2.sup.M bits, wherein Q equals a value of a section of a second difference corresponding to the section of the first difference, wherein the second difference is between a second secret share of the second value and a second secret share of the first value.

16. The one or more computer-readable storage media of claim 15, wherein: a result of an XOR operation on the first random bit and the first selected bit is 0 when the value of the section of the first difference and the value of the corresponding section of the second difference are equal; and the result of the XOR operation on the first random bit and the first selected bit is 1 when the value of the section of the first difference and the value of the corresponding section of the second difference are not equal.

17. The one or more computer-readable storage media of claim 11, wherein the operations further comprise: during a last iteration of the plurality of iterations: generating a last random bit for a first input of the last iteration; generating, based on the last random bit, a last group of 2.sup.M bits; and sending, to the second party based on the OT protocol, a last selected bit from the last group of 2.sup.M bits, wherein determining whether the first value and the second value are equal comprises: performing an XOR operation on the last random bit and the last selected bit.

18. The one or more computer-readable storage media of claim 11, wherein determining whether the first value and the second value are equal comprises: performing one or more AND operations on a first input and a second input of a last iteration of the plurality of iterations.

19. The one or more computer-readable storage media of claim 15, wherein the first secret share of the first value and the second secret share of the first value are arithmetic shares of the first value, and wherein the first secret share of the second value and the second secret share of the second value are arithmetic shares of the second value.

20. A computer-implemented system comprising: one or more computers; and one or more computer memory devices interoperably coupled with the one or more computers and having computer-readable storage media storing one or more instructions that, when executed by the one or more computers, perform one or more operations comprising: generating, by a first party of a secure multi-party computation (MPC), a first difference between a first secret share of a first value and a first secret share of a second value; during a first iteration of the secure MPC: partitioning the first difference into N sections each comprising M bits, where N and M are positive integers; for each section of the N sections: generating a first random bit; generating, based on the first random bit, a first group of 2.sup.M bits; and sending, to a second party of the secure MPC based on oblivious transfer (OT) protocol, a first selected bit from the first group of 2.sup.M bits; and concatenating first random bits of the N sections as a first input of a second iteration of the secure MPC; and determining whether the first value equals the second value based on performing a plurality of iterations of the secure MPC comprising at least the first iteration and the second iteration.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0017] FIG. 1 illustrates an example process of performing equality testing in a secure multi-party computation (MPC) system.

[0018] FIG. 2 illustrates a flow chart of the example method of performing equality testing in the secure MPC system as shown in FIG. 1.

[0019] FIG. 3 illustrates another example process of performing equality testing in a secure MPC system.

[0020] FIG. 4 illustrates a flow chart of the example method of performing equality testing in the secure MPC system as shown in FIG. 3.

[0021] FIG. 5 illustrates an example of a Vector Oblivious Shift Evaluation (VOSE) protocol using Boolean operation.

[0022] FIG. 6 illustrates an example of a Vector Oblivious Shift Evaluation (VOSE) protocol using arithmetic operation.

[0023] FIG. 7 illustrates another example process of performing equality testing in a secure MPC system.

[0024] FIG. 8 illustrates a flow chart of the example method of performing equality testing in the secure MPC system as shown in FIG. 7.

[0025] FIG. 9 illustrates a schematic diagram of an example computing system.

[0026] Like reference numbers and designations in the various drawings indicate like elements.

DETAILED DESCRIPTION

[0027] This specification relates to methods, apparatuses, and systems for performing equality testing in secure multi-party computation (MPC). Secure equality testing is widely used in many secure computation scenarios, such as privacy-preserving machine learning, private set intersection, secure data mining, etc. Secure equality testing can calculate whether a first private input equals the second private input, without disclosing the private inputs to any party. In secure MPC, especially in secure two-party computation (2PC), secure equality testing remains the bottleneck that affects the performance of the secure MPC.

[0028] The present disclosure provides techniques to improve the speed and efficiency of secure equality testing in secure MPC. In some implementations, the secure MPC can perform equality testing in an iterative approach by invoking oblivious transfer (OT) protocol. In each iteration, a first party (P0) and a second party (P1) can each partition its input into a number of sections. By invoking the OT protocol for each section, the secure MPC can generate secret shares of an indicator indicating whether the corresponding sections of the P0's input and P1's input are equal. The secret shares of the indicator can be inputs of a subsequent iteration. As such, the number of communication rounds between the first party and the second party can be reduced, for example, compared to equality testing based on AND operations.

[0029] In some implementations, in one or more iterations, the secure MPC can invoke an equality testing protocol. The equality testing protocol includes local computation based on Vector Oblivious Shift Evaluation (VOSE) protocol, which can further reduce the number of rounds of online communication between the first party and the second party.

[0030] The described techniques can achieve one or more technical effects. For example, through multiple invocations of the OT protocol, the secure equality testing can be performed with higher speed and efficiency. For another example, the described techniques can reduce the number of communication rounds between the parties of the secure MPC, while balancing the volume of data transmission between parties of the secure MPC. Further, the described techniques can protect data security against two semi-honest parties. In some implementations, additional or different technical effects can be achieved.

[0031] Techniques of the present disclosure can be applied in a variety of practical scenarios. For example, in cryptographic key management, secure MPC can help build an environment for generating, storing, and managing cryptographic keys without the need for a hardware security appliance. For another example, in the healthcare domain, secure MPC can provide a safe solution for encrypting, storing, and transmitting sensitive medical data. For yet another example, in the financial sector, secure MPC can help financial organizations to jointly analyze financial trends without exposing individual customer data.

[0032] The above aspects and some other aspects of the present disclosure are discussed in greater detail below.

[0033] The table below shows some example notations and their corresponding meaning.

TABLE-US-00001 Example Notations Notation Meaning For arithmetic sharing, a value x having l bits in length is shared additively in the ring For Boolean sharing, each bit of a value x having l bits in length is shared independently in the ring x .sup.A Arithmetic share of x x .sup.B Boolean share of x x .sub.i Secret share of x that belongs to party i. 1{b} Indicator function, which equals to 1 when b is true and equals to 0 when b is false. s S Sampling an element s, uniformly at random from S. concatenation operation [x] The smallest integer greater than or equal to x: [x] = min{n Z | n x}

[0034] FIG. 1 illustrates an example process 100 of equality testing in a secure two-party computation (MPC) system. A first party participating in the secure MPC is denoted as Party 0 (P0), and a second party participating in the secure MPC is denoted as Party 1 (P1). The equality testing aims to determine whether two private inputs are equal (e.g., whether a=b), without disclosing the private inputs to any party.

[0035] As starter, the first party P0 has an arithmetic share of the private input a denoted as (a).sub.0.sup.A and an arithmetic share of the private input b denoted as (b).sub.0.sup.A. The second party P1 has an arithmetic share of the private input a denoted as (a).sub.1.sup.A, and an arithmetic share of the private input b denoted as

[00001]${.Math.b.Math.}_1^A.$

The sum of arithmetic shares is the private input, such that

[00002]${.Math.a.Math.}_0^A+{.Math.a.Math.}_1^A=a,\mathrm{and}{.Math.b.Math.}_0^A+{.Math.b.Math.}_1^A=b.$

For example, the secure MPC can generate a random number as

[00003]${.Math.a.Math.}_0^A$

and send it to P0, and generate

[00004]$a-{.Math.a.Math.}_0^A\mathrm{as}{.Math.a.Math.}_1^A$

and send it to P1. As such, the secure MPC system can determine whether a=b by determining whether

[00005]${.Math.a.Math.}_0^A+{.Math.b.Math.}_0^A={.Math.b.Math.}_1^A+{.Math.a.Math.}_1^A.$

[0036] The process 100 can determine whether

[00006]${.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A={.Math.b.Math.}_1^A-{.Math.a.Math.}_1^A$

in an iterative approach by invoking oblivious transfer (OT) protocol. PG generates

[00007]${.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A$

as its initial input x.sub.0, and P1 generates

[00008]${.Math.b.Math.}_1^A-{.Math.a.Math.}_1^A$

as its initial input y.sub.0, where x.sub.0 and y.sub.0 are values in binary form.

[0037] At 102, in a first iteration of the process 100, P0 and P1 set i=0. P0 partitions its input x.sub.i (which is x.sub.0 for the first iteration) into a number of sections x.sub.i,j, such that x.sub.i=x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 . . . x.sub.i,1x.sub.i,0. The length of the input x.sub.i is l.sub.i bits. The length of each section is m.sub.i bits, so that the input is partitioned into

[00009]$q_i=.Math.\frac{l_i}{m_i}.Math.$

sections. As an example, as shown in FIG. 1, P0 inputs x.sub.i=x.sub.0=1101110100110110, which is 16 bits in length. P0 can partition x.sub.0 into four sections, each section being 4 bits in length: x.sub.0,3=1101, x.sub.0,2=1101, x.sub.0,1=0011, and x.sub.0,0=0110. That is, l.sub.i=16, m.sub.i=4, and q.sub.i=4.

[0038] Similarly, P1 partitions its input y.sub.i (which is y.sub.0 for the first iteration) into a number of sections y.sub.i,j, such that y.sub.i=y.sub.i,q.sub.i.sub.1y.sub.i,q.sub.i.sub.2 . . . y.sub.i,0. The length of the input y.sub.i is l.sub.i bits. The length of each section is m.sub.i bits, so that the input is partitioned into

[00010]$q_i=.Math.\frac{l_i}{m_i}.Math.$

sections. As an example, as shown in FIG. 1, P1 inputs y.sub.i=y.sub.0=1101110000110110, which is 16 bits in length. P1 can partition y.sub.0 into four sections, each section being 4 bits in length: y.sub.0,3=1101, y.sub.0,2=1100, y.sub.0,1=0011, and y.sub.0,0=0110.

[0039] At 104, for each section x.sub.i,j (j={0,1, . . . , q.sub.i1}), P0 can generate a random bit

[00011]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B\left\{0,1\right\}.$

The random bit is either 0 or 1. The random bit can be regarded as a Boolean share that belongs to P0. Based on the random bit

[00012]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B,$

P0 can generate a group of M.sub.i bits, each denoted as t.sub.i,j,k, where M.sub.i=2.sup.m.sup.i, and k={0,1, . . . , M.sub.i=1}. Each bit t.sub.i,j,k can be generated as

[00013]$t_{i,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}k\right\}.$

[0040] As an example, for the section x.sub.0,0=0110, P0 generates a random bit 1 as

[00014]${.Math.{\mathrm{eq}}_{0,0}.Math.}_0^B.$

P0 then generates a group of 16 bits, t.sub.0,0,0 to t.sub.0,0,15, where:

[00015]$t_{0,0,0}={.Math.{\mathrm{eq}}_{0,0}.Math.}_0^{B}1\left\{x_{0,0}0\right\}=11=0,$$t_{0,0,1}={.Math.{\mathrm{eq}}_{0,0}.Math.}_0^{B}1\left\{x_{0,0}1\right\}=11=0,.Math.,$$t_{0,0,6}={.Math.{\mathrm{eq}}_{0,0}.Math.}_0^{B}1\left\{x_{0,0}6\right\}=10=1,.Math.,\mathrm{and}$$t_{0,0,15}={.Math.{\mathrm{eq}}_{0,0}.Math.}_0^{B}1\left\{x_{0,0}15\right\}=11=0$

[0041] By invoking the OT protocol, P1 can select and obtain one bit

[00016]$t_{i,j,y_{i,j}}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}{y}_{i,j}\right\}$

from the group of M.sub.i bits. The selected bit t.sub.i,j,y.sub.i,j can be denoted as a Boolean share

[00017]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B$

that belongs to P1, since

[00018]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B=0$

when x.sub.i,j=y.sub.i,j, and

[00019]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B=1$

when x.sub.i,jy.sub.i,j. As such, the MPC can determine whether x.sub.i,j=y.sub.i,j by computing

[00020]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B.$

[0042] As an example, the section of y.sub.0 that corresponds to x.sub.0,0=0110 is y.sub.0,0=0110 (6 in decimal). Based on y.sub.0,0, P1 selects and obtains the bit t.sub.0,0,6 from the 16 bits t.sub.0,0,0 to t.sub.0,0,15. Therefore,

[00021]${.Math.{\mathrm{eq}}_{0,0}.Math.}_1^B=t_{0,0,6}=1.$

Since

[00022]${.Math.{\mathrm{eq}}_{0,0}.Math.}_0^B{.Math.{\mathrm{eq}}_{0,0}.Math.}_1^B=11=0,$

it indicates that x.sub.0,0=y.sub.0,0.

[0043] At 106, P0 can output q.sub.i bits, each bit

[00023]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B$

is a first secret share of an indicator that indicates whether the section x.sub.i,j equals the section y.sub.i,j. Pn1 can output q.sub.i bits, each bit

[00024]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B$

is a second secret share of the indicator. In this way, the input x.sub.i, which is l.sub.i bits in length, can be compressed to a value in binary form having a shorter length (q.sub.i bits in length). As one example, as shown in FIG. 1, in the first iteration of the process 100, P0's input x.sub.0, which is 16 bits in length, is compressed into 4 bits

[00025]${.Math.{\mathrm{eq}}_{0,3}.Math.}_0^B.Math..Math.{.Math.{\mathrm{eq}}_{0,2}.Math.}_0^B.Math..Math.{.Math.{\mathrm{eq}}_{0,1}.Math.}_0^B.Math..Math.{.Math.{\mathrm{eq}}_{0,0}.Math.}_0^B\left(e.g.,0011\right).$

P1's input y.sub.0, which is 16 bits in length, is compressed into 4 bits

[00026]${.Math.{\mathrm{eq}}_{0,3}.Math.}_1^B.Math..Math.{.Math.{\mathrm{eq}}_{0,2}.Math.}_1^B.Math..Math.{.Math.{\mathrm{eq}}_{0,1}.Math.}_1^B.Math..Math.{.Math.{\mathrm{eq}}_{0,0}.Math.}_1^B=t_{0,3,13}.Math..Math.t_{0,2,12}.Math..Math.t_{0,1,2}.Math..Math.t_{0,0,6}\left(e.g.,0011\right).$

[0044] At 108, the process 100 proceeds to a second iteration, where P0 and P1 set i=1. The output of the first iteration can be the input of the second iteration. The input of P0 is

[00027]$x_i={.Math.{\mathrm{eq}}_{i-1,q_{i-1}-1}.Math.}_0^B.Math..Math..Math..Math..Math.{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_0^B.$

The input of P1 is

[00028]$y_i={.Math.{\mathrm{eq}}_{i-1,q_{i-1}-1}.Math.}_1^B.Math..Math..Math..Math..Math.{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_1^B.$

The secure MPC system can determine whether x.sub.0=y.sub.0 by determining whether x.sub.1=y.sub.1.

[0045] Similar to the first iteration, P0 partitions its input x.sub.i (which is x.sub.1 for the second iteration) into a number of sections x.sub.i,j, such that x.sub.i=x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 . . . x.sub.i,0. The length of the input x.sub.i is l.sub.i bits. The length of each section is m.sub.i bits, so that the input is partitioned into

[00029]$q_i=.Math.\frac{l_i}{m_i}.Math.$

sections. As an example, as shown in FIG. 1, P0 inputs x.sub.i=x.sub.1=0011, which is 4 bits in length and can be viewed as one section having 4 bits in length. P1 inputs y.sub.i=y.sub.1=0111, which is 4 bits in length and can be viewed as one section having 4 bits in length. In this example, the second iteration can be the last iteration.

[0046] At 110, similar to 104, for each section x.sub.i,j (j={0,1, . . . , q.sub.i1}), P0 can generate a random bit

[00030]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B\left\{0,1\right\}$

as a Boolean share. Based on the random bit

[00031]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B,$

P0 can generate a group of M.sub.i bits, each denoted as t.sub.i,j,k, where M.sub.i=2.sup.m.sup.i, and k={0,1, . . . , M.sub.i1}. Each bit t.sub.i,j,k can be generated as

[00032]$t_{l,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}k\right\}.$

[0047] As an example, for the section x.sub.1,0=0011, P0 generates a random bit 0 as

[00033]${.Math.{\mathrm{eq}}_{1,0}.Math.}_0^B.$

P0 then generates a group of 16 bit, t.sub.1,0,0 to t.sub.1,0,15, where:

[00034]$$\begin{gathered} t_{1,0,0}={.Math.{\mathrm{eq}}_{1,0}.Math.}_0^{B}1\left\{x_{1,0}0\right\}=01=1, \\ {t}_{1,0,1}={.Math.{\mathrm{eq}}_{1,0}.Math.}_0^{B}1\left\{x_{1,0}1\right\}=01=1,.Math., \\ {t}_{1,0,3}={.Math.{\mathrm{eq}}_{1,0}.Math.}_0^{B}1\left\{x_{1,0}3\right\}=00=0,.Math.,\mathrm{and}{t}_{1,0,15}={.Math.{\mathrm{eq}}_{1,0}.Math.}_0^{B}1\left\{x_{1,0}15\right\}=01=1 \end{gathered}$$

[0048] By invoking the oblivious transfer protocol, P1 can select and obtain one bit

[00035]$t_{i,j,y_{i,j}}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}{y}_{i,j}\right\}$

from the group of M.sub.i bits. The selected bit t.sub.i,j,y.sub.i,j can be denoted as a Boolean share

[00036]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B$

that belongs to P1.

[0049] As an example, based on y.sub.1,0=0111, P1 selects and obtains the bit t.sub.1,0,7 from the 16 bits t.sub.1,0,0 to t.sub.1,0,15. Therefore,

[00037]${.Math.{\mathrm{eq}}_{1,0}.Math.}_1^B=t_{1,0,7}=1.$

[0050] At 112, for the second iteration where i=1, P0 outputs q.sub.i bits, each bit

[00038]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B$

representing a section x.sub.i,j. P1 can output q.sub.i bits, each bit t.sub.i,j,y.sub.i,j representing a section y.sub.i,j. In this way, the input x.sub.i and y.sub.i are each further compressed to a value in binary form having a shorter length.

[0051] The process 100 can include multiple rounds of iteration, until the initial input x.sub.0 and y.sub.0 are each compressed to a single bit. In the last iteration, P0 and P1 each output a single bit.

[0052] At 114, by performing an XOR operation on the single-bit output of the last iteration, the secure MPC can determine whether a=b. In this way, through the iterative approach by invoking oblivious transfer (OT) protocol, the secure MPC system can obtain the result of equality testing.

[0053] As an example shown in FIG. 1, the process includes two rounds of iteration. In the second (last) iteration, P0 outputs

[00039]${.Math.{\mathrm{eq}}_{1,0}.Math.}_0^B=0,$

and P1 outputs

[00040]${.Math.{\mathrm{eq}}_{1,0}.Math.}_1^B=1.$

By computing

[00041]${.Math.{\mathrm{eq}}_{1,0}.Math.}_0^B.Math.{.Math.{\mathrm{eq}}_{1,0}.Math.}_1^B=1,$

the secure MPC system can determine that x.sub.1y.sub.1, which is equivalent to x.sub.0y.sub.0, which is equivalent to ab.

[0054] In some implementations, for the last iteration where i=n and the input x.sub.n and y.sub.n each include only one section, P0 can generate a group of M.sub.n bits each denoted as t.sub.n,0,k, where M.sub.n=2.sup.m.sup.n, and k={0,1, . . . , M.sub.n1}. Each bit t.sub.n,0,k can be generated as

[00042]$t_{n,0,k}={.Math.{\mathrm{eq}}_{n,j}.Math.}_0^B.Math.1\left\{x_{n,0}=k\right\}.$

As such, when performing XOR operation on the single-bit output of

[00043]${.Math.{\mathrm{eq}}_{n,0}.Math.}_0^B$

from P0 and the single-bit output

[00044]${.Math.{\mathrm{eq}}_{n,0}.Math.}_1^B$

from P1,

[00045]${.Math.{\mathrm{eq}}_{n,0}.Math.}_0^B.Math.{.Math.{\mathrm{eq}}_{n,0}.Math.}_1^B=1$

indicates that

[00046]$a=b,\mathrm{and}{.Math.{\mathrm{eq}}_{n,0}.Math.}_0^B.Math.{.Math.{\mathrm{eq}}_{1,0}.Math.}_1^B=0$

indicates that ab.

[0055] It should be noted that the example process 100 is for illustration purposes. The initial input x.sub.0 and y.sub.0 can have any suitable length in bits, the input of each iteration can be partitioned into sections of any suitable length in bits, and the process can include any suitable number of rounds of iteration. For example, the initial input x.sub.0 and y.sub.0 can each include 64 bits, and each be partitioned into 16 sections (each section has a length of 4 bits). The first iteration can compress x.sub.0 and y.sub.0 into x.sub.1 and y.sub.1, x.sub.1 and y.sub.1 each having a length of 16 bits. The second iteration can compress x.sub.1 and y.sub.1 into x.sub.2 and y.sub.2, x.sub.2 and y.sub.2 each having a length of 4 bits. The third (last) iteration can compress x.sub.2 and y.sub.2 into a single bit. By performing an XOR operation on the two single bits, the secure MPC system can determine whether a=b.

[0056] Below is an example algorithm for process 100.

TABLE-US-00002 [00047]$P_0\mathrm{locally}\mathrm{computes}{.Math.d.Math.}_0^A={.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A,P_1\mathrm{locally}\mathrm{computes}{.Math.d.Math.}_1^A={.Math.a.Math.}_1^A-{.Math.b.Math.}_1^A.$ [00048]$P_0\mathrm{sets}{x}_0={.Math.d.Math.}_0^A,P_1\mathrm{sets}{y}_0=-{.Math.d.Math.}_1^A.$ P.sub.0 and P.sub.1 set i = 0. do P.sub.0 parses its input as x.sub.i = x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 ... x.sub.i,0, and P.sub.1 parses its input as [00049]${y_i=y_{i,q_i-1}.Math.y_{i,q_i-2}.Math..Math..Math.y_{i,0},\mathrm{where}{x}_{i,j},y_{i,j}\{0,1)}^{m_i},q_i=.Math.\frac{l_i}{m_i}.Math.,\mathrm{the}\mathrm{bit}\mathrm{lengths}\mathrm{of}$ x.sub.i and y.sub.i are equal, denoted as l.sub.i. Let M.sub.i = 2.sup.m.sup.i for j = {0, 1, ... , q.sub.i 1} do [00050]$P_0\mathrm{samples}{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B\left\{0,1\right\}$ for k = {0, 1, ... , M.sub.i 1} do if q.sub.i > 1 [00051]$P_0\mathrm{sets}{t}_{i,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}k\right\}$ else [00052]$P_0\mathrm{sets}{t}_{i,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}=k\right\}$ end if end for P.sub.0 and P.sub.1 invoke an instance of 1 out of M.sub.i OT, where P.sub.0 is the sender with inputs {t.sub.i,j,k}.sub.k and P.sub.1 is the receiver with input y.sub.i,j. P.sub.1 sets its output as [00053]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B.$ end for P.sub.0 and P.sub.1 compute i = i + 1. [00054]$P_0\mathrm{sets}{x}_i={.Math.{\mathrm{eq}}_{i-1,q_{i-1}-1}.Math.}_0^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_0^B$ [00055]$P_1\mathrm{sets}{y}_i={.Math.{\mathrm{eq}}_{i-1,q_{i-1}-1}.Math.}_1^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_1^B$ while q.sub.i1 > 1 [00056]$P_0\mathrm{and}{P}_1\mathrm{set}\mathrm{their}\mathrm{output}\mathrm{as}{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_0^B\mathrm{and}{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_1^B,\mathrm{respectively}.$

[0057] In some implementations, the last round iteration of process 100 can be performed based on AND operation, instead of based on OT protocol. In the last iteration where P0's input is

[00057]$x_n={.Math.{\mathrm{eq}}_{n-1,q_{n-1}-1}.Math.}_0^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{n-1,0}.Math.}_0^B$

and P0's input is

[00058]$y_n={.Math.{\mathrm{eq}}_{n-1,q_{n-1}-1}.Math.}_1^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{n-1,0}.Math.}_1^B,$

the secure MPC can determine whether x.sub.n=y.sub.n by computing

[00059]$1\left\{{.Math.{\mathrm{eq}}_{n-1,q_{n-1}-1}.Math.}_0^B={.Math.{\mathrm{eq}}_{n-1,q_{n-1}-1}.Math.}_1^B\right\}\mathrm{AND}.Math.\mathrm{AND}$$\left\{{.Math.{\mathrm{eq}}_{n-1,q_0-1}.Math.}_0^B={.Math.{\mathrm{eq}}_{n-1,q_0-1}.Math.}_1^B\right\}.$

If the result of the AND operations is 1, x.sub.n=y.sub.n. If the result of the AND operations is 0, x.sub.ny.sub.n.

[0058] As an example shown in FIG. 1, P0's input of the last iteration is x.sub.1=0011, P1's input of the last iteration is y.sub.1=0111. P1 can locally compute

[00060]$y_1^{}=y_{1}0111=1000.$

In the first round of AND operation, the secure MPC can perform an XOR operation on the first bit of x.sub.1 and the first bit of

[00061]$y_1^{},$

an XOR operation on the second bit of x.sub.1 and the second bit of

[00062]$y_1^{},$

and an AND operation on the results of the two XOR operations, such that (01) AND (00)=1 AND 0=0. The result can be a first input of the second round of AND operation. Then, the secure MPC can perform an XOR operation on the third bit of x.sub.1 and the third bit of

[00063]$y_1^{},$

an XOR operation on the fourth bit of x.sub.1 and the fourth bit of

[00064]$y_1^{},$

and an AND operation on the results of the two XOR operations, such that (10) AND (10)=1 AND 1=1. The result can be a second input of the second round of AND operation. In the second round of AND operation, the secure MPC can perform an AND operation on the first input and the second input, such that 0 AND 1=0. If the result of the last AND operation is 0, it means x.sub.1y.sub.1, which is equivalent to ab. If the result of the last AND operation is 1, it means x.sub.1=y.sub.1, which is equivalent to a=b.

[0059] Below is an example algorithm for process 100 where the last iteration performs equality testing based on AND operations.

TABLE-US-00003 [00065]$P_0\mathrm{locally}\mathrm{computes}{.Math.d.Math.}_0^A={.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A,P_1\mathrm{locally}\mathrm{computes}{.Math.d.Math.}_1^A={.Math.a.Math.}_1^A-{.Math.b.Math.}_1^A.$ [00066]$P_0\mathrm{sets}{x}_0={.Math.d.Math.}_0^A,P_1\mathrm{sets}{y}_0=-{.Math.d.Math.}_1^A.$ P.sub.0 and P.sub.1 set i = 0. do P.sub.0 parses its input as x.sub.i = x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 ... x.sub.i,0, and P.sub.1 parses its input as [00067]${y_i=y_{i,q_i-1}.Math.y_{i,q_i-2}.Math..Math..Math.y_{i,0},\mathrm{where}{x}_{i,j},y_{i,j}\{0,1)}^{m_i},q_i=.Math.\frac{l_i}{m_i}.Math.,\mathrm{the}\mathrm{bit}\mathrm{lengths}\mathrm{of}$ x.sub.i and y.sub.i are equal, denoted as l.sub.i. Let M.sub.i = 2.sup.m.sup.i for j = {0, 1, ... , q.sub.i 1} do [00068]$P_0\mathrm{samples}{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B\left\{0,1\right\}$ for k = {0, 1, ... , M.sub.i 1} do if q.sub.i > T [00069]$P_0\mathrm{sets}{t}_{i,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}k\right\}$ else [00070]$P_0\mathrm{sets}{t}_{i,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}=k\right\}$ end if end for P.sub.0 and P.sub.1 invoke an instance of 1 out of M.sub.i OT, where P.sub.0 is the sender with inputs {t.sub.i,j,k}.sub.k and P.sub.1 is the receiver with input y.sub.i,j. P.sub.1 sets its output as [00071]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B.$ end for P.sub.0 and P.sub.1 compute i = i + 1. [00072]$P_0\mathrm{sets}{x}_i={.Math.{\mathrm{eq}}_{i-1,q_{i-1}-1}.Math.}_0^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_0^B$ [00073]$P_1\mathrm{sets}{y}_i={.Math.{\mathrm{eq}}_{i-1,q_{i-1}-1}.Math.}_1^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_1^B$ while q.sub.i1 > T for k = {1, ... , log(q.sub.i)} do for j = {0, 1, ... , q.sub.i/2.sup.k 1)} do [00074]$\mathrm{for}b\left\{0,1\right\},P_b\mathrm{invokes}\mathrm{AND}\mathrm{with}\mathrm{inputs}{.Math.{\mathrm{eq}}_{k-1,2j}.Math.}_b^B\mathrm{and}{.Math.{\mathrm{eq}}_{k-1,2j+1}.Math.}_b^B\mathrm{to}$ [00075]$\mathrm{learn}\mathrm{output}{.Math.{\mathrm{eq}}_{k,j}.Math.}_b^B.$ end for end for [00076]$P_0\mathrm{and}{P}_1\mathrm{set}\mathrm{their}\mathrm{output}\mathrm{as}{.Math.{\mathrm{eq}}_{.Math.\log \left(q_{i-1}\right).Math.,0}.Math.}_0^B\mathrm{and}{.Math.{\mathrm{eq}}_{.Math.\log \left(q_{i-1}\right).Math.,0}.Math.}_1^B,\mathrm{respectively}.$

[0060] FIG. 2 illustrates a flow chart of the example method 200 of performing equality testing as shown in FIG. 1. The operations shown in method 200 may not be exhaustive and that other operations can be performed as well before, after, or in between any of the illustrated operations. Further, some of the operations may be performed simultaneously, or in a different order than shown in FIG. 2. In some implementations, some of the operations may be performed by a computer, or multiple computers based on secure MPC.

[0061] At 202, a first party (e.g., P0 of FIG. 1) of a secure multi-party computation (MPC) generates a first difference (e.g., x.sub.0 of FIG. 1) between a first secret share (e.g., arithmetic share

[00077]${.Math.a.Math.}_0^A)$

of a first value (e.g., private input a) and a first secret share (e.g., arithmetic share

[00078]${.Math.b.Math.}_0^A)$

of a second value (e.g., private input b). The second party (e.g., P1 of FIG. 1) of the secure MPC generates a second difference (e.g., y.sub.0 of FIG. 1) between a second secret share (e.g., arithmetic share

[00079]${.Math.b.Math.}_1^A)$

of the second value and a second secret share (e.g., arithmetic share

[00080]${.Math.a.Math.}_1^A)$

of the first value.

[0062] At 204, during a first iteration of the secure MPC, the first party partitions the first difference into N sections (e.g., x.sub.0=x.sub.0,3x.sub.0,2x.sub.0,1x.sub.0,0) each including M bits, where N and M are positive integers. The second party partitions the second difference into N sections (e.g., y.sub.0=y.sub.0,3y.sub.0,2y.sub.0,1y.sub.0,0) each including M bits.

[0063] At 206, for each section of the N sections, the first party generates a first random bit (e.g.,

[00081]${.Math.{\mathrm{eq}}_{0,j}.Math.}_0^B$

of FIG. 1), generates a first group of 2.sup.M bits (e.g., t.sub.0,j,0 to t.sub.0,j,15 of FIG. 1) based on the first random bit, and sends, to the second party and based on oblivious transfer (OT) protocol, a first selected bit (e.g., t.sub.0,j,y.sub.0,j, also denoted as

[00082]${.Math.{\mathrm{eq}}_{0,j}.Math.}_1^B$

in FIG. 1) from the first group of 2.sup.M bits.

[0064] In some implementations, the first group of 2.sup.M bits are generated by generating a k.sup.th bit, (k=0, 1, 2, . . . , 2.sup.M1), of the first group of 2.sup.M bits by performing an exclusive OR (XOR) operation on the first random bit and an indicator bit (e.g., 1{x.sub.0,jk} of FIG. 1). The indicator bit is 0 when a value of the corresponding section equals k, and the indicator bit is 1 when the value of the section is not equal to k.

[0065] Further, the first selected bit is the Ql bit of the first group of 2.sup.M bits, where Q equals the value of a corresponding section (e.g., y.sub.0,j of FIG. 1) of the second difference. As such, a result of an XOR operation on the first random bit and the first selected bit is 0 when the value of the section of the first difference and the value of the corresponding section of the second difference are equal. The result of the XOR operation on the first random bit and the first selected bit is 1 when the value of the section of the first difference and the value of the corresponding section of the second difference are not equal.

[0066] At 208, the first party concatenates first random bits of the N sections as a first input (e.g., x.sub.1 of FIG. 1) of a second iteration of the secure MPC. The second party concatenates first selected bits of the N sections as a second input (e.g., y.sub.1 of FIG. 1) of the second iteration.

[0067] In some implementations, during the second iteration, the first party partitions the first input into R sections each including M bits, and the second party partitions the second input into R sections each including M bits, where R is a positive integer. For each section of the R sections, the first party generates a second random bit (e.g.,

[00083]${.Math.{\mathrm{eq}}_{1,0}.Math.}_0^B$

of FIG. 1), generates a second group of 2.sup.M bits (e.g., t.sub.1,0,0 to t.sub.1,0,15 of FIG. 1) based on the second random bit, and sends, to the second party based on the OT protocol, a second selected bit (e.g., t.sub.1,0,y.sub.1,0, also denoted as

[00084]${.Math.{\mathrm{eq}}_{1,0}.Math.}_1^B$

of FIG. 1) from the second group of 2.sup.M bits.

[0068] At 210, the secure MPC determines whether the first value equals the second value based on results of a plurality of iterations of the secure MPC. The plurality of iterations includes at least the first iteration and the second iteration.

[0069] In some implementations, the last iteration of the plurality of iterations is also performed based on OT protocol. During the last iteration, the first party generates a last random bit, generates a last group of 2.sup.M bits based on the last random bit, and sends, to the second party based on the OT protocol, a last selected bit from the last group of 2.sup.M bits. The secure MPC determines whether the first value and the second value are equal by performing an XOR operation on the last random bit and the last selected bit.

[0070] In some implementations, the last iteration of the plurality of iterations is performed based on AND operations. The secure MPC determines whether the first value and the second value are equal by performing one or more AND operations on a first input and a second input of the last iteration.

[0071] FIG. 3 illustrates an example process 300 of equality testing in a secure two-party computation (MPC) system. A first party participating in the secure MPC is denoted as Party 0 (P0), and a second party participating in the secure MPC is denoted as Party 1 (P1). The equality testing aims to determine whether two private inputs are equal (e.g., whether a=b), without disclosing the private inputs to any party.

[0072] As starter, the first party P0 has an arithmetic share of the private input a denoted as

[00085]${.Math.a.Math.}_0^A$

and an arithmetic share of the private input b denoted as

[00086]${.Math.b.Math.}_0^A.$

The second party P1 has an arithmetic share of the private input a denoted as

[00087]${.Math.a.Math.}_1^A,$

and an arithmetic share of the private input b denoted as

[00088]${.Math.a.Math.}_0^A+{.Math.a.Math.}_1^A=a,$$\mathrm{and}{.Math.b.Math.}_0^A+{.Math.b.Math.}_1^A=b.$

The sum of arithmetic shares is the private input, such that

[00089]${.Math.b.Math.}_1^A.$

For example, the secure MPC can generate a random integer as

[00090]${.Math.a.Math.}_0^A$

and send it to P0, and generate

[00091]$a-{.Math.a.Math.}_0^A\mathrm{as}{.Math.a.Math.}_1^A$

and send it to P1. As such, the secure MPC system can determine whether a=b by determining whether

[00092]${.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A={.Math.b.Math.}_1^A-{.Math.a.Math.}_1^A.$

[0073] The process 300 can determine whether

[00093]${.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A={.Math.b.Math.}_1^A-{.Math.a.Math.}_1^A$

in an iterative approach by invoking oblivious transfer (OT) protocol. P0 generates

[00094]${.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A$

as its initial input x.sub.0, and P1 generates

[00095]${.Math.b.Math.}_1^A-{.Math.a.Math.}_1^A$

as its initial input y.sub.0, where x.sub.0 and y.sub.0 are values in binary form.

[0074] At 302, in a first iteration of the process 300, P0 and P1 set i=0. P0 partitions its input x.sub.i (which is x.sub.0 for the first iteration) into a number of sections x.sub.i,j, such that x.sub.i=x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 . . . x.sub.i,1x.sub.i,0. The length of the input x.sub.i is l.sub.i bits. The length of each section is m.sub.i bits, so that the input is partitioned into

[00096]$q_i=.Math.\frac{l_i}{m_i}.Math.$

sections. As an example, as shown in FIG. 3, P0 inputs x.sub.i=x.sub.0=1101110100110110, which is 16 bits in length. P0 can partition x.sub.0 into four sections, each section being 4 bits in length: x.sub.0,3=1101, x.sub.0,2=1101, x.sub.0,1=0011, and x.sub.0,0=0110.

[0075] Similarly, P1 partitions its input y.sub.i (which is y.sub.0 for the first iteration) into a number of sections y.sub.i,j, such that y.sub.i=y.sub.i,q.sub.i.sub.1y.sub.i,q.sub.i.sub.2 . . . y.sub.i,0. The length of the input y.sub.i is l.sub.i bits. The length of each section is m.sub.i bits, so that the input is partitioned into

[00097]$q_i=.Math.\frac{l_i}{m_i}.Math.$

sections. As an example, as shown in FIG. 3, P1 inputs y.sub.i=y.sub.0=1101110000110110, which is 16 bits in length. P1 can partition y.sub.0 into four sections, each section being 4 bits in length: y.sub.0,3=1101, y.sub.0,2=1300, y.sub.0,1=0011, and y.sub.0,0=0110. That is, l.sub.i=16, m.sub.i=4, and q.sub.i=4.

[0076] At 304, for each section x.sub.i,j (j={0,1, . . . , q.sub.i1}), P0 can generate a random integer

[00098]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A\left\{0,1,...,q_i\right\}.$

The random integer is sampled from 0 to q.sub.i. The random integer can be regarded as an arithmetic share that belongs to P0. Based on the random integer

[00099]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A,$

P0 can generate a group of M.sub.i integers, each denoted as t.sub.i,j,k, where M.sub.i=2.sup.m.sup.i, and k={0,1, . . . , M.sub.i1}. Each bit t.sub.i,j,k can be generated as

[00100]$t_{i,j,k}=\left(1\left\{x_{i,j}k\right\}-{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right).$

[0077] As an example, for the section x.sub.0,0=0110, P0 generates a random integer 4 as

[00101]${.Math.{\mathrm{eq}}_{0,0}.Math.}_0^A.$

P0 then generates a group of 16 integers, t.sub.0,0,0 to t.sub.0,0,15, where:

[00102]$t_{0,0,0}=\left(1\left\{x_{0,0}0\right\}-{.Math.{\mathrm{eq}}_{0,0}.Math.}_0^A\right)\mathrm{mod}\left(q_0+1\right)=\left(1-4\right)\mathrm{mod}5=2,$$t_{0,0,1}=\left(1\left\{x_{0,0}1\right\}-{.Math.{\mathrm{eq}}_{0,0}.Math.}_0^A\right)\mathrm{mod}\left(q_0+1\right)=\left(1-4\right)\mathrm{mod}5=2,...,$$t_{0,0,6}=\left(1\left\{x_{0,0}6\right\}-{.Math.{\mathrm{eq}}_{0,0}.Math.}_0^A\right)\mathrm{mod}\left(q_0+1\right)=\left(0-4\right)\mathrm{mod}5=1,...,\mathrm{and}$$t_{0,0,15}=\left(1\left\{x_{0,0}15\right\}-{.Math.{\mathrm{eq}}_{0,0}.Math.}_0^A\right)\mathrm{mod}\left(q_0+1\right)=\left(1-4\right)\mathrm{mod}5=2.$

[0078] By invoking the OT protocol, P1 can select and obtain one integer

[00103]$t_{i,j,y_{i,j}}=\left(1\left\{x_{i,j}{y}_{i,j}\right\}-{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right)$

from the group of M.sub.i integers. The selected integer t.sub.i,j,y.sub.i,j can be denoted as ab arithmetic share

[00104]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^A$

that belongs to P1 since

[00105]$\left({.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A+{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^A\right)\mathrm{mod}\left(q_i+1\right)=0$

when x.sub.i,j=y.sub.i,j, and

[00106]$\left({.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A+{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^A\right)\mathrm{mod}\left(q_i+1\right)0$

when x.sub.i,jy.sub.i,j. As such, the secure MPC can determine whether x.sub.i,j=y.sub.i,j by computing

[00107]$\left({.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A+{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^A\right)\mathrm{mod}\left(q_i+1\right).$

[0079] As an example, the section of y.sub.0 that corresponds to x.sub.0,0=0110 is y.sub.0,0=0110. Based on y.sub.0,0, P1 selects and obtains the integer t.sub.0,0,6 from the 16 integers t.sub.0,0,1 to t.sub.0,0,15. Therefore,

[00108]${.Math.{\mathrm{eq}}_{0,0}.Math.}_1^A=t_{0,0,6}=1.$

Since

[00109]$\left({.Math.{\mathrm{eq}}_{0,0}.Math.}_0^A+{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B\right)\mathrm{mod}5=\left(4+1\right)\mathrm{mod}5=0,$

it indicates that x.sub.0,0=y.sub.0,0.

[0080] At 306, P0 can output

[00110]$\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_0^A+...+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right).$

P1 can output

[00111]$\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_1^A+...+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_1^A\right)\mathrm{mod}\left(q_i+1\right).$

When x.sub.0=y.sub.0, the sum of the two outputs is a multiple of (q.sub.i+1). When x.sub.0y.sub.0, the sum of the two outputs is not a multiple of (q.sub.i+1). As one example, as shown in FIG. 3, in the first iteration of the process 300, P0's input x.sub.0, which is 16 bits in length, is compressed into the output of one integer

[00112]$\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_0^A+...+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right),$

which can be represented by 3 bits (e.g., 2=010). P1's input y.sub.0, which is 16 bits in length, is compressed into the output of one integer

[00113]$\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_1^A+...+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_1^A\right)\mathrm{mod}\left(q_i+1\right),$

which can also be represented by 3 bits (e.g., 4=100).

[0081] The process 300 proceeds to a second iteration, where P0 and P1 set i=1. The output of the first iteration can be the input of the second iteration. The input from P0 is

[00114]$x_i=\left({.Math.{\mathrm{eq}}_{i-1,0}.Math.}_0^A+...+{.Math.{\mathrm{eq}}_{i-1,q_i-1}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right).$

The input from P1 is

[00115]$y_i=\left[-\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_1^A+...+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_1^A\right)\right]\mathrm{mod}\left(q_i+1\right).$

The secure MPC system can determine whether x.sub.0=y.sub.0 by determining whether x.sub.1=y.sub.1.

[0082] In some implementations, the following iterations (including the second iteration) can be performed in the same approach as the first iteration, where P0 generate a random integer, generates a group of integers based on the random integer, and sends a selected integer from the group of integers based on OT protocol. In some implementations, some of the following iterations can be performed in the approach as shown in process 100.

[0083] At 308, P0 can partition its input x.sub.i into a number of sections x.sub.i,j, such that x.sub.i=x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 . . . x.sub.i,1x.sub.i,0. The length of the input x.sub.i is l.sub.i bits. The length of each section is m.sub.i bits, so that the input is partitioned into

[00116]$q_i=.Math.\frac{l_i}{m_i}.Math.$

sections. As an example, as shown in FIG. 3, P0 inputs x.sub.i=x.sub.1=010, which is 3 bits in length. x.sub.1 can be viewed as a single section x.sub.1=x.sub.1,0. That is, l.sub.i=3, m.sub.i=3, and q.sub.i=1.

[0084] Similarly, P1 partitions its input y.sub.i into a number of sections y.sub.i,j, such that y.sub.i=y.sub.i,q.sub.i.sub.1y.sub.i,q.sub.i.sub.2 . . . y.sub.i,0. The length of the input y.sub.i is l.sub.i bits. The length of each section is m.sub.i bits, so that the input is partitioned into

[00117]$q_i=.Math.\frac{l_i}{m_i}.Math.$

sections. As an example, as shown in FIG. 3, P1 inputs y.sub.i=y.sub.1=001, which is 3 bits in length. y.sub.1 can be viewed as a single section y.sub.1=y.sub.1,0. That is, l.sub.i=3, m.sub.i=3, and q.sub.i=1.

[0085] At 310, for each section x.sub.i,j(j={0,1, . . . , q.sub.i1}), P0 can generate a random bit

[00118]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B\left\{0,1\right\}.$

The random bit includes one bit of either 0 or 1. The random bit can be regarded as a Boolean share that belongs to P0. Based on the random integer

[00119]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B,$

P0 can generate a group of M.sub.i bits, each denoted as t.sub.i,j,k, where M.sub.i=2.sup.m.sup.i, and k={0,1, . . . , M.sub.i1}. Each bit t.sub.i,j,k can be generated as

[00120]$t_{i,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}=k\right\}.$

[0086] As an example, for the section x.sub.1,0=010, P0 generates a random bit 0 as

[00121]${.Math.{\mathrm{eq}}_{1,0}.Math.}_0^B.$

P0 then generates a group of 8 bit, t.sub.1,0,0 to t.sub.1,0,7, where:

[00122]$\begin{array}{c}{t}_{1,0,0}={.Math.{\mathrm{eq}}_{1,0}.Math.}_0^{B}1\left\{x_{1,0}=0\right\}=00=0,\\ t_{1,0,1}={.Math.{\mathrm{eq}}_{1,0}.Math.}_0^{B}1\left\{x_{1,0}=1\right\}=00=0,\\ t_{1,0,2}={.Math.{\mathrm{eq}}_{1,0}.Math.}_0^{B}1\left\{x_{1,0}=2\right\}=01=1,.Math.,\mathrm{and}\\ t_{1,0,7}={.Math.{\mathrm{eq}}_{1,0}.Math.}_0^{B}1\left\{x_{0,0}=7\right\}=00=0\end{array}$

[0087] By invoking the OT protocol, P1 can select and obtain one bit

[00123]$t_{i,j,y_{i,j}}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}=y_{i,j}\right\}$

from the group of M.sub.i bits. The selected bit t.sub.i,j,y.sub.i,j can be denoted as a Boolean share

[00124]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B$

that belongs to P1, since

[00125]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B=1$

when x.sub.i,j=y.sub.i,j, and

[00126]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B=0$

when x.sub.i,jy.sub.i,j. As such, the MPC can determine whether x.sub.i,j=y.sub.i,j by computing

[00127]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B{.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B.$

[0088] At 312, for the second iteration where i=1, P0 outputs q.sub.i bits, each bit

[00128]${.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B$

is a first secret share of an indicator that indicates whether the section x.sub.i,j equals the section y.sub.i,j. P1 can output q.sub.i bits, each bit

[00129]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B$

is a second secret share of the indicator. In this way, the input x.sub.i and y.sub.i are each further compressed to a value in binary form having a shorter length.

[0089] The process 300 can include multiple rounds of iteration, until the initial input x.sub.0 and y.sub.0 are each compressed to a single bit. In the last iteration, P0 and P1 each output a single bit.

[0090] At 314, by performing an XOR operation on the single-bit output of the last iteration, the secure MPC can determine whether a=b. In this way, through the iterative approach by invoking OT protocol, the secure MPC system can obtain the result of equality testing.

[0091] As an example, the section of y.sub.0 that corresponds to x.sub.1,0=010 is y.sub.1,0=001. Based on y.sub.1,0, P1 selects and obtains the bit t.sub.1,0,1 from the 8 bits t.sub.1,0,0 to t.sub.1,0,7. Therefore,

[00130]${.Math.{\mathrm{eq}}_{1,0}.Math.}_1^B=t_{1,0,1}=0.$

Since

[00131]${.Math.{\mathrm{eq}}_{1,0}.Math.}_0^B{.Math.{\mathrm{eq}}_{1,0}.Math.}_1^B=00=0,$

it indicates that x.sub.1,0y.sub.1,0, which is equivalent to x.sub.0y.sub.0, which is equivalent to ab.

[0092] It should be noted that the example process 300 is for illustration purposes. The initial input x.sub.0 and y.sub.0 can have any suitable length in bits, the input of each iteration can be partitioned into sections of any suitable length in bits, and the process can include any suitable number of rounds of iteration. For example, the initial input x.sub.0 and y.sub.0 can each include 64 bits, and are each partitioned into 16 sections (each section has a length of 4 bits). By implementing the process 300, the first iteration can compress x.sub.0 and y.sub.0 into x.sub.1 and y.sub.1, x.sub.1 and y.sub.1 each having a length of 5 bits. The second iteration can implement the process 100, and compress x.sub.1 and y.sub.1 into x.sub.2 and y.sub.2, x.sub.2 and y.sub.2 each having a length of 3 bits. The third (last) iteration can implement the process 100, and compress x.sub.2 and y.sub.2 into a single bit. By performing an XOR operation on the two single bits, the secure MPC system can determine whether a=b.

[0093] Below is an example algorithm for process 300.

TABLE-US-00004 [00132]$P_0\mathrm{locally}\mathrm{computes}{.Math.d.Math.}_0^A={.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A,P_1\mathrm{locally}\mathrm{computes}{.Math.d.Math.}_1^A={.Math.a.Math.}_1^A-{.Math.b.Math.}_1^A.$ [00133]$P_0\mathrm{sets}{x}_0={.Math.d.Math.}_0^A,P_1\mathrm{sets}{y}_0=-{.Math.d.Math.}_1^A.$ P.sub.0 and P.sub.1 set i = 0. do P.sub.0 parses its input as x.sub.i = x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 ... x.sub.i,0, and P.sub.1 parses its input as [00134]${y_i=y_{i,q_i-1}.Math.y_{i,q_i-2}.Math..Math..Math.y_{i,0},\mathrm{where}{x}_{i,j},y_{i,j}\{0,1)}^{m_i},q_i=.Math.\frac{l_i}{m_i}.Math.,\mathrm{the}\mathrm{bit}\mathrm{lengths}\mathrm{of}$ x.sub.i and y.sub.i are equal, denoted as l.sub.i. Let M.sub.i = 2.sup.m.sup.i for j = {0, 1, ... , q.sub.i 1} do [00135]$P_0\mathrm{samples}{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A\left\{0,1,.Math.,q_i\right\}$ for k = {0, 1, ... , M.sub.i 1} do [00136]$P_0\mathrm{sets}{t}_{i,j,k}=\left(1\left\{x_{i.j}k\right\}-{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right)$ end for P.sub.0 and P.sub.1 invoke an instance of 1 out of M.sub.i OT, where P.sub.0 is the sender with inputs {t.sub.i,j,k}x and P.sub.1 is the receiver with input y.sub.i,j. P.sub.1 sets its output as [00137]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^A.$ end for [00138]$P_0\mathrm{sets}{x}_{i+1}=\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_0^A+.Math.+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right)$ [00139]$P_1\mathrm{sets}{y}_{i+1}=[-\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_1^A+.Math.+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_1^A\right)\mathrm{mod}\left(q_i+1\right)$ P.sub.0 and P.sub.1 compute i = i + 1. while q.sub.i1 > T, T is threshold value do P.sub.0 parses its input as x.sub.i = x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 ... x.sub.i,0, and P.sub.1 parses its input as [00140]${y_i=y_{i,q_i-1}.Math.y_{i,q_i-2}.Math..Math..Math.y_{i,0},\mathrm{where}{x}_{i,j},y_{i,j}\{0,1)}^{m_i},q_i=.Math.\frac{l_i}{m_i}.Math.,\mathrm{the}\mathrm{bit}\mathrm{lengths}\mathrm{of}$ x.sub.i and y.sub.i are equal, denoted as l.sub.i. Let M.sub.i = 2.sup.m.sup.i for j = {0, 1, ... , q.sub.i 1} do [00141]$P_0\mathrm{samples}{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^B\left\{0,1\right\}$ for k = {0, 1, ... , M.sub.i 1} do if q.sub.i > 1 [00142]$P_0\mathrm{sets}{t}_{i,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}k\right\}$ else [00143]$P_0\mathrm{sets}{t}_{i,j,k}={.Math.{\mathrm{eq}}_{i,j}.Math.}_0^{B}1\left\{x_{i,j}=k\right\}$ end if end for P.sub.0 and P.sub.1 invoke an instance of 1 out of M.sub.i OT, where P.sub.0 is the sender with inputs {t.sub.i,j,k}x and P.sub.1 is the receiver with input y.sub.i,j. P.sub.1 sets its output as [00144]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^B.$ end for [00145]$P_0\mathrm{sets}{x}_{i+1}={.Math.{\mathrm{eq}}_{i,0}.Math.}_0^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_0^B$ [00146]$P_1\mathrm{sets}{y}_{i+1}={.Math.{\mathrm{eq}}_{i,0}.Math.}_1^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_1^B$ P.sub.0 and P.sub.1 compute i = i + 1. while q.sub.i1 > 1 [00147]$P_0\mathrm{and}{P}_1\mathrm{set}\mathrm{their}\mathrm{output}\mathrm{as}{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_0^B\mathrm{and}{.Math.{\mathrm{eq}}_{i-1,0}.Math.}_1^B,\mathrm{respectively}.$

[0094] In some implementations, the last round iteration of process 300 can be performed based on AND operation, instead of based on oblivious transfer (OT) protocol. In the last iteration where P0's input is

[00148]$x_n={.Math.{\mathrm{eq}}_{n-1,q_{n-1}-1}.Math.}_0^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{n-1,0}.Math.}_0^B$

and P0's input is

[00149]$y_n={.Math.{\mathrm{eq}}_{n-1,q_{n-1}-1}.Math.}_1^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{n-1,0}.Math.}_1^B,$

secure MPC can determine whether x.sub.n=y.sub.n by computing

[00150]$1\left\{{.Math.{\mathrm{eq}}_{n-1,q_{n-1}-1}.Math.}_0^B={.Math.{\mathrm{eq}}_{n-1,q_{n-1}-1}.Math.}_1^B\right\}\mathrm{AND}.Math.\mathrm{AND}1\left\{{.Math.{\mathrm{eq}}_{n-1,q_0-1}.Math.}_0^B={.Math.{\mathrm{eq}}_{n-1,q_0-1}.Math.}_1^B\right\}.$

If the result of the AND operations is 1, x.sub.n=y.sub.n. If the result of the AND operations is 0, x.sub.ny.sub.n.

[0095] As an example shown in FIG. 3, P0's input of the last iteration is x.sub.1=010, P1's input of the last iteration is y.sub.1=001. P1 can locally compute y.sub.1=y.sub.1111=110. In the first round of AND operation, the secure MPC can perform an XOR operation on the first bit of x.sub.1 and the first bit of

[00151]$y_1^{},$

an XOR operation on the second bit of x.sub.1 and the second bit of

[00152]$y_1^{},$

and an AND operation on the results of the two XOR operations, such that (01) AND (11)=0 AND 1=0. The result can be an input of the second round of AND operation. Then the secure MPC can perform an XOR operation on the third bit of x.sub.1 and the third bit of

[00153]$y_1^{},$

and an AND operation on the results of the AND operation of the last round, such that (00) AND 0=0. If the result of the last AND operation is 0, it means x.sub.1y.sub.1, which is equivalent to ab. If the result of the last AND operation is 1, it means x.sub.1=y.sub.1, which is equivalent to a=b.

[0096] Below is an example algorithm for process 300 where the last iteration performs equality testing based on AND operations.

TABLE-US-00005 [00154]$P_0\mathrm{locally}\mathrm{computes}{.Math.d.Math.}_0^A={.Math.a.Math.}_0^A-{.Math.b.Math.}_0^A,P_1\mathrm{locally}\mathrm{computes}{.Math.d.Math.}_1^A={.Math.a.Math.}_1^A-{.Math.b.Math.}_1^A.$ [00155]$P_0\mathrm{sets}{x}_0={.Math.d.Math.}_0^A,P_1\mathrm{sets}{y}_0=-{.Math.d.Math.}_1^A.$ P.sub.0 and P.sub.1 set i = 0. do P.sub.0 parses its input as x.sub.i = x.sub.i,q.sub.i.sub.1x.sub.i,q.sub.i.sub.2 ... x.sub.i,0, and P.sub.1 parses its input as [00156]${y_i=y_{i,q_i-1}.Math.y_{i,q_i-2}.Math..Math..Math.y_{i,0},\mathrm{where}{x}_{i,j},y_{i,j}\{0,1)}^{m_i},q_i=.Math.\frac{l_i}{m_i}.Math.,\mathrm{the}\mathrm{bit}\mathrm{lengths}\mathrm{of}$ x.sub.i and y.sub.i are equal, denoted as l.sub.i. Let M.sub.i = 2.sup.m.sup.i for j = {0, 1, ... , q.sub.i 1} do [00157]$P_0\mathrm{samples}{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A\left\{0,1,.Math.,q_i+1\right\}$ for k = {0, 1, ... , M.sub.i 1} do if q.sub.i > 1 [00158]$P_0\mathrm{sets}{t}_{i,j,k}=\left(1\left\{x_{i,j}k\right\}-{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right)$ else [00159]$P_0\mathrm{sets}{t}_{i,j,k}=\left(1\left\{x_{i,j}=k\right\}-{.Math.{\mathrm{eq}}_{i,j}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right)$ end if end for P.sub.0 and P.sub.1 invoke an instance of 1 out of M.sub.i OT, where P.sub.0 is the sender with inputs {t.sub.i,j,k}.sub.k and P.sub.1 is the receiver with input y.sub.i,j. P.sub.1 sets its output as [00160]${.Math.{\mathrm{eq}}_{i,j}.Math.}_1^A.$ end for [00161]$P_0\mathrm{sets}{x}_{i+1}=\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_0^A+.Math.+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_0^A\right)\mathrm{mod}\left(q_i+1\right)$ [00162]$P_1\mathrm{sets}{y}_{i+1}=[-\left({.Math.{\mathrm{eq}}_{i,0}.Math.}_1^A+.Math.+{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_1^A\right)\mathrm{mod}\left(q_i+1\right)$ P.sub.0 and P.sub.1 compute i = i + 1. while q.sub.i1 > T, T is threshold value [00163]$P_0\mathrm{parses}\mathrm{its}\mathrm{input}\mathrm{as}{x}_i={.Math.{\mathrm{eq}}_{i,0}.Math.}_0^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_0^B,\mathrm{and}{P}_1\mathrm{parses}\mathrm{its}\mathrm{input}\mathrm{as}{y}_i=$ [00164]${.Math.{\mathrm{eq}}_{i,0}.Math.}_1^B.Math..Math..Math.{.Math.{\mathrm{eq}}_{i,q_i-1}.Math.}_1^B.Math.q_i\mathrm{is}\mathrm{the}\mathrm{bit}\mathrm{length}\mathrm{of}{x}_i\mathrm{and}{y}_i.$ for k = {1, ... , log(q.sub.i)} do for j = {0, ... , q.sub.i/2.sup.k 1)} do [00165]$\mathrm{for}b\left\{0,1\right\},P_b\mathrm{invokes}\mathrm{AND}\mathrm{with}\mathrm{inputs}{.Math.{\mathrm{eq}}_{k-1,2j}.Math.}_b^B\mathrm{and}{.Math.{\mathrm{eq}}_{k-1,2j+1}.Math.}_b^B\mathrm{to}$ [00166]$\mathrm{learn}\mathrm{output}{.Math.{\mathrm{eq}}_{k,j}.Math.}_b^B.$ end for end for [00167]$P_0\mathrm{and}{P}_1\mathrm{set}\mathrm{their}\mathrm{output}\mathrm{as}{.Math.{\mathrm{eq}}_{.Math.\log \left(q_i\right).Math.,0}.Math.}_0^B\mathrm{and}{.Math.{\mathrm{eq}}_{.Math.\log \left(q_i\right).Math.,0}.Math.}_1^B,\mathrm{respectively}.$