Reducing the Complexity in the Distributed Multiplication Protocol of Two Polynomially Shared Values

The multiparty multiplication of two polynomially shared values over Z_q with 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(n²k log n + nk²) 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(n²k + nk²) by using Newton´s classical interpolation formula. The impact of the new method on distributed signatures is outlined.