Communication complexity of secure distributed computation in the presence of noise
Eytan Modiano, Anthony Ephremides · IEEE Transactions on Information Theory · 1992
A simple model of distributed computation that requires information exchange over a noisy channel is considered. A communication protocol is utilized that requires alternate bit exchanges between two processors. First, the case of a single public channel is considered and the number of bits that need to be exchanged between the processors to permit delta -accuracy in their goal is compared. For this computation, an error-detection-and-retransmission mechanism of error control and an error-correction-and-retransmission mixture that are consistent with the logical protocol that governs this exchange are considered. Second, the case of the availability of an additional secret channel is considered and interest in determining the minimum number of bits that need to be exchanged over a secret channel in order to maintain in -uncertainty about the computation for an eavesdropper on the public channel is shown. Various subcases under this case are considered and an upper bound on the number of secret bits when no error-control scheme is used is obtained.>