On the Optimality of Keyless Authentication in a Noisy Model

We further study the keyless authentication problem in a noisy model in our previous work, where no secret setup is available for sender Alice and receiver Bob while there is discrete memoryless channel (DMC) W1 from Alice to Bob and a two-way noiseless but insecure channel between them. We propose a construction such that the message length over DMC W1 does not depend on the size of the source space. If the source space is S and the number of channel W1 uses is n, then our protocol only has a round complexity of log* |S| - log* n + 4. In addition, we show that the round complexity of any secure protocol in our model is lower bounded by log* |S| - log* n - 5. We also obtain a lower bound on the success probability when the message size on DMC W1 is given. Finally, we derive the capacity for a noninteractive authentication protocol under general DMCs, which extends the result under Binary Symmetric Channels in our previous work.