On the Optimality of Keyless Authentication in a Noisy Model
This work addresses secure communication without secret setup for senders and receivers, but it is incremental as it builds on previous results in the same model.
The paper tackles the keyless authentication problem in a noisy model by proposing a construction that achieves message length independent of source space size, with round complexity of log*|S| - log*n + 4, and provides matching lower bounds and capacity results for non-interactive protocols.
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.