Hybrid authentication based on noisy channels

We consider a cryptographic scenario where some center broadcasts a random binary string to Alice, Bob and Eve over binary symmetric channels with bit error probabilities e _A, e _B and e _E respectively. Alice and Bob share no secret key initially, and their goal is to generate, after public discussion, a common information-theoretically secure key facing an active eavesdropper Eve. Under the condition e _AE and e _BE, code authentication (CA) can be used as part of a public discussion protocol to solve this problem. This authentication exploits parts of substrings received by Alice and Bob from the broadcasting center as authenticators to messages transmitted in a public discussion. Unfortunately, it happens to be ineffective because it produces a key of small length. We propose a hybrid authentication (HA) that combines both keyless code authentication and key authentication based on an almost strong universal class of hash functions. We prove a theorem that allows estimation of the performance evaluation of hybrid authentication. The selection algorithm for the main HA parameters, given security and reliability thresholds, is presented in detail.