Paper 2006/175

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

Moni Naor, 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.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Preliminary version in CRYPTO '06. Full version in IEEE Transactions on Information Theory (special issue on Information-Theoretic Security).
Keywords
authenticationlower boundsone-way functionsunconditional security
Contact author(s)
gil segev @ weizmann ac il
History
2008-07-03: last of 10 revisions
2006-05-22: received
See all versions
Short URL
https://ia.cr/2006/175
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/175,
      author = {Moni Naor and Gil Segev and Adam Smith},
      title = {Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/175},
      year = {2006},
      url = {https://eprint.iacr.org/2006/175}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.