Multiparty computation for interval, equality, and comparison without bit-decomposition protocol

Abstract. Damg̊ard et al. [11] showed a novel technique to convert a polynomial sharing of secret a into the sharings of the bits of a in con-stant 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 an-alyzing the original protocol. Moreover, we construct more efficient pro-tocols for a comparison, interval test and equality test of shared secrets without relying on the bit-decomposition protocol though it seems es-sential to such bit-oriented operations. The key idea is that we do com-putation 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