Cryptology ePrint Archive: Report 2016/109

Fast Multiparty Multiplications from shared bits

Ivan Damgård and 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.

Category / Keywords: Multiplication, Arithmetic Black Box

Date: received 9 Feb 2016

Contact author: rwl at cs au dk, ivan@cs au dk, tftoft@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160210:220824 (All versions of this report)

Short URL: ia.cr/2016/109

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]