**Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models**

*Moni Naor and Gil Segev and 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.

**Category / Keywords: **cryptographic protocols / authentication, lower bounds, one-way functions, unconditional security

**Publication Info: **Preliminary version in CRYPTO '06. Full version in IEEE Transactions on Information Theory (special issue on Information-Theoretic Security).

**Date: **received 18 May 2006, last revised 3 Jul 2008

**Contact author: **gil segev at weizmann ac il

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20080703:225533 (All versions of this report)

**Short URL: **ia.cr/2006/175

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]