Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol
Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol
复制标题
DOI：
10.1007/978-3-540-71677-8_23
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
T. Nishide;K. Ohta
中科院分区：
文献类型：
--
作者：
T. Nishide;K. Ohta
Damgårdet al.[11]展示了一种新技术，将秘密的多项式共享转换为恒定轮次的比特共享，称为比特分解协议。位分解协议是一个非常强大的工具，因为即使共享秘密作为字段中的元素给出，它也可以实现面向位的操作。然而，比特分解协议的成本相对较高。本文通过对原始协议的分析，提出了一种简化的比特分解协议。此外，我们构建了更有效的协议来进行共享秘密的比较、区间测试和相等性测试，而不依赖于位分解协议，尽管它对于这种面向位的操作似乎至关重要。关键思想是我们对 Secretawithcandr 进行计算，其中 c=a+r，cis 是一个显示值，ris 是一个随机按位共享秘密。这些协议的输出也被共享而不被泄露。实现的协议以及原始协议都是恒定轮次的，并且比[11]的协议运行时的通信轮次和数据通信更少。例如，回合复杂度降低了大约 3 到 10 倍。
Damgårdet al.[11] showed a novel technique to convert a polynomial sharing of secretainto the sharings of the bits ofain 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 secretawithcandrwherec=a+r,cis a revealed value, andris 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.