Multiround unconditionally secure authentication (Q1273507)

Authentication is known to be one of the major primitives in cryptography. Originally, authentication codes (A-codes) considered for various scenarios were of ''single-round'' type. However, as key size is a very important parameter here, later on multiround A-codes were introduced as an attempt to reduce the size of the key. In the paper unconditionally secure multiround authentication codes (without secrecy) are investigated. First, the multiround authentication model is described and the basic notation introduced. In the next section attacks on multiround A-codes are described and a definition of the probability of a successful attack in an \(n\)-round authentication scheme is given. Subsequently it is shown how the probability of a successful impersonation attack or substitution attack can be calculated in the model. In the next section the construction of a secure efficient scheme with only 3 rounds is given and its security is proved. It is shown that the scheme offers attractive properties as it realizes authentication of very long messages using short keys. To complete the treatment the construction of a secure \(n \geq 3\)-round scheme is given and upper and lower bounds on the key size for a given probability of a successful attack are derived.