Welcome to the resource topic for 2018/387
Title:
Efficient Bit-Decomposition and Modulus-Conversion Protocols with an Honest Majority
Authors: Ryo Kikuchi, Dai Ikarashi, Takahiro Matsuda, Koki Hamada, Koji Chida
Abstract:We propose secret-sharing-based bit-decomposition and modulus conversion protocols for a prime order ring \mathbb{Z}_p with an honest majority: an adversary can corrupt k-1 parties of n parties and 2k-1 \le n. Our protocols are secure against passive and active adversaries depending on the components of our protocols. We assume a secret is an \ell-bit element and 2^{\ell+\lceil \log m \rceil} < p, where m= k in the passive security and m= \binom{n}{k-1} in the active security. The outputs of our bit-decomposition and modulus-conversion protocols are \ell tuple of shares in \mathbb{Z}_2 and a share in \mathbb{Z}_{p'}, respectively, where p' is the modulus to be converted. If k and n are small, the communication complexity of our passively secure bit-decomposition and modulus-conversion protocols are O(\ell) bits and O(\lceil \log p' \rceil) bits, respectively. Our key observation is that a quotient of additive shares can be computed from the \emph{least} significant \lceil \log m \rceil bits. If a secret a is ``shifted’’ and additively shared by x_i in \mathbb{Z}_p as 2^{\lceil \log m \rceil}a = \sum_{i=0}^{m-1} x_i = 2^{ \lceil \log m \rceil} a + qp, the least significant \lceil \log m \rceil bits of \sum_{i=0}^{m-1} x_i determines q since p is an odd prime and the least significant \lceil \log m \rceil bits of 2^{\lceil \log m \rceil} a are $0$s.
ePrint: https://eprint.iacr.org/2018/387
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .