Vaudenay recently proposed a message authentication protocol which is interactive and based on short authenticated strings
(SAS). We study here SAS-based non-interactive message authentication protocols (NIMAP). We start by the analysis of two popular
non-interactive message authentication protocols. The first one is based on a collision-resistant hash function and was presented
by Balfanz et al. The second protocol is based on a universal hash function family and was proposed by Gehrmann, Mitchell,
and Nyberg. It uses much less authenticated bits but requires a stronger authenticated channel.
We propose a protocol which can achieve the same security as the first protocol but using less authenticated bits, without
any stronger communication model, and without requiring a hash function to be collision-resistant. Finally, we demonstrate
the optimality of our protocol.