Paper 2016/109

Fast Multiparty Multiplications from shared bits

Ivan Damgård, Tomas Toft, and Rasmus Winther Zakarias

Abstract

We study the question of securely multiplying N-bit integers that are stored in binary representation, in the context of protocols for dishonest majority with preprocessing. We achieve communication complexity O(N) using only secure operations over small fields F_2 and F_p with log(p) \approx log(N). For semi-honest security we achieve communication O(N)2^{O(log∗(N))} using only secure operations over F_2. This improves over the straightforward solution of simulating a Boolean multiplication circuit, both asymptotically and in practice.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
MultiplicationArithmetic Black Box
Contact author(s)
rwl @ cs au dk
ivan @ cs au dk
tftoft @ gmail com
History
2016-02-10: received
Short URL
https://ia.cr/2016/109
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/109,
      author = {Ivan Damgård and Tomas Toft and Rasmus Winther Zakarias},
      title = {Fast Multiparty Multiplications from shared bits},
      howpublished = {Cryptology ePrint Archive, Paper 2016/109},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/109}},
      url = {https://eprint.iacr.org/2016/109}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.