**Efficient Bit-Decomposition and Modulus-Conversion Protocols with an Honest Majority**

*Ryo Kikuchi and Dai Ikarashi and Takahiro Matsuda and Koki Hamada and 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.

**Category / Keywords: **cryptographic protocols / secret sharing, bit-decomposition, modulus conversion

**Original Publication**** (with minor differences): **ACISP 2018

**Date: **received 10 Apr 2018, last revised 30 Apr 2018

**Contact author: **kikuchi_ryo at fw ipsj or jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20180501:015308 (All versions of this report)

**Short URL: **ia.cr/2018/387

[ Cryptology ePrint archive ]