Date Added: Feb 2011
The authors study the problem of authentication based on a weak key in the information-theoretic setting. A key is weak if its min-entropy is an arbitrary small fraction of its bit length. This problem has recently received considerable attention, with different solutions optimizing different parameters. The authors study the problem in an extended setting, where the weak key is as a one-time session key that is derived from a public source of randomness with the help of a (Potentially also weak) long-term key. The goal now is to authenticate a message by means of the weak session key in such a way that (Nearly) no information on the long-term key is leaked. Ensuring privacy of the long-term key is vital for the long-term key to be re-usable.