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:
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.
Gates 4B (opposite 490)