2014/09/05 by Shaoquan Jiang, Jiang, Shaoquan
Computer Science · Mathematics · #94A60 #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.CR #cs.IT #math.IT #msc:94A60
paper · pdf · doi:10.48550/arxiv.1409.1657
10 pages
arxiv created 2014/09/05 · arxiv updated 2014/09/08
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 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 \cal S and the number of channel W1 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 W1 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.