Is it possible to carry out multiplication of BGW protocol without communication?

Question

I read the following famous two papers related to multiparty computation and I have a question like title.

• [AL17] Gilad Asharov, and Yehuda Lindell. "A full proof of the BGW protocol for perfectly secure multiparty computation." Journal of Cryptology 2017.
• [CDI05] Cramer, Ronald, Ivan Damgård, and Yuval Ishai. "Share conversion, pseudorandom secret-sharing and applications to secure computation." Theory of Cryptography Conference 2005.

In [AL17], authors constructed a protocol that privately computes multiplication given access to the randomization functionality and the degree-reduction functionality. While they also proposed a secure degree-reduction protocol (i.e. protocol to privately compute degree-reduction functionality) without communication, the proposed randomization protocol (i.e. protocol to privately compute randomization functionality) needs n^2 communications.

Authors of [CDI05] showed that a proposed protocol (PRZS) can create a pseudorandom zero-sharing with degree 2t (i.e. the randomization protocol) without communication.

Therefore, I’m wondering whether it is possible to carry out multiplication of BGW protocol without communication if the randomization protocol of [AL17] is replaced by PRZS protocol of [CDI05]. (Except for the communication of input sharing stage and output reconstruction stage) Moreover, given an application consisting of addition and multiplication, is it possible to construct a multiparty computation protocol based on BGW without communication?

Answer 1

No, it is impossible. We do not know of any way to perform this randomization step without interaction; furthermore, it was shown in this paper that multiplication require interactions in secure computation, in a variety of important settings (including all forms of BGW-style secure computation). Share conversions work for some restricted type of functionalities, but do not allow to evaluate generic multiplication gate over $\mathbb{F}_2$ on secret shares without interaction.

Note, however, that we can have multiparty computation with no interaction (except for sending an encryption of the input and sending back an encryption of the output) in the computational setting, using fully homomorphic encryption (which we can build assuming the LWE assumption).