Mobile computing is a technology that allows transmission of data, voice and video via a computer or any other wireless enabled device without having to be connected to a fixed physical link. With today’s technology, many applications rely on the existence of small devices that can exchange information and form communication networks. In a significant portion of such applications, the confidentiality and integrity of the communicated messages are of particular interest. In this paper, the authors propose two novel techniques for authenticating short encrypted messages that are directed to meet the requirements of mobile and pervasive applications.