Paper 2018/387
Efficient BitDecomposition and ModulusConversion Protocols with an Honest Majority
Ryo Kikuchi, Dai Ikarashi, Takahiro Matsuda, Koki Hamada, and Koji Chida
Abstract
We propose secretsharingbased bitdecomposition and modulus conversion protocols for a prime order ring $\mathbb{Z}_p$ with an honest majority: an adversary can corrupt $k1$ parties of $n$ parties and $2k1 \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}{k1}$ in the active security. The outputs of our bitdecomposition and modulusconversion 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 bitdecomposition and modulusconversion 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}^{m1} x_i = 2^{ \lceil \log m \rceil} a + qp$, the least significant $\lceil \log m \rceil$ bits of $\sum_{i=0}^{m1} 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)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Minor revision. ACISP 2018
 Keywords
 secret sharingbitdecompositionmodulus conversion
 Contact author(s)
 kikuchi_ryo @ fw ipsj or jp
 History
 20180501: received
 Short URL
 https://ia.cr/2018/387
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/387, author = {Ryo Kikuchi and Dai Ikarashi and Takahiro Matsuda and Koki Hamada and Koji Chida}, title = {Efficient BitDecomposition and ModulusConversion Protocols with an Honest Majority}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/387}, year = {2018}, url = {https://eprint.iacr.org/2018/387} }