[Resource Topic] 2021/158: Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate

Welcome to the resource topic for 2021/158

Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate

Authors: Nicolas Resch, Chen Yuan


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).

ePrint: https://eprint.iacr.org/2021/158

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .