On the Optimality of Keyless Authentication in a Noisy Model

Abstract

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 DMC \(W_1\) 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 \(W_1\) does not depend on the size of the source space. If the source space is \({\cal S}\) and the number of channel \(W_1\) uses is \(n\), then our protocol only has a round complexity of \(\log^*|{\cal S}|-\log^*n+4.\) In addition, we show that the round complexity of any secure protocol in our model is lower bounded by \(\log^*|{\cal S}|-\log^* n-5\). We also obtain a lower bound on the success probability when the message size on DMC \(W_1\) is given. Finally, we derive the capacity for a non-interactive authentication protocol under general DMCs, which extends the result under BSCs in our previous work.