Constant-Round Multiparty Computation for Interval Test, Equality Test, and Comparison

• NISHIDE Takashi

  Hitachi Software Engineering Co., Ltd.

• OHTA Kazuo

  Graduate School of Electro-Communications, the University of Electro-Communications

Abstract

We propose constant-round protocols for interval tests, equality tests, and comparisons where shared secret inputs are not given bitwise. In [9]. Damgard et al. presented a novel protocol called the bit-decomposition, which can convert a polynomial sharing of an element in prime field Z_p into sharings of bits. Though, by using the bit-decomposition protocol, those protocols can be constructed with constant round complexities theoretically, it involves expensive computation, leading to relatively high round and communication complexities. In this paper, we construct more efficient protocols for those protocols without relying on the bit-decomposition protocol. In the interval test protocol, checking whether a shared secret exists in the known interval is reduced to checking whether a bitwise-shared random secret exists in the appropriate interval. In the comparison protocol, comparing two shared secrets is reduced to comparing the two secrets via p/2 indirectly where p is an odd prime for an underlying linear secret sharing scheme. In the equality test protocol, checking whether two shared secrets are equal is reduced to checking whether the difference of the two secrets is zero and furthermore checking whether the difference is a zero is reduced to checking quadratice residuosity of a random secret in a probabilistic way.

Journal

• IEICE transactions on fundamentals of electronics, communications and computer sciences

  IEICE transactions on fundamentals of electronics, communications and computer sciences 90 (5), 960-968, 2007-05-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• multiparty computation
• secret sharing
• bitwise sharing
• computing with encrypted data

Details

• CRID: 1570009752602408448
• NII Article ID: 110007519160
• NII Book ID: AA10826239
• ISSN: 09168508
• Text Lang: en
• Data Source:
  • CiNii Articles