Secure Equality and Greater-Than Tests with Sublinear Online Complexity

Secure multiparty computation (MPC) allows multiple parties to evaluate functions without disclosing the private inputs. Secure comparisons (testing equality and greater-than) are important primitives required by many MPC applications. We propose two equality tests for ℓ-bit values with

O

(1) online communication that require

O

(ℓ) respectively

O

(

κ

) total work, where

κ

is a correctness parameter.

Combining these with ideas of Toft [16], we obtain (i) a greater-than protocol with sublinear online complexity in the arithmetic black-box model (

O

(

c

) rounds and

O

(

c

·ℓ

1/

c

) work online, with

c

 = logℓ resulting in logarithmic online work). In difference to Toft, we do not assume two mutually incorruptible parties, but

O

(ℓ) offline work is required, and (ii) two greater-than protocols with the same online complexity as the above, but with overall complexity reduced to

O

(logℓ(

κ

 + loglogℓ)) and

O

(

c

·ℓ

1/

c

(

κ

 + logℓ)); these require two mutually incorruptible parties, but are highly competitive with respect to online complexity when compared to existing protocols.