Paper 2021/158

Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate

Abstract

In the model of Perfectly Secure Message Transmission (PSMT), a sender Alice is connected to a receiver Bob via $n$ parallel two-way channels, and Alice holds an $\ell$ symbol secret that she wishes to communicate to Bob. There is an unbounded adversary Eve that controls $t$ of the channels, where $n=2t+1$. Eve is able to corrupt any symbol sent through the channels she controls, and furthermore may attempt to infer Alice's secret by observing the symbols sent through the channels she controls. The transmission is required to be (a) reliable, i.e., Bob must always be able to recover Alice's secret, regardless of Eve's corruptions; and (b) private, i.e., Eve may not learn anything about Alice's secret. We focus on the two-round model, where Bob is permitted to first transmit to Alice, and then Alice responds to Bob. In this work we provide upper and lower bounds for the PSMT model when the length of the communicated secret $\ell$ is asymptotically large. Specifically, we first construct a protocol that allows Alice to communicate an $\ell$ symbol secret to Bob by transmitting at most $2(1+o_{\ell \to \infty}(1))n\ell$ symbols. Under a reasonable assumption (which is satisfied by all known efficient two-round PSMT protocols), we complement this with a lower bound showing that $2n\ell$ symbols are necessary for Alice to privately and reliably communicate her secret. This provides strong evidence that our construction is optimal (even up to the leading constant).

Note: In this revised version, we have corrected a mistake in our lower bound proof. We have added an additional assumption to make the proof go through. We also added more remarks comparing our work to prior work.