Paper 2018/387

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

Ryo Kikuchi, Dai Ikarashi, Takahiro Matsuda, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACISP 2018
Keywords
secret sharingbit-decompositionmodulus conversion
Contact author(s)
kikuchi_ryo @ fw ipsj or jp
History
2018-05-01: received
Short URL
https://ia.cr/2018/387
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/387,
      author = {Ryo Kikuchi and Dai Ikarashi and Takahiro Matsuda and Koki Hamada and Koji Chida},
      title = {Efficient Bit-Decomposition and Modulus-Conversion Protocols with an Honest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2018/387},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/387}},
      url = {https://eprint.iacr.org/2018/387}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.