Reducing the Complexity in the Distributed Multiplication Protocol of Two Polynomially Shared Values
Peter Lory · 2007
The multiparty multiplication of two polynomially shared values over Zqwith a public prime number q is an important module in distributed computations. The multiplication protocol of Gennaro, Rabin and Rabin (1998) is considered as the best protocol for this purpose. It requires a complexity of O(n2k log n + nk2) bit-operations per player, where k is the bit size of the prime q andn is the number of players. The present paper reduces this complexity to O(n2k + nk2) by using Newton's classical interpolation formula. The impact of the new method on distributed signatures is outlined.