Authentication amplification by synchronization

Information-theoretic message authentication is traditionally defined as the task of authenticating a message, transmitted over an insecure channel, using a secret key shared between sender and receiver. Previous results have investigated the trade-offs between key size, message size, and the adversary´s cheating probability. In this paper we propose a new approach to information-theoretic authentication, without a secret key, but assuming that a short message (much shorter than the actual message) can be transmitted authentically, for example by speaker identification over the phone. By using such a scheme recursively one can authenticate arbitrarily long messages if one can authenticate a very short message whose length only depends on the desired cheating probability, and if it is guaranteed as a mild form of synchronization that every message arrives before the next one is sent. This result has also implications for key-based authentication. If the short message is itself authenticated with a key-based scheme, this combined scheme yields an optimal key-based authentication scheme for arbitrarily long messages, provably beating the best traditional authentication code, i.e., the best scheme that transmits a single key-dependent message over an insecure channel. The required key size is independent of the message length, which is impossible to achieve for traditional authentication codes. The proposed schemes are not only of theoretical interest but may well have practical applications in contexts where information-theoretic security is required, for example in quantum cryptography.