## Tight bounds for unconditional authentication protocols in the manual
channel and shared key models

### Gil Segev, Weizmann

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

25 Aug (Friday) at 1630 hrs
Gates 4B (opposite 490)