FAST SECURE MULTIPARTY COMPARISON OPTIMIZED FOR COMMON COMPUTING ARCHITECTURES

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 1 bit and a share b 1 bit ;

receiving, from a second computing device associated with the second number B bit , a share a 2 bit and a share b 2 bit , wherein the first number A bit =a 1 bit +a 2 bit mod 2 64 and wherein the second number B bit =b 1 bit +b 2 bit mod 2 64 , and wherein the first number A bit =a 1 bit XOR a 2 bit and wherein the second number B bit =b 1 bit XOR b 2 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 64 , the first number A bit and the second number B bit to generate a shared output bit indicating which number is larger.

2 . The method of claim 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.

3 . The method of claim 2 , wherein the share a 1 bit is in a 64-bit format and the share b 1 bit is in the 64-bit format.

4 . The method of claim 1 , wherein the XOR function compares a 1 bit with a 2 bit and b 1 bit with b 2 bit on a bit-by-bit basis and not under modulo 2 64 .

5 . The method of claim 1 , wherein the comparison function is represented as a multivariate polynomial in terms of individual bits of A bit and B bit .

6 . The method of claim 5 , wherein the comparison function applies a recursive approach to evaluate the multivariate polynomial.

7 . The method of claim 1 , wherein the comparing, via comparison function that compares numbers as modulo 2 64 , 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.

8 . The method of claim 1 , 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.

9 . The method of claim 8 , wherein the Beaver triples technique uses three 64-bit strings R, S, T such that T−R AND S.

10 . The method of claim 9 , wherein R, S and T are equivalent to 64 Beaver triples over a field GF(2).

11 . The method of claim 1 , 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.

12 . The method of claim 11 , wherein the comparison function is implemented as a recursively computed comparison circuit.

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 first computing device associated with the first number A bit , a share a 1 bit and a share b 1 bit ;

receive, from a second computing device associated with the second number B bit , a share a 2 bit and a share b 2 bit , wherein the first number A bit =a 1 bit +a 2 bit mod 2 64 and wherein the second number B bit =b 1 bit +b 2 bit mod 2 64 , and wherein the first number A bit =a 1 bit XOR a 2 bit and wherein the second number B bit =b 1 bit XOR b 2 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 64 , the first number A bit and the second number B bit to generate a shared output bit indicating which number is larger.

14 . The system of claim 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.

15 . The system of claim 14 , wherein the share a 1 bit is in a 64-bit format and the share b 1 bit is in the 64-bit format.

16 . The system of claim 13 , wherein the XOR function compares a 1 bit with a 2 bit and b 1 bit with b 2 bit on a bit-by-bit basis and not under modulo 2 64 .

17 . The system of claim 13 , wherein the comparison function is represented as a multivariate polynomial in terms of individual bits of A bit and B bit .

18 . The system of claim 17 , wherein the comparison function applies a recursive approach to evaluate the multivariate polynomial.

19 . The system of claim 13 , wherein the comparing, via comparison function that compares numbers as modulo 2 64 , 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.

20 . The system of claim 13 , 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.

21 . The system of claim 20 , wherein the Beaver triples technique uses three 64-bit strings R, S, T such that T−R AND S.

22 . The system of claim 21 , wherein R, S and T are equivalent to 64 Beaver triples over a field GF(2).

23 . The system of claim 13 , 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.

24 . The system of claim 23 , wherein the comparison function is implemented as a recursively computed comparison circuit.