On the optimal communication complexity of multiphase protocols for perfect communication

In the perfectly secure message transmission (PSMT) problem, two synchronized non-faulty players (or processors), the Sender S and the Receiver R are connected by n wires (each of which facilitates 2-way communication); S has a message, represented by a sequence off elements from a finite field, that he wishes to send to R; after exchanging messages in phases R should correctly obtain S's message, while an adversary listening on and actively controlling any set of t (or less) wires should have no information about S's message. Similarly, in the problem of perfect reliable message transmission (PRMT), the receiver R should correctly obtain S's message, in spite of the adversary actively controlling an)? set of t (or less) wires. In this paper we prove a lower bound of Omega(nl/n-2t) field elements on communication complexity of any PSMT protocol. In the literature, it is known that there exists a two-phase PSMT protocol with a communication complexity of O(nl/n-2t) field elements [1]. Thus, we infer that with respect to communication complexity of PSMT, surprisingly, additional phases (beyond two) do not help! Similarly, we prove a lower bound of Omega)(nl/n-t) field elements on communication complexity of any PRMT protocol; since a three-phase PRMT protocol with a complexity of O(nl/n-t) field elements is known [16], we may infer that with respect to communication complexity of PRMT additional phases (beyond three) do not help! An interesting and key ingredient of our proof technique is a reduction from Secret Sharing to PSMT and PRMT While it is well-known that PSMT can be reduced to secret sharing [9], the reduction other way round is proved in this paper for the first time in the literature.