Reducing the complexity in the distributed multiplication protocol of two polynomially shared values

The multiparty multiplication of two polynomially shared values over Zq with a public prime number q is an important module in distributed computations. The mul-tiplication protocol of Gennaro, Rabin and Rabin (1998) is considered as the best protocol for this purpose. It re-quires a complexity of O(n2k log n + nk2) bit-operations per player, where k is the bit size of the prime q and n is the number of players. The present paper reduces this complex-ity to O(n2k + nk2) by using Newton’s classical interpola-tion formula. The impact of the new method on distributed signatures is outlined. 1