Welcome to the resource topic for 2006/175
Title:
Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models
Authors: Moni Naor, Gil Segev, Adam Smith
Abstract:We address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to ``manually’’ authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any 0 < \epsilon < 1 there exists a \log^* n-round protocol for authenticating n-bit messages, in which only 2 \log(1 / \epsilon) + O(1) bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most \epsilon to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of 2 \log(1 / \epsilon) - O(1) on the required length of the manually authenticated string. The second model we consider is the traditional message authentication model. In this model the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. We apply the proof technique above to obtain a lower bound of 2 \log(1 / \epsilon) - 2 on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (CRYPTO '93). Finally, we prove that one-way functions are {\em necessary} (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting.
ePrint: https://eprint.iacr.org/2006/175
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 .