Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol

Damgård

et al.

[11] showed a novel technique to convert a polynomial sharing of secret

a

into the sharings of the bits of

a

in constant rounds, which is called the bit-decomposition protocol. The bit-decomposition protocol is a very powerful tool because it enables bit-oriented operations even if shared secrets are given as elements in the field. However, the bit-decomposition protocol is relatively expensive.

In this paper, we present a simplified bit-decomposition protocol by analyzing the original protocol. Moreover, we construct more efficient protocols for a comparison, interval test and equality test of shared secrets without relying on the bit-decomposition protocol though it seems essential to such bit-oriented operations. The key idea is that we do computation on secret

a

with

c

and

r

where

c

 = 

a

 + 

r

,

c

is a revealed value, and

r

is a random bitwise-shared secret. The outputs of these protocols are also shared without being revealed.

The realized protocols as well as the original protocol are constant-round and run with less communication rounds and less data communication than those of [11]. For example, the round complexities are reduced by a factor of approximately 3 to 10.