^June July – 2006

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:

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

2. Our protocol is essentially optimal. We provide a lower bound of $2\log(1/ \epsilon) - 6$ on the required length of the manually authenticated string. Then, we consider the well-known shared secret key authentication model, and apply our proof technique from the first model 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 necessary (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting.

Joint work with Moni Naor and Adam Smith.