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

### 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 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) - 6 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.
Once again, we apply our proof technique, and prove 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 necessary (and
sufficient) for the existence of protocols breaking the above lower
bounds in the computational setting.

Paper: PDF. Slides:
ppt

Related On-Line Papers:
- Peter Gemmell and Moni Naor,
**Codes for Interactive
Authentication, **** **
Abstract ,
Paper: Postscript, gzipped
Postscript.
- Danny Dolev, Cynthia Dwork and Moni Naor ,
*Non-Malleable
Cryptography,* Siam J. on Computing 30(2), 2000, pp.
391-437.

Back to On-Line Publications

Back Home