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 Zp with an honest majority: an adversary can corrupt k1 parties of n parties and 2k1n. Our protocols are secure against passive and active adversaries depending on the components of our protocols. We assume a secret is an -bit element and 2+logm<p, where m=k in the passive security and m=(nk1) in the active security. The outputs of our bit-decomposition and modulus-conversion protocols are tuple of shares in Z2 and a share in Zp, 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() bits and O(logp) bits, respectively. Our key observation is that a quotient of additive shares can be computed from the \emph{least} significant bits. If a secret is ``shifted'' and additively shared by in as , the least significant bits of determines since is an odd prime and the least significant bits of are 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},
      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.