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
-
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},
url = {https://eprint.iacr.org/2016/109}
}
